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 $\mathbb{\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+6A{x}^2+12Bx-A^2$

${\psi }_4=4y(x^6+5A{x}^4+20B{x}^3-5A^2{x}^2-4ABx-8B^2-A^3)$

$⋮$

${\psi }_{2m+1}={\psi }_{m+2}{\psi }_m^3-{\psi }_{m-1}{\psi }_{m+1}^3\text{ for }m\ge 2$

${\psi }_{2m}=\left(\frac{{\psi }_m}{2y}\right)\cdot ({\psi }_{m+2}{\psi }_{m-1}^2-{\psi }_{m-2}{\psi }_{m+1}^2)\text{ for }m\ge 3$

The polynomial ${\psi }_n$ is called the n^th division polynomial.

Properties

• In practice, one sets $y^2=x^3+Ax+B$, and then ${\psi }_{2m+1}\in \mathbb{\mathbb{Z}}[x,A,B]$ and ${\psi }_{2m}\in 2y\mathbb{\mathbb{Z}}[x,A,B]$.
• The division polynomials form a generic elliptic divisibility sequence over the ring $\mathbb{\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 n^th multiple of $P$ in terms of division polynomials:

$nP=(\frac{{\varphi }_n(x)}{{\psi }_n^2(x)},\frac{{\omega }_n(x,y)}{{\psi }_n^3(x,y)})=(x-\frac{{\psi }_{n-1}{\psi }_{n+1}}{{\psi }_n^2(x)},\frac{{\psi }_{2n}(x,y)}{2{\psi }_n^4(x)})$

where ${\varphi }_n$ and ${\omega }_n$ are defined by:

${\varphi }_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}$, ${\varphi }_n$ are all in $K[x]$.

Let $p>3$ be prime and let $E:y^2=x^3+Ax+B$ be an elliptic curve over the finite field ${\mathbb{𝔽}}_p$, i.e., $A,B\in {\mathbb{𝔽}}_p$. The $\ell$-torsion group of $E$ over ${\overline{\mathbb{𝔽}}}_p$ is isomorphic to $\mathbb{\mathbb{Z}}/\ell \times \mathbb{\mathbb{Z}}/\ell$ if $\ell \ne p$, and to $\mathbb{\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 $\ell$th 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.

See also

• Schoof's algorithm

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{𝔽}}_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.