Isogenies - Elliptic Curves: Number Theory and Cryptography - page 396

if this is done for su ciently many , then we obtain a . As described in Section
4.5, the Frobenius acts on the -torsion E [ ]asamatrix
( φ ) = st

.

uv

By Proposition 4.11, a ≡ Trace(( φ ) )and p ≡ det(( φ ) )(mod ). Suppose

there is a basis of E [ ] such that
( φ ) = λb

0 μ

for some integers λ and μ . This means that there is a subgroup C of E [ ]
such that φ ( P )= λP for all P ∈ C .Moreover,

T 2

− aT + p ≡ ( T − λ )( T − μ )(mod ) .

Conversely, if T 2 aT + p has a root λ mod , then there is a subgroup C

such that φ ( P )= λP for all P

−

C (this is the result from linear algebra that
the eigenvalues are the roots of the characteristic polynomial of a matrix).
Let C be a subgroup such that φ q ( P )= λP for all P

∈

C ,sothe q th-power
Frobenius permutes the elements of C . Consider the isogeny with kernel C
constructed in Theorem 12.16. The formula for the isogenous curve E 2 is
symmetric in the coordinates of the points of C .Since φ q permutes these co-
ordinates, it leaves invariant the coecients of equation of E 2 . Consequently,
the j -invariant j 2 of E 2 is fixed by φ q and therefore lies in F q . Similarly, the
monic polynomial whose roots are the x -coordinates of the points in C has
coe cients that lie in F q .Thereare(

∈

− 1) / 2 such coordinates, so we obtain a

polynomial F ( x )ofdegree( 1) / 2. Recall that the th division polynomial

ψ ( x ), whose roots are the x -coordinates of all the points in E [ ], has degree
( 2

−

1) / 2. Therefore, F ( x ) is a factor of ψ ( x )ofdegreemuchsmallerthan
ψ ( x ).
In Schoof's algorithm, the most time-consuming parts are the computations
mod ψ ( x ). The ideas in Section 4.5 allow us to work mod F ( x ) instead, and
find a λ such that φ ( P )= λP for some P = ∞ in C . Since the degree of
F ( x ) is much smaller than the degree of ψ ( x ), the computations proceed
much faster. Since λμ ≡ p (mod ), we have

−

a ≡ Trace(( φ ) ) ≡ λ + p

(mod ) ,

λ

so we obtain a mod .
Finding F ( x ) eciently is rather complicated. See [12] or [99] for details.
Determining whether λ and μ exist is more straightforward and uses the
modular polynomial Φ ( X, Y ) (see Theorem 10.15). Recall that Φ ( X, Y )has
integer coecients. If j 1 ,j 2 ∈ C ,thenΦ ( j 1 ,j 2 ) = 0 if and only there is
an isogeny of degree from an elliptic curve with j -invariant j 1 to one with