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

This can be generalized to any finite field F q with q odd by defining, for
x ∈ F q ,

⎨

x
F q

=

+1 if t 2 = x has a solution t F q ,

− 1if t 2 = x has no solution t ∈ F q ,
0if x =0 .

∈

⎩

THEOREM 4.14
Let E be an elliptic curve defined by y 2 = x 3 + Ax + B over F q .Then

x 3 + Ax + B
F q

.

# E ( F q )= q +1+
x ∈ F q

PROOF For a given x 0 , there are two points ( x, y )with x -coordinate x 0
if x 0 + Ax 0 + B is a nonzero square in F q , one such point if it is zero, and no
points if it is not a square. Therefore, the number of points with x -coordinate

x 0 equals 1 + x 0 + Ax 0 + B

. Summing over all x 0 ∈ F q , and including 1 for

F q

the point ∞ , yields

1+ x 3 + Ax + B
F q

.

# E ( F q )=1+
x ∈ F q

Collecting the term 1 from each of the q summands yields the desired formula.

COROLLARY 4.15
Let x 3 + Ax + B be a polynom ialw ith A, B

∈ F q ,where q is odd. T hen

x 3 + Ax + B
F q

≤ 2 √ q.

x ∈ F q

PROOF When x 3 + Ax + B has no repeated roots, y 2 = x 3 + Ax + B gives
an elliptic curve, so Theorem 4.14 says that

x 3 + Ax + B
F q

.

q +1 − # E ( F q )= −

x ∈ F q

The result now follows from Hasse's theorem.
Thecasewhere x 3 + Ax + B has repeated roots follows from Exercise 4.3.