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

In order to study the torsion subgroups, we need to describe the map on
an elliptic curve given by multiplication by an integer. As in Section 2.9, this
is an endomorphism of the elliptic curve and can be described by rational
functions. We shall give formulas for these functions.
We start with variables A, B . Define the division polynomials ψ m ∈

Z [ x, y, A, B ]by

ψ 0 =0
ψ 1 =1
ψ 2 =2 y
ψ 3 =3 x 4 +6 Ax 2 +12 Bx − A 2
ψ 4 =4 y ( x 6 +5 Ax 4 +20 Bx 3 5 A 2 x 2 8 B 2 A 3 ) − − 4 ABx − −

ψ 2 m +1 = ψ m +2 ψ 3 m − ψ m− 1 ψ 3 m +1 for m ≥ 2

ψ 2 m =(2 y ) − 1 ( ψ m )( ψ m +2 ψ 2 m− 1 − ψ m− 2 ψ 2 m +1 )for m

≥ 3 .

LEMMA 3.3
ψ n isapo ynom ial in Z [ x, y 2 ,A,B ] when n is odd, and ψ n isapo ynom ial
in 2 y Z [ x, y 2 ,A,B ] when n is even.

PROOF The lemma is true for n ≤ 4. Assume, by induction, that it holds
for all n< 2 m . We may assume that 2 m> 4, so m> 2. Then 2 m>m +2,
so all polynomials appearing in the definition of ψ 2 m satisfy the induction
assumptions. If m is even, then ψ m ,ψ m +2 ,ψ m− 2 are in 2 y Z [ x, y 2 ,A,B ], from
which it follows that ψ 2 m is in 2 y Z [ x, y 2 ,A,B ]. If m is odd, then ψ m− 1 and
ψ m +1 are in 2 y Z [ x, y 2 ,A,B ], so again we find that ψ 2 m is in 2 y Z [ x, y 2 ,A,B ].
Therefore, the lemma holds for n =2 m . Similarly, it holds for n =2 m +1.

Define polynomials

φ m = xψ 2 m − ψ m +1 ψ m− 1

ω m =(4 y ) − 1 ( ψ m +2 ψ 2 m− 1 − ψ m− 2 ψ 2 m +1 ) .

LEMMA 3.4
φ n ∈ Z [ x, y 2 ,A,B ] for all n .If n is odd, then ω n ∈ y Z [ x, y 2 ,A,B ] .If n is
even, then ω n ∈ Z [ x, y 2 ,A,B ] .

PROOF If n is odd, then ψ n +1 and ψ n− 1 are in y Z [ x, y 2 ,A,B ], so their
product is in Z [ x, y 2 ,A,B ]. Therefore, φ n ∈ Z [ x, y 2 ,A,B ]. If n is even, the
proof is similar.
The facts that y − 1 ω n ∈ Z [ x, y 2 ,A,B ]forodd n and ω n ∈

1

2 Z [ x, y 2 ,A,B ]
for even n follow from Lemma 3.3, and these are all that we need for future