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

point will contribute the correct power of p to the least common multiple of
the orders of the points. If p is small, say p = 2, then the probability is at
least 1/2. This means that if we choose several randomly chosen points, the
least common multiples of their orders should still have the correct power of
p . The conclusion is that if we choose several random points and compute the
least common multiple of their orders, it is very likely that we will obtain n 2 ,
which is as large as possible.
The following result of Cremona and Harley shows that knowledge of n 2
usually determines the group structure.

PROPOSITION 4.19
Let E be an elliptic curve over F q .Wr te E ( F q ) Z n 1 ⊕ Z n 2 with n 1 |n 2 .
Suppose that q is not one of the follow ing:

3 , 4 , 5 , 7 , 9 , 11 , 13 , 17 , 19 , 23 , 25 , 27 , 29 , 31 , 37 ,
43 , 61 , 73 , 181 , 331 , 547 .

Then n 2 uniquelydeterm ines n 1 .

PROOF Fix q and suppose there exist n 2 ,x,y (regard x, y as two possible
values of n 1 )with

1. x, y|n 2
2. √ q 1 2 ≤ √ q +1 2 − ≤ n 2 x<n 2 y

(so the groups of order n 2 x and n 2 y satisfy the bounds in Hasse's theorem).
Our first goal is to show that if n 2 ,x,y satisfying (1) and (2) exist then
q ≤ 4612.
Let d =gcd( x, y ). Then n 2 = dn 2 ,x = x/d, y = y/d also satisfy (1), (2).
So we may assume that gcd( x, y ) = 1. Since n 2 y − n 2 x> 0,

( √ q +1) 2 ( √ q 1) 2 =4 √ q.

n 2 ≤ n 2 y − n 2 x ≤ − −

Since x, y | n 2 ,wehave xy | n 2 , hence xy ≤ n 2 . Therefore,

4 √ q, x 2

≤ xy ≤ n 2 ≤

which implies that

≤ n 2 x ≤ (4 √ q )(4 √ q ) 1 / 2 .
But √ q − 1 2 > 8 q 3 / 4 when q ≥ 4613. Therefore, we must have q ≤ 4612.
The values of q ≤ 4612 can be checked on a computer to get a much smaller
list of possibilities for q .

( √ q − 1) 2

However, we can speed up the search with the

following observations.