Division polynomials explained

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

Z [x,y,A,B] with x, y, A, B free variables that is recursively defined by:\psi _{0} = 0 \psi _{1} = 1 \psi _{2} = 2 y \psi _{3} = 3 x ^{4} + 6 Ax ^{2} + 12 Bx - A ^{2} \psi _{4} = 4 y(x ^{6} + 5 Ax ^{4} + 20 Bx ^{3} - 5 A ^{2} x ^{2} - 4 ABx - 8 B ^{2} - A ^{3} ) \vdots \psi _{2m+1} = \psi _{m+2} \psi ^{3} _{m} - \psi _{m-1} \psi ^{3} ^{m +1} for m \geq 2 \psi = \left ( (\psi _{m})/(2 y) \right ) ⋅ ( \psi _{m+2} \psi ^{2} _{m -1} - \psi _{m-2} \psi ^{2} ^{m +1} ) for 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 _{2m+1} \in Z [x,A,B] and \psi _{2m} \in 2 y 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-Ax-B)} .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 _{2n+1} are the x -coordinates of the points of E[ 2 n +1 ]\setminus \{O\} , where E[ 2 n +1 ] is the ( 2 n +1 ) ^{th} torsion subgroup of E . Similarly, the roots of \psi _{2n} /y are the x -coordinates of the points of E[ 2 n]\setminus E[ 2 ] .

• 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 ( (\phi _{n} (x))/(\psi ^{2} _{n} (x)) , (\omega _{n} (x,y))/(\psi ^{3} _{n} (x,y)) \right) = \left( x - (\psi _{n-1} \psi _{n+1})/(\psi ^{2} _{n} (x)) , (\psi _{2} (x,y))/(2 \psi ^{4} _{n} (x)) \right)

where

\phi _{n} and \omega _{n} are defined by:\phi _{n} = x\psi ^{2} _{n} - \psi _{n+1} \psi _{n-1} , \omega _{n} = (\psi _{n +2} \psi ^{2} _{n -1} - \psi _{n-2} \psi ^{2} _{n +1})/(4 y) .

Using the relation between

\psi _{2m} and \psi _{2m} , along with the equation of the curve, the functions \psi ^{2} _{n} , (\psi _{2n})/(y) , \psi _{2n} , \phi _{n} are all in K[x] .

Let

p> 3 be prime and let E:y ^{2=x} ^{3+Ax+B} be an elliptic curve over the finite field F _{p} , i.e., A,B \in F _{p} . The \ell -torsion group of E over \bar{ F }_p is isomorphic to Z /\ell x Z /\ell if \ell ≠ p , and to Z /\ell or \{ 0 \} if \ell = p . Hence the degree of \psi _{\ell} is equal to either (1)/(2) (l ^{2-1)} , (1)/(2) (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( 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.