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.

The set of division polynomials is a sequence of polynomials in ${\displaystyle \mathbb {Z} [x,y,A,B]}${\displaystyle \mathbb {Z} [x,y,A,B]} with ${\displaystyle x,y,A,B}${\displaystyle x,y,A,B} free variables that is recursively defined by:

${\displaystyle \psi _{0}=0}${\displaystyle \psi _{0}=0}

${\displaystyle \psi _{1}=1}${\displaystyle \psi _{1}=1}

${\displaystyle \psi _{2}=2y}${\displaystyle \psi _{2}=2y}

${\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2}}${\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2}}

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

${\displaystyle \vdots }${\displaystyle \vdots }

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

${\displaystyle \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\geq 3}${\displaystyle \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\geq 3}

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

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

${\displaystyle nP=\left({\frac {\phi _{n}(x)}{\psi _{n}^{2}(x)}},{\frac {\omega _{n}(x,y)}{\psi _{n}^{3}(x,y)}}\right)=\left(x-{\frac {\psi _{n-1}\psi _{n+1}}{\psi _{n}^{2}(x)}},{\frac {\psi _{2n}(x,y)}{2\psi _{n}^{4}(x)}}\right)}${\displaystyle nP=\left({\frac {\phi _{n}(x)}{\psi _{n}^{2}(x)}},{\frac {\omega _{n}(x,y)}{\psi _{n}^{3}(x,y)}}\right)=\left(x-{\frac {\psi _{n-1}\psi _{n+1}}{\psi _{n}^{2}(x)}},{\frac {\psi _{2n}(x,y)}{2\psi _{n}^{4}(x)}}\right)}

where ${\displaystyle \phi _{n}}${\displaystyle \phi _{n}} and ${\displaystyle \omega _{n}}${\displaystyle \omega _{n}} are defined by:

${\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},}${\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},}

${\displaystyle \omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2}}{4y}}.}${\displaystyle \omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2}}{4y}}.}

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

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

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

• Schoof's algorithm

• 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 ${\displaystyle E(\mathbb {F} _{q})}${\displaystyle 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.

• Polynomials
• Algebraic curves