Division polynomials

Division Polynomials

Division Polynomials play a central role in the study of Counting Points on Elliptic Curves.

Definition

We define recursively a sequence of polynomials in ${Z}[x,y,A,B]$, with $x,y,A,B$ free variables:

$\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 _{m+1}^{3}{\text{ for }}m\geq 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\geq 3$

\

The polynomial $\psi _{n}$ is called the n^th Division Polynomial.

Properties

• $\psi _{2n+1}$ is a polynomial in ${Z}[x,y^{2},A,B]$, while $\psi _{2m}$ is a polynomial in $2y{Z}[x,y^{2},A,B]$.

• If an elliptic curve $E$ is given in the Weierstrass form $y^{2}=x^{3}+Ax+B$ then the powers of $y$ can only be less or equal to 1, as it is possible to replace $y^{2}$ by $x^{3}+Ax+B$. The roots of the $(2n+1)^{\text{th}}$ division polynomial $\psi _{2n+1}$ are exactly 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 the group $E$ of an elliptic curve.

• Given a point $P=(x_{P},y_{P})$ on the elliptic curve $E:y^{2}=x^{3}+Ax+B$, we can express the coordinates of the n^th multiple of $P$ in terms of division polynomials:

$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)}{\psi _{n}^{4}(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}}{4y}}$

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

This is the fact that enabled Schoof to make use of division polynomials to devise an efficient point counting algorithm.

See Also

• Schoof's Algorithm
• Counting Points on Elliptic Curves

References

• A. Brown: Algorithms for Elliptic Curves over Finite Fields, EPFL - LMA. Avaliable 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 $E(\mathbb {F} _{q})$. Avaliable 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. Avaliable 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. Avaliable 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.