Torsion Points - Elliptic Curves: Number Theory and Cryptography - page 83

Subtracting and using the recursion relation shows that the leading term of
ψ 2 m +1 is as claimed in the lemma. The other cases are treated similarly.

We can now state the main theorem.

THEOREM 3.6
Let P =( x, y ) be a pointon the ellipticcurve y 2 = x 3 + Ax + B (over som e
field of characteristic not 2), and let n be a positive integer. T hen
nP = φ n ( x )

ψ n ( x, y ) 3 .

ω n ( x, y )

ψ n ( x ) ,

The proof will be given in Section 9.5.

COROLLARY 3.7
Let E be an elliptic curve. T he endom orphism of E given by m ultiplication

by n has degree n 2 .

PROOF From Lemma 3.5, we have that the maximum of the degrees of
the numerator and denominator of φ n ( x ) /ψ n ( x )is n 2 . Therefore, the degree
of the endomorphism is n 2 if this rational function is reduced, that is, if φ n ( x )
and ψ n ( x ) have no common roots. We'll show that this is the case. Suppose
not. Let n be the smallest index for which they have a common root.
Suppose n =2 m is even. A quick calculation shows that

φ 2 ( x )= x 4 2 Ax 2 8 Bx + A 2 . − −

Computing the x -coordinate of 2 m ( x, y ) in two steps by multiplying by m
and then by 2, and using the fact that

ψ 2 =4 y 2 =4( x 3 + Ax + B ) ,

we obtain

φ 2 ( φ m /ψ 2 m )
ψ 2 ( φ m /ψ 2 m )

φ 2 m
ψ 2 m

=

φ 4 m − 8 Bφ m ψ 6 m + A 2 ψ 8 m

(4 ψ 2 m )( φ 3 m + Aφ m ψ 4 m + Bψ 6 m )

2 Aφ 2 m ψ 4 m −

=

U
V ,

=

where U and V are the numerator and denominator of the preceding expres-
sion. To show U and V have no common roots, we need the following.