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

1. m 2 | p +1 − a

2. n 2 |p +1+ a

3. ( p +1 − a ) /m < 4 √ p
4. ( p +1+ a ) /n < 4 √ p .

Therefore, the theorem is true for p> 457.
For p = 457, we may take a = 10, m =8, n = 6, which correspond
to the groups Z 8 ⊕ Z 56 and Z 6 ⊕ Z 78 (and can be realized by the curves
E : y 2 = x 3 − 125 and its quadratic twist E : y 2 = x 3 − 1) . Note, howev er, t hat

the only multiple of 56 in the interval 457 + 1 − 2 √ 457 , 457+1+2 √ 457 =
(415 . 2 , 500 . 8) is 448, which is the order of E ( F 457 ). Similarly, the only mul-
tiple of 78 in this interval is 468, which is the order of E ( F 457 ). Therefore,
the theorem still holds in this case.
In fact, the search for a, m, n can be extended in this way to 229 <p≤ 457,
with conditions (3) and (4) replaced by

3'. there is mor e than one m u ltiple of ( p +1 − a ) /m in the interval

p +1 − 2 √ p, p +1+2 √ p

4'. there is mor e than one m u ltiple of ( p +1+ a ) /m in the interval

p +1 − 2 √ p, p +1+2 √ p .

No values of a, m, n exist satisfying these conditions, so the theorem holds.

Example 4.10
The theorem is false for p = 229.

Consider the curve E : y 2 = x 3

− 1.

A calculation shows that E ( F 229 ) for

all P ∈ E ( F 229 ). The Hasse bound says that 200 ≤ # E ( F 229 ) ≤ 260, so the
existence of a point of order 42 allows both the values 210 and 252. Since 2 is a
quadratic nonresidue mod 229, the curve E : y 2 = x 3

Z 6 ⊕ Z 42 . Therefore, 42 P = ∞

− 8isthequadratictwist
of E . A calculation shows that E ( F 229 ) Z 4 ⊕ Z 52 . Therefore, 52 P = ∞
for all P ∈ E ( F 229 ). The existence of a point of order 52 allows both the
values 208 and 260. Therefore, neither E nor its quadratic twist E has a

point whose order has only one multiple in the Hasse interval.

n 2 . Then the order of every element
divides n 2 . If we choose some random points and compute their orders, what
is the chance that the least common multiple of these orders is n 2 ?Let P 1 ,P 2
be points of orders n 1 ,n 2 such that every P ∈ E ( F q ) is uniquely expressible in
the form P = a 1 P 1 + a 2 P 2 with 0 ≤ a i <n i .Let p be a prime dividing n 2 .If
we take a random point P , then the probability is 1 − 1 /p that p a 2 .If p a 2 ,
then the order of P contains the highest power of p possible. If p is large,
then this means that it is very likely that the order of one randomly chosen

Suppose E ( F q ) Z n 1 ⊕ Z n 2 with n 1 |