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 {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 n^th 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 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)}{2\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}}^{{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}}$ and $\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.

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 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. 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.

This article is issued from Wikipedia - version of the 7/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Division polynomials

Definition

Properties

See also

References