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 nth division polynomial.

Properties

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.