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

4.4 A Family of Curves

In this section we give an explicit formula for the number of points in E ( F p ),
where E is the elliptic curve

y 2 = x 3 − kx,

and k ≡ 0(mod p ). Counting the points on this curve mod a prime p has a
long history, going back at least to Gauss.

THEOREM 4.23
Let p be an odd primeand et k ≡ 0(mod p ) .Let N p =# E ( F p ) ,where E
isthe ellipticcurve

y 2 = x 3

− kx.

1. If p ≡ 3(mod4) ,then N p = p +1 .

2. If p ≡ 1(mod4) ,write p = a 2 + b 2 ,where a, b are integers w ith b even
and a + b ≡ 1(mod4) .Then

⎧
⎨

p +1 2 a if k isafourthpowermod p

p +1+2 a if k isasquaremod p but not a 4thpowermod p
p +1 ± 2 b if k is not a square m od p.

−

N p =

⎩

The proof of the theorem will take the rest of this section.
The integer a is uniquely determined by the conditions in the theorem, and
b is uniquely determined up to sign. When k is not a square mod p , the proof
below does not determine the sign of b . This is a much more delicate problem
and we omit it.

Example 4.12
Let p =61=( 5) 2 +6 2 , where we chose the negative sign on 5 so that −

− 5+6 ≡ 1 (mod 4). Since k = 1 is a fourth power, the number of points on

y 2 = x 3 − x is p +1 − 2( − 5) = 72.

It is well known that every prime p ≡ 1 (mod 4) is a sum of two squares
(this follows from Proposition 4.27 below). The next lemma shows that a and
b are uniquely determined up to order and sign.

LEMMA 4.24
Suppose p isprimeand a, b, c, d are integers such that a 2 + b 2 = p = c 2 + d 2 .
Then a = ±c and b = ±d ,or a = ±d and b = ±c .