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

It remains to consider the case where x q 2 ,y q 2 = ± q ( x, y ) for all ( x, y ) ∈

E [ ]. If

φ q ( x, y )= x q 2 ,y q 2 = q ( x, y ) ,

then

aφ q ( x, y )= φ q ( x, y )+ q ( x, y )=2 q ( x, y ) ,

hence

a 2 q ( x, y )= a 2 φ q ( x, y )=(2 q ) 2 ( x, y ) .
Therefore, a 2 q ≡ 4 q 2 (mod ), so q is a square mod .If q is not a square
mod , then we cannot be in this case. If q is a square mod ,let w 2 ≡ q

(mod ). We have

( φ q + w )( φ q − w )( x, y )=( φ q − q )( x, y )= ∞

for all ( x, y ) ∈ E [ ]. Let P be any point in E [ ]. Then either ( φ q − w ) P = ∞ ,
so φ q P = wP ,or P =( φ q − w ) P is a finite point with ( φ q + w ) P = ∞ .

Therefore, in either case, there exists a point P ∈ E [ ]with φ q P = ± wP .

Suppose there exists a point P ∈ E [ ] such that φ q P = wP .Then

∞ =( φ q − aφ q + q ) P =( q − aw + q ) P,

2 w 2

so aw ≡ 2 q ≡ (mod ). Therefore, a ≡ 2 w (mod ). Similarly, if there

exists P such that φ q P = 2 w (mod ). We can check

whether we are in this case as follows. We need to know whether or not

− wP ,then a ≡−

( x q ,y q )= ±w ( x, y )= ± ( x w ,y w )=( x w , ±y w )

E [ ]. Therefore, we compute x q for some ( x, y ) ∈ − x w , which is a rational

function of x .If

gcd(numerator( x q

− x w ) ,ψ ) =1 ,

thenthereissome( x, y ) ∈ E [ ] such that φ q ( x, y )= ±w ( x, y ). If this happens,
then use the y -coordinates to determine the sign.
Why do we use the gcd rather than simply checking whether we have 0 mod
ψ ? The gcd checks for the existence of one point. Looking for 0 (mod ψ )
checks if the relation holds for all points simultaneously. The problem is that
we are not guaranteed that φ q P = ±wP for all P ∈ E [ ]. For example,
the matrix representing φ q on E [ ] might not be diagonalizable. It might

be w 1
0 w

.

In this case, the eigenvectors for φ q form a one-dimensional

subspace.
If we have gcd(numerator( x q − x w ) ,ψ ) = 1, then we cannot be in the case

x q 2 ,y q 2 = q ( x, y ), so the only remaining case is x q 2 ,y q 2 =

q ( x, y ). In
this case, aP =( φ q + q ) P = ∞ for all P ∈ E [ ]. Therefore, a ≡ 0(mod ).
We summarize Schoof's algorithm as follows. We start with an elliptic curve
E over F q given by y 2 = x 3 + Ax + B . We want to compute # E ( F q )= q +1 −a .

−