Elliptic Curves over Finite Fields - Elliptic Curves: Number Theory and Cryptography - page 113

PROOF Let k be the order of g .Then k | M . Suppose k = M .Let p i be

a prime dividing M/k .Then p i k | M ,so k | ( M/p i ). Therefore, ( M/p i ) g =0,

contrary to assumption. Therefore k = M .

Therefore, step (6) finds the order of P .

REMARK 4.22 (1) To save storage space, it might be more ecient to
store only the x coordinates of the points jP (along with the corresponding
integer j ), since looking for a match with ±jP only requires the x -coordinate
(assuming we are working with a Weierstrass equation). When a match is
found, the two possible y -coordinates can be recomputed.
(2) Computing Q + k (2 mP ) can be done by computing Q and 2 mP once
for all. To get from Q + k (2 mP )to Q +( k + 1)(2 mP ), simply add 2 mP rather
than recomputing everything. Similarly, once jP has been computed, add P
to get ( j +1) P .
(3) We are assuming that we can factor M . If not, we can at least find all
the small prime factors p i and check that ( M/p i ) P

= ∞ for these. Then M

will be a good candidate for the order of P .
(4) Why is the method called “Baby Step, Giant Step”? The baby steps
are from a point jP to ( j +1) P .The giant steps are from a point k (2 mP )
to ( k + 1)(2 mP ), since we take the “bigger” step 2 mP .

Example 4.11
Let E be the elliptic curve y 2 = x 3 10 x +21 over F 557 , as in Example 4.7.

Let P =(2 , 3). We follow the procedure above.

−

1. Q = 558 P = (418 , 33).

2. Let m = 5, which is greater than 557 1 / 4 . The list of jP is

∞, (2 , 3) , (58 , 164) , (44 , 294) , (56 , 339) , (132 , 364) .

3. When k =1,wehave Q + k (2 mP )=(2 , 3), which matches the point on
our list for j =1.

4. We have ( q +1+2 mk − j ) P = 567 P = ∞ .

5. Factor 567 = 3 4

· 7. Compute (567 / 3) P = 189 P = ∞ . We now have 189
as a candidate for the order of P .

6. Factor 189 = 3 3 7. Compute (189 / 3) P =(38 , 535)

= ∞ and (189 / 7) P =

(136 , 360) = ∞ . Therefore 189 is the order of P .

As pointed out in Example 4.7, this su ces to determine that # E ( F 557 )=
567.