Division polynomials

Quality 0.50 · 2 views · Updated 2 months ago

title: "Division polynomials" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["polynomials", "algebraic-curves"] topic_path: "general/polynomials" source: "https://en.wikipedia.org/wiki/Division_polynomials" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

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 \mathbb{Z}[x,y,A,B] with x, y, A, B free variables that is recursively defined by:

::\psi_{0} = 0

::\psi_{1} = 1

::\psi_{2} = 2y

::\psi_{3} = 3x^{4} + 6Ax^{2} + 12Bx - A^{2}

::\psi_{4} = 4y(x^{6} + 5Ax^{4} + 20Bx^{3} - 5A^{2}x^{2} - 4ABx - 8B^{2} - A^{3})

::\vdots

::\psi_{2m+1} = \psi_{m+2} \psi_{m}^{ 3} - \psi_{m-1} \psi ^{ 3}_{ m+1} \text{ for } m \geq 2

::\psi_{ 2m} = \left ( \frac { \psi_{m}}{2y} \right ) \cdot ( \psi_{m+2}\psi^{ 2}{m-1} - \psi{m-2} \psi ^{ 2}_{m+1}) \text{ for } m \geq 3

The polynomial \psi_n is called the nth division polynomial.

Properties

  • In practice, one sets y^2=x^3+Ax+B, and then \psi_{2m+1}\in\mathbb{Z}[x,A,B] and \psi_{2m}\in 2y\mathbb{Z}[x,A,B].
  • The division polynomials form a generic elliptic divisibility sequence over the ring \mathbb{Q}[x,y,A,B]/(y^2-x^3-Ax-B).
  • If an elliptic curve E is given in the Weierstrass form y^2=x^3+Ax+B over some field K, i.e. A, B\in K, one can use these values of A, B and consider the division polynomials in the coordinate ring of E. The roots of \psi_{2n+1} are the x-coordinates of the points of E[2n+1]\setminus {O}, where E[2n+1] is the (2n+1)^{\text{th}} torsion subgroup of E. Similarly, the roots of \psi_{2n}/y are the x-coordinates of the points of E[2n]\setminus E[2].
  • Given a point P=(x_P,y_P) on the elliptic curve E:y^2=x^3+Ax+B over some field K, we can express the coordinates of the nth multiple of P in terms of division polynomials: ::nP= \left ( \frac{\phi_{n}(x)}{\psi_{n}^{2}(x)}, \frac{\omega_{n}(x,y)}{\psi^{3}{n}(x,y)} \right) = \left( x - \frac {\psi{n-1} \psi_{n+1}}{\psi^{2}{n}(x)}, \frac{\psi{2 n}(x,y)}{2\psi^{4}{n}(x)} \right) : where \phi{n} and \omega_{n} are defined by: ::\phi_{n}=x\psi_{n}^{2} - \psi_{n+1}\psi_{n-1}, ::\omega_{n}=\frac{\psi_{n+2}\psi_{n-1}^{2}-\psi_{n-2}\psi_{n+1}^{2}}{4y}.

Using the relation between \psi_{2m} and \psi {2m + 1}, along with the equation of the curve, the functions \psi{n}^{2} , \frac{\psi_{2n}}{y}, \psi_{2n + 1}, \phi_{n} are all in K[x].

Let p3 be prime and let E:y^2=x^3+Ax+B be an elliptic curve over the finite field \mathbb{F}_p, i.e., A,B \in \mathbb{F}_p. The \ell-torsion group of E over \bar{ \mathbb{F}}p is isomorphic to \mathbb{Z}/\ell \times \mathbb{Z}/\ell if \ell\neq p, and to \mathbb{Z}/\ell or {0} if \ell=p. Hence the degree of \psi\ell is equal to either \frac{1}{2}(l^2-1), \frac{1}{2}(l-1), or 0.

René Schoof observed that working modulo the \ellth division polynomial allows one to work with all \ell-torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.

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 E(\mathbb{F}_q). Available at https://www-users.cse.umn.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.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

polynomialsalgebraic-curves