Cryptography Reference
In-Depth Information
2 m .
Therefore, if m is fixed, q occurs as the value of one of finitely many
quadratic polynomials.
(b) Use Hasse's theorem in the form a 2
4 q to show that
|
k
|≤
(c) The prime number theorem implies that the number of prime pow-
ers less than x is approximately x/ ln x . Use this to show that most
prime powers do not occur as values of the finite list of polynomials
in (b).
(d) Use Hasse's theorem to show that mn ≥ m ( q − 1).
(e) Show that if m
17 and q is su ciently large ( q
1122 su ces),
then E ( F q ) has a point of order greater than 4 q .
(f) Show that for most value s of q , an elliptic curve over F q has a point
of order greater than 4 q .
(a) Let E be defined by y 2 + y = x 3 + x over F 2 . Show that # E ( F 2 )=
5.
(b) Let E be defined by y 2 = x 3
4.7
x +2 over F 3 . Show that # E ( F 3 )=1.
(c) Show that the curves in (a) and (b) are supersingular, but that, in
each case, a = p +1
# E ( F p )
= 0. This shows that the restriction
to p
5 is needed in Corollary 4.32.
4.8 Let p
5 be prime. Use Theorem 4.23 to prove Hasse's theorem for the
elliptic curve given by y 2 = x 3
kx over F p .
4.9 Let E be a n elliptic curve over F q with q = p 2 m . Suppose that # E ( F q )=
q +1
2 q .
p m ) 2 =0.
(a) Let φ q be the Frobenius endomorphism. Show that ( φ q
(b) Show that φ q − p m =0( Hint: Theorem 2.22).
(c) Show that φ q acts as the identity on E [ p m
1], and therefore that
E [ p m
E ( F q ).
(d) Show that E ( F q ) Z p m 1 Z p m 1 .
1]
4.10 Let E be an elliptic curve over F q with q odd. Write # E ( F q )= q +1 −a .
Let d ∈ F q
and let E ( d )
be the twist of E , as in Exercise 2.23. Show
that
d
F q
a.
# E ( d ) ( F q )= q +1
( Hint: Use Exercise 2.23(c) and Theorem 4.14.)
4.11 Let F q be a finite field of odd characteristic and let a, b
F q with
a
=
±
2 b and b
= 0. Define the elliptic curve E by
y 2 = x 3 + ax 2 + b 2 x.
 
Search WWH ::




Custom Search