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

Therefore, x + y 1 (mod 4). It follows that y is

even. This proves (1). The proofs of (2) and (3) are similar.

≡ 1(mod4)and x − y ≡

If k is a fourth power mod p ,then χ 4 ( k )=1,so α ≡ 1(mod2+2 i ). The
lemma yields α = a + bi with b even and a + b ≡ 1(mod4). Thisproves
part of part (2) of Theorem 4.23. The other parts are proved similarly. This
completes the proof of Theorem 4.23.

4.5 Schoof's Algorithm

In 1985, Schoof [97] published an algorithm for computing the number
of points on elliptic curves over finite fields F q that runs much faster than
existing algorithms, at least for very large q . In particular, it requires at
most a constant times log 8 q bit operations, in contrast to the q 1 / 4 used in
Baby Step, Giant Step, for example. Subsequently, Atkin and Elkies refined
and improved Schoof's method (see Section 12.4). It has now been used
successfully when q has several hundred decimal digits. In the following, we'll
give Schoof's method. For details of the method of Atkins and Elkies, see [12]
and [99]. For other methods for counting points, see [60] and [94].
Suppose E is an elliptic curve given by y 2 = x 3 + Ax + B over F q .We

know, by Hasse's theorem, that

2 √ q. # E ( F q )= q +1 − a, with | a |≤

Let S = { 2 , 3 , 5 , 7 ,...,L} be a set of primes such that

> 4 √ q.

∈ S

If we can determine a mod for each prime ∈ S , then we know a mod ,
and therefore a is uniquely determined.
Let be prime. For simplicity, we assume = p ,where p is the characteristic
of F q . We also assume that q is odd. We want to compute a (mod ).
If =2,thisiseasy. If x 3 + Ax + B has a root e ∈ F q ,then( e, 0) ∈ E [2]

and ( e, 0) 0

(mod 2), so a is even. If x 3 + Ax + B has no roots in F q ,then E ( F q )hasno
points of order 2, and a is odd. To determine whether x 3 + Ax + B has a root
in F q , we could try all the elements in F q , but there is a faster way. Recall
(see Appendix C) that the roots of x q

∈ E ( F q ), so E ( F q ) has even order. In this case, q +1 − a ≡

− x are exactly the elements of F q .
Therefore, x 3 + Ax + B has a root in F q if and only if it has a root in common
with x q − x . The Euclidean algorithm, applied to polynomials, yields the gcd

of the two polynomials.