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

ψ_{0} = 0

ψ_{1} = 1

ψ_{2} = 2 y

ψ_{3} = 3 x^{4} + 6 A x^{2} + 12 B x - A^{2}

ψ_{4} = 4 y (x^{6} + 5 A x^{4} + 20 B x^{3} - 5 A^{2} x^{2} - 4 A B x - 8 B^{2} - A^{3})

⋮

ψ_{2 m + 1} = ψ_{m + 2} ψ_{m}^{3} - ψ_{m - 1} ψ_{m + 1}^{3} for m \geq 2

ψ_{2 m} = (\frac{ψ_{m}}{2 y}) \cdot (ψ_{m + 2} ψ_{m - 1}^{2} - ψ_{m - 2} ψ_{m + 1}^{2}) for m \geq 3

The polynomial $ψ_{n}$ is called the n^th division polynomial.

Properties

In practice, one sets $y^{2} = x^{3} + A x + B$ , and then $ψ_{2 m + 1} \in ℤ [x, A, B]$ and $ψ_{2 m} \in 2 y ℤ [x, A, B]$ .
The division polynomials form a generic elliptic divisibility sequence over the ring $ℚ [x, y, A, B] / (y^{2} - x^{3} - A x - B)$ .
If an elliptic curve $E$ is given in the Weierstrass form $y^{2} = x^{3} + A x + 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 $ψ_{2 n + 1}$ are the $x$ -coordinates of the points of $E [2 n + 1] ∖ {O}$ , where $E [2 n + 1]$ is the $(2 n + 1)^{th}$ torsion subgroup of $E$ . Similarly, the roots of $ψ_{2 n} / y$ are the $x$ -coordinates of the points of $E [2 n] ∖ E [2]$ .
Given a point $P = (x_{P}, y_{P})$ on the elliptic curve $E : y^{2} = x^{3} + A x + B$ over some field $K$ , we can express the coordinates of the n^th multiple of $P$ in terms of division polynomials:

n P = (\frac{ϕ_{n} (x)}{ψ_{n}^{2} (x)}, \frac{ω_{n} (x, y)}{ψ_{n}^{3} (x, y)}) = (x - \frac{ψ_{n - 1} ψ_{n + 1}}{ψ_{n}^{2} (x)}, \frac{ψ_{2 n} (x, y)}{2 ψ_{n}^{4} (x)})

where

ϕ_{n}

and

ω_{n}

are defined by:

ϕ_{n} = x ψ_{n}^{2} - ψ_{n + 1} ψ_{n - 1},

ω_{n} = \frac{ψ_{n + 2} ψ_{n - 1}^{2} - ψ_{n - 2} ψ_{n + 1}^{2}}{4 y} .

Using the relation between $ψ_{2 m}$ and $ψ_{2 m + 1}$ , along with the equation of the curve, the functions $ψ_{n}^{2}$ , $\frac{ψ_{2 n}}{y}, ψ_{2 n + 1}$ , $ϕ_{n}$ are all in $K [x]$ .

Let $p > 3$ be prime and let $E : y^{2} = x^{3} + A x + B$ be an elliptic curve over the finite field $𝔽_{p}$ , i.e., $A, B \in 𝔽_{p}$ . The $ℓ$ -torsion group of $E$ over ${\bar{𝔽}}_{p}$ is isomorphic to $ℤ / ℓ \times ℤ / ℓ$ if $ℓ \neq p$ , and to $ℤ / ℓ$ or ${0}$ if $ℓ = p$ . Hence the degree of $ψ_{ℓ}$ is equal to either $\frac{1}{2} (l^{2} - 1)$ , $\frac{1}{2} (l - 1)$ , or 0.

René Schoof observed that working modulo the $ℓ$ th division polynomial allows one to work with all $ℓ$ -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 (𝔽_{q})$ . 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 https://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 https://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.

Division polynomials

Definition

Properties

See also

References