Division polynomials

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.

Definition

The set of division polynomials is a sequence of polynomials in with free variables that is recursively defined by:

The polynomial is called the n^th division polynomial.

In practice, one sets, and then and.
The division polynomials form a generic elliptic divisibility sequence over the ring.
If an elliptic curve is given in the Weierstrass form over some field, i.e., one can use these values of and consider the division polynomials in the coordinate ring of. The roots of are the -coordinates of the points of, where is the torsion subgroup of. Similarly, the roots of are the -coordinates of the points of.
Given a point on the elliptic curve over some field, we can express the coordinates of the n^th multiple of in terms of division polynomials:

Using the relation between and, along with the equation of the curve, the functions ,, are all in.
Let be prime and let be an elliptic curve over the finite field, i.e.,. The -torsion group of over is isomorphic to if, and to or if. Hence the degree of is equal to either,, 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.