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

with λ = 3, hence to the curve y 2 = x ( x 3). The next three factors

correspond to j = 1728, hence to the curve y 2 = x 3 + x . The last factor
corresponds to j = 0, hence to y 2 = x 3 + 1. Therefore, we have found the
three supersingular curves over F 23 . Of course, over F 23 , there are different
forms of these curves. For example, y 2 = x 3 +1 a nd y 2 = x 3 + 2 are different
curves over F 23 , but are the same over F 23 .

− 1)( x −

Example 4.15
When p = 13,

H 13 ( T ) ≡ ( T 2 +4 T +9)( T 2 +12 T +3)( T 2 +7 T +1) .
Thesixrootscorrespondtoonevalueof j .Since λ = − 2+ √ 8 is a root of
the first factor, the corresponding elliptic curve is
y 2 = x ( x − 1)( x +2 − √ 8) .

The appearance of a square root such as √ 8 is fairly common. It is possible
to show that a supersingular curve over a perfect field of characteristic p
must have its j -invariant in F p 2 ( see [109, Theorem V.3.1]). Therefore, a
supersingular elli pti c curve over F q can always be transformed via a change
of variables (over F q ) into a curve defined over F p 2 .

Exercises

4.1 Let E be the elliptic curve y 2 = x 3 + x +1 (mod 5).

(a) Show that 3(0 , 1) = (2 , 1) on E .

(b) Show that (0 , 1) generates E ( F 5 ). (Use the fact that E ( F 5 )has
order 9 (see Example 4.1), plus the fact that the order of any
element of a group divides the order of the group.)

4.2 Let E be the elliptic curve y 2 + y = x 3 over F 2 . Show that
# E ( F 2 n )= 2 n +1 if n is odd

2 n +1 − 2( − 2) n/ 2

if n is even.

4.3 Let F q be a finite field with q odd. Since F q is cyclic of even order q− 1,
half of the elements of F q are squares and half are nonsquares.