# 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.

## Properties

- 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:

- where and are defined by:

Using the relation between and , along with the equation of the curve, the functions , and 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.

## See also

## References

- 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.