Division polynomials

In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves over Finite fields. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.

Definition

The division polynomials are a sequence of polynomials in $\mathbb{Z}[x,y,A,B]$ with x,y,A,B free variables that is recursively defined by:

ψ₀ = 0

ψ₁ = 1

ψ₂ = 2y

ψ₃ = 3x⁴ + 6Ax² + 12Bx − A²

ψ₄ = 4y(x⁶ + 5Ax⁴ + 20Bx³ − 5A²x² − 4ABx − 8B² − A³)

$\vdots$

$\psi_{2m+1} = \psi_{m+2} \psi_{m}^{ 3} - \psi_{m-1} \psi ^{ 3}_{ m+1} \text{ for } m \geq 2$

$\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$

The polynomial ψ_n is called the n^th division polynomial.

Properties

• ψ_{2n + 1} is a polynomial in Z[x,y²,A,B], while ψ_2m is a polynomial in 2yZ[x,y²,A,B].
• The division polynomials form an elliptic divisibility sequence. Moreover all nonsingular elliptic divisibility sequences arise this way.
• If an elliptic curve E is given in the Weierstrass form y² = x³ + Ax + B over some field K, i.e. $A, B\in K$ one can evaluate the division polynomials at those A,B and consider them as polynomials in the coordinate ring. Then the powers of y can only be less or equal to 1, as y² is replaced by x³ + Ax + B. In particular, ψ_{2n + 1} is a univariate polynomial in x only. The roots of the (2n + 1)^th division polynomial ψ_{2n + 1} are exactly the x coordinates of the points of $E[2n+1]\setminus \{O\}$, where E[2n + 1] is the (2n + 1)^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² = x³ + 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^{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)$

where ϕ_n and ω_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 ψ_2m and ψ_{2m + 1}, along with the equation of the curve, we have that $\psi_{n}^{2}$ , $\frac{\psi_{2n}}{y}, \psi_{2n + 1}$ and ϕ_n are all functions in the variable x.

Let p > 3 be prime and let $E:y^2=x^3+Ax+B, A,B \in \mathbb{F}_p$ be an elliptic curve over the finite field $\in \mathbb{F}_p$. The l-torsion group of E over $\bar{ \mathbb{F}}_p$ is isomorphic to $\mathbb{Z}/l \times \mathbb{Z}/l$ if $l\neq p$ and to $\mathbb{Z}/l$ of {0} otherwise which means that the degree of ψ_l is (l² − 1) / 2, (l − 1) / 2 or 0.

René Schoof observed that working modulo the lth division polynomial means working with all l-torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.

See also

• Schoof's algorithm

References

• A. Brown: Algorithms for Elliptic Curves over Finite Fields, EPFL — LMA. Available 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)$. 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.