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.

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

ψ 0 = 0 {\displaystyle \psi _{0}=0}

ψ 1 = 1 {\displaystyle \psi _{1}=1}

ψ 2 = 2 y {\displaystyle \psi _{2}=2y}

ψ 3 = 3 x 4 + 6 A x 2 + 12 B x − A 2 {\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-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 ) {\displaystyle \psi _{4}=4y(x^{6}+5Ax^{4}+20Bx^{3}-5A^{2}x^{2}-4ABx-8B^{2}-A^{3})}

⋮ {\displaystyle \vdots }

ψ 2 m + 1 = ψ m + 2 ψ m 3 − ψ m − 1 ψ m + 1 3  for  m ≥ 2 {\displaystyle \psi _{2m+1}=\psi _{m+2}\psi _{m}^{3}-\psi _{m-1}\psi _{m+1}^{3}{\text{ for }}m\geq 2}

ψ 2 m = ( ψ m 2 y ) ⋅ ( ψ m + 2 ψ m − 1 2 − ψ m − 2 ψ m + 1 2 )  for  m ≥ 3 {\displaystyle \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 ψ n {\displaystyle \psi _{n}} is called the n^th division polynomial.

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

n P = ( ϕ n ( x ) ψ n 2 ( x ) , ω n ( x , y ) ψ n 3 ( x , y ) ) = ( x − ψ n − 1 ψ n + 1 ψ n 2 ( x ) , ψ 2 n ( x , y ) 2 ψ n 4 ( x ) ) {\displaystyle 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 ϕ n {\displaystyle \phi _{n}} and ω n {\displaystyle \omega _{n}} are defined by:

ϕ n = x ψ n 2 − ψ n + 1 ψ n − 1 , {\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},}

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

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

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

René Schoof observed that working modulo the ℓ {\displaystyle \ell } th division polynomial allows one to work with all ℓ {\displaystyle \ell } -torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.

• Schoof's algorithm

• 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 ( F q ) {\displaystyle E(\mathbb {F} _{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 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.