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

PROPOSITION 4.18
Let p> 229 be primeand et E be an elliptic curve over F p .E ther E or
its quadratictwist E has a point P w hose order has onlyonemu tipleinthe

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

PROOF Let

E ( F p ) E ( F p ) Z m ⊕ Z M , Z n ⊕ Z N ,

a ,then nN =# E ( F p )= with m | M and n | N .If mM =# E ( F p )= p +1 −

p +1+ a .Since m|M and n|N ,wehave m 2 |p +1 − a and n 2 |p +1+ a .

Therefore, gcd( m 2 ,n 2 ) | 2 a .
Since E [ m ] ⊆ E ( F p ), then μ m ⊆ F p by Corollary 3.11, so p ≡ 1(mod m ).
Therefore, 2 − a ≡ p +1 − a ≡ 0(mod m ). Similarly, 2 + a ≡ 0(mod n ).
Therefore, gcd( m, n ) a )+(2+ a ) = 4, and gcd( m 2 ,n 2 ) | (2 − | 16.

gcd( m 2 ,n 2 ), which divides 2 a .Then8 If 4 | m and 4 | n ,then16 | | a ,whichis

impossible since then 2 0 (mod 4). Therefore,

gcd( m 2 ,n 2 ) | 4. This implies that the least common multiple of m 2

− a ≡ 0(mod m ) implies 2 − 0 ≡

and n 2 is

a multiple of m 2 n 2 / 4.
Let φ be the p th power Frobenius endomorphism for E .Since E [ n ] ⊆
E ( F p ), it follows that φ acts trivially on E [ n ]. Choose a basis for E [ n 2 ]. The
action of φ on E [ n 2 ] is given by a matrix of the form
1+ sn .

tn

un 1+ vn

By Proposition 4.11, we have a ≡ 2+( s + v ) n (mod n 2 )and p ≡ 1+( s + v ) n
(mod n 2 ). Therefore, 4 p 0(mod m 2 ).

It follows that the least common multiple of m 2 and n 2 divides 4 p

a 2 0(mod n 2 ). Similarly, 4 p a 2 − ≡ − ≡

a 2 ,so −

m 2 n 2
4

≤ 4 p − a 2 .

Suppose that both M and N are less than 4 √ p . Then, since a 2 < 4 p ,

1) 2 < ( p +1) 2 a 2 =( p +1 ( p − − − a )( p +1+ a )= mMnN

< 4(4 p a 2 ) 1 / 2 (4 √ p ) 2 64 p 3 / 2 . − ≤

A straightforward calculation shows that this implies that p< 4100. We have
the re fore shown that if p> 4100, then either M or N must be greater th an

4 √ p . This means that either E or E has a point of order greater than 4 √ p .
Therefore, t h ere can be a t most one multiple of this order in the interval

p +1 − 2 √ p, p +1+2 √ p . This proves the theorem for p> 4100.
Suppose now that 457 <p< 4100. A straig ht forward computation shows

that there are no integers a, m, n with |a| < 2 √ p such that