An Introduction to Elliptic Curve Cryptography - Introduction to Cryptography with Maple - page 640

Mestre-Shanks method—to compute the order of the group. This algorithm is much
more efficient than the naive point counting we have seen but is not efficient enough
for curves of cryptographic size, where one has to apply Schoof's algorithm or the
SEA algorithm.
Consider the following prime, used in [75] to define an elliptic curve:
> p192 := 2ˆ192-2ˆ64-1;
6277101735386680763835789423207666416083908700390324961279
We define an elliptic curve over this prime:
> ec192 := EllipticCurve(-1512718932230020811709266491917131419968886211715362931724,
1769520287457231963690687866380165522983746710433431160335, p192):
The point
> pt192 := [6268594639044626559588135250819421255947009647065456089152,
4094928720749295414661683627820549126173799055397430561800]
can be shown to have order equal to:
> opt192 := 562662171652688657360198955576059:
To check that this number is indeed the order of the point we first show that
opt192 multiplied by the point gives the point at infinity:
> EllipticMult(opt192, pt192, ec192);
0
This shows that the order of pt192 divides opt192 and to see that the two are
equal we have to show that if pt192 is multiplied by the result of dividing opt192
by any one of its prime factors, then the result is different from the point at infinity.
This can be done independently for each of the three prime factors of opt192 but
we do it in one pass:
> member(0, map(x -> EllipticMult(x, pt192, ec192),
iquo ∼ (opt192, op ∼ (1, ifactors(opt192)[2]))));
false
Next we check whether the order opt192 is greater than 4 √ p :
> evalb(opt192 > evalf(4*sqrt(p192)));
true
Since this property holds, we know from our previous discussion regarding
Hasse's theorem that opt192 has a unique multiple in the Hasse interval, which
must be equal to the order of the curve. We compute this order as follows:
> o192:= opt192*iquo(p192+1+floor(evalf(2*sqrt(p192))), opt192);
6277101735386680763835789423128040313757010230206649133264
Exercise 11.20 Consider the curve ec192 defined in Example 11.16 and deter-
mine the structure of its group of rational points as follows (some knowledge of the
structure theorem for finite abelian groups is required for this purpose).