Division Polynomial

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 ,y,A,B/math> with $x, y, A, B$ free variables that is recursively defined by:

::$\psi_ = 0$

::$\psi_ = 1$

::$\psi_ = 2y$

::$\psi_ = 3x^ + 6Ax^ + 12Bx - A^$

::$\psi_ = 4y(x^ + 5Ax^ + 20Bx^ - 5A^x^ - 4ABx - 8B^ - A^)$

::$\vdots$

::$\psi_ = \psi_ \psi_^ - \psi_ \psi ^_ \text m \geq 2$

::$\psi_ = \left ( \frac \right ) \cdot ( \psi_\psi^_ - \psi_ \psi ^_) \text 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_\in\mathbb ,A,B/math> and \psi_\in 2y\mathbb ,A,B/math>.
* The division polynomials form a generic elliptic divisibility sequence over the ring \mathbb ,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_$ are the $x$-coordinates of the points of $E$n+1setminus \, where $E$n+1/math> is the $(2n+1)^$ torsion subgroup of $E$. Similarly, the roots of $\psi_/y$ are the $x$-coordinates of the points of E nsetminus E /math>.
*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, \frac \right) = \left( x - \frac , \frac \right)$
: where $\phi_$ and $\omega_$ are defined by:
::$\phi_=x\psi_^ - \psi_\psi_,$
::$\omega_=\frac.$

Using the relation between $\psi_$ and $\psi _$, along with the equation of the curve, the functions $\psi_^$ , $\frac, \psi_$, $\phi_$ are all in K /math>.

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 $\bar_p$ is isomorphic to $\mathbb/\ell \times \mathbb/\ell$ if $\ell\neq p$, and to $\mathbb/\ell$ or $\$ if $\ell=p$. Hence the degree of $\psi_\ell$ is equal to either $\frac(l^2-1)$, $\frac(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 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.

{{Algebraic curves navbox

Polynomials
Algebraic curves