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

(a) Let u ∈ F q . Show that

x + u
F q

=0 .

x ∈ F q

(b) Let f ( x )=( x − r ) 2 ( x − s ), where r, s ∈ F q with q odd. Show that

f ( x )
F q

= − r .

− s

F q

x ∈ F q

( Hint: If x = r ,then( x − r ) 2 ( x − s ) is a square exactly when x − s
is a square.)

4.4 Let x ∈ F q with q odd. Show that
x
F q

= x ( q− 1) / 2

as elements of F q . Remark: Since the exponentiation on the right
can be done quickly, for example, by successive squaring (this is the
multiplicative version of the successive doubling in Section 2.2), this
shows that the generalized Legendre symbol can be calculated quickly.
Of course, the classical Legendre symbol can also be calculated quickly
using quadratic reciprocity.)

4.5 Let p ≡ 1 (mod 4) be prime and let E be given by y 2 = x 3 − kx ,where

k ≡ 0(mod p ).

(a) Use Theorem 4.23 to show that # E ( F p ) is a multiple of 4 when k
is a square mod p .
(b) Show that when k is a square mod p ,then E ( F p ) contains 4 points
P satisfying 2 P = ∞ . Conclude again that # E ( F p ) is a multiple
of 4.
(c) Show that when k is not a square mod p ,then E ( F p )containsno
points of order 4.
(d) Let k be a square but not a fourth power mod p . Show that exactly
one of the curves y 2 = x 3 x and y 2 = x 3

− − kx has a point of order

4 defined over F p .

4.6 Let E be an elliptic curve over F q and suppose

E ( F q ) Z n ⊕ Z mn .

(a) Use the techniques of the proof of Proposition 4.16 to show that
q = mn 2 + kn + 1 for some integer k .