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 with free variables that is recursively defined by:
The polynomial is called the nth 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 nth multiple of in terms of division polynomials:
- where and are defined by:
Using the relation between and , along with the equation of the curve, the functions , and are all in .
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.
- A. Brown: Algorithms for Elliptic Curves over Finite Fields, EPFL — LMA. Available at http://algo.epfl.ch/handouts/en/andrew.pdf
- A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
- N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994
- Müller : Die Berechnung der Punktanzahl von elliptischen kurvenüber endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991.
- G. Musiker: Schoof's Algorithm for Counting Points on . Available at http://www-math.mit.edu/~musiker/schoof.pdf
- Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available at http://www.mat.uniroma2.it/~schoof/ctpts.pdf
- R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
- L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.
- J. Silverman: The Arithmetic of Elliptic Curves, Springer-Verlag, GTM 106, 1986.