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 _{{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 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 _{{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) \)
wher \(\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 p>3 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 \( \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 ( F q ) {\displaystyle E(\mathbb {F} _{q})} E(\mathbb {F} _{q}). Available at http://www-math.mit.edu/~musiker/schoof.pdf[permanent dead link]
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.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
