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

If q is very large, the polynomial x q has very large degree. Therefore, it is

x q (mod x 3 + Ax + B ) by successive squaring
(cf. Section 2.2), and then use the result to compute

more e cient to compute x q ≡

x, x 3 + Ax + B )=gcd( x q x, x 3 + Ax + B ) . gcd( x q − −

If the gcd is 1, then there is no common root and a is odd. If the gcd is not
1, then a is even. This finishes the case =2.
In the following, various expressions such as x q and x q 2 will be used. They
will always be computed mod a polynomial in a manner similar to that just
done in the case =2
In Section 3.2, we defined the division polynomials ψ n .When n is odd, ψ n
is a polynomial in x and, for ( x, y ) ∈ E ( F q ), we have

( x, y ) ∈ E [ n ] ⇐⇒ ψ n ( x )=0 .

These polynomials play a crucial role in Schoof's algorithm.
Let φ q be the Frobenius endomorphism (not to be confused with the poly-
nomials φ n from Section 3.2, which are not used in this section), so

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

By Theorem 4.10,

φ q − aφ q + q =0 .

Let ( x, y )beapointoforder .Then
x q 2 ,y q 2 + q ( x, y )= a ( x q ,y q ) .

Let

q ≡ q (mod ) , |q | </ 2 .

Then q ( x, y )= q ( x, y ), so
x q 2 ,y q 2 + q ( x, y )= a ( x q ,y q ) .

Since ( x q ,y q ) is also a point of order , this relation determines a mod .The
idea is to compute all the terms except a in this relation, then determine a
value of a that makes the relation hold. Note that if the relation holds for
one point ( x, y ) ∈ E [ ], then we have determined a (mod ); hence, it holds
for all ( x, y ) ∈ E [ ].

Assume first that x q 2 ,y q 2 = ± q ( x, y )forsome( x, y ) ∈ E [ ]. Then

( x ,y ) de = x q 2 ,y q 2 + q ( x, y ) = ∞,