In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.
The set of division polynomials is a sequence of polynomials in
Z
[
x
,
y
,
A
,
B
]
with
x
,
y
,
A
,
B
free variables that is recursively defined by:
The polynomial
ψ
n
is called the nth division polynomial.
In practice, one sets
y
2
=
x
3
+
A
x
+
B
, and then
ψ
2
m
+
1
∈
Z
[
x
,
A
,
B
]
and
ψ
2
m
∈
2
y
Z
[
x
,
A
,
B
]
.
The division polynomials form a generic elliptic divisibility sequence over the ring
Q
[
x
,
y
,
A
,
B
]
/
(
y
2
−
x
3
−
A
x
−
B
)
.
If an elliptic curve
E
is given in the Weierstrass form
y
2
=
x
3
+
A
x
+
B
over some field
K
, i.e.
A
,
B
∈
K
, one can use these values of
A
,
B
and consider the division polynomials in the coordinate ring of
E
. The roots of
ψ
2
n
+
1
are the
x
-coordinates of the points of
E
[
2
n
+
1
]
∖
{
O
}
, where
E
[
2
n
+
1
]
is the
(
2
n
+
1
)
th
torsion subgroup of
E
. Similarly, the roots of
ψ
2
n
/
y
are the
x
-coordinates of the points of
E
[
2
n
]
∖
E
[
2
]
.
Given a point
P
=
(
x
P
,
y
P
)
on the elliptic curve
E
:
y
2
=
x
3
+
A
x
+
B
over some field
K
, we can express the coordinates of the nth multiple of
P
in terms of division polynomials:
where
ϕ
n
and
ω
n
are defined by:
ϕ
n
=
x
ψ
n
2
−
ψ
n
+
1
ψ
n
−
1
,
ω
n
=
ψ
n
+
2
ψ
n
−
1
2
−
ψ
n
−
2
ψ
n
+
1
2
4
y
.
Using the relation between
ψ
2
m
and
ψ
2
m
+
1
, along with the equation of the curve, the functions
ψ
n
2
,
ψ
2
n
y
,
ψ
2
n
+
1
and
ϕ
n
are all in
K
[
x
]
.
Let
p
>
3
be prime and let
E
:
y
2
=
x
3
+
A
x
+
B
be an elliptic curve over the finite field
F
p
, i.e.,
A
,
B
∈
F
p
. The
ℓ
-torsion group of
E
over
F
¯
p
is isomorphic to
Z
/
ℓ
×
Z
/
ℓ
if
ℓ
≠
p
, and to
Z
/
ℓ
or
{
0
}
if
ℓ
=
p
. Hence the degree of
ψ
ℓ
is equal to either
1
2
(
l
2
−
1
)
,
1
2
(
l
−
1
)
, or 0.
René Schoof observed that working modulo the
ℓ
th division polynomial allows one to work with all
ℓ
-torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.
