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 [math]\displaystyle{ \mathbb{Z}[x,y,A,B] }[/math] with [math]\displaystyle{ x, y, A, B }[/math] free variables that is recursively defined by:

[math]\displaystyle{ \psi_{0} = 0 }[/math]

[math]\displaystyle{ \psi_{1} = 1 }[/math]

[math]\displaystyle{ \psi_{2} = 2y }[/math]

[math]\displaystyle{ \psi_{3} = 3x^{4} + 6Ax^{2} + 12Bx - A^{2} }[/math]

[math]\displaystyle{ \psi_{4} = 4y(x^{6} + 5Ax^{4} + 20Bx^{3} - 5A^{2}x^{2} - 4ABx - 8B^{2} - A^{3}) }[/math]

[math]\displaystyle{ \vdots }[/math]

[math]\displaystyle{ \psi_{2m+1} = \psi_{m+2} \psi_{m}^{ 3} - \psi_{m-1} \psi ^{ 3}_{ m+1} \text{ for } m \geq 2 }[/math]

[math]\displaystyle{ \psi_{ 2m} = \left ( \frac { \psi_{m}}{2y} \right ) \cdot ( \psi_{m+2}\psi^{ 2}_{m-1} - \psi_{m-2} \psi ^{ 2}_{m+1}) \text{ for } m \geq 3 }[/math]

The polynomial [math]\displaystyle{ \psi_n }[/math] is called the n^th division polynomial.

Properties

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

[math]\displaystyle{ nP= \left ( \frac{\phi_{n}(x)}{\psi_{n}^{2}(x)}, \frac{\omega_{n}(x,y)}{\psi^{3}_{n}(x,y)} \right) = \left( x - \frac {\psi_{n-1} \psi_{n+1}}{\psi^{2}_{n}(x)}, \frac{\psi_{2 n}(x,y)}{2\psi^{4}_{n}(x)} \right) }[/math]

where [math]\displaystyle{ \phi_{n} }[/math] and [math]\displaystyle{ \omega_{n} }[/math] are defined by:

[math]\displaystyle{ \phi_{n}=x\psi_{n}^{2} - \psi_{n+1}\psi_{n-1}, }[/math]

[math]\displaystyle{ \omega_{n}=\frac{\psi_{n+2}\psi_{n-1}^{2}-\psi_{n-2}\psi_{n+1}^{2}}{4y}. }[/math]

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

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

René Schoof observed that working modulo the [math]\displaystyle{ \ell }[/math]th division polynomial allows one to work with all [math]\displaystyle{ \ell }[/math]-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 [math]\displaystyle{ E(\mathbb{F}_q) }[/math]. 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.