Jump to content

Division polynomials

From Wikipedia, the free encyclopedia

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

[edit]

The set of division polynomials is a sequence of polynomials in with free variables that is recursively defined by:

The polynomial is called the nth division polynomial.

Properties

[edit]
  • In practice, one sets , and then and .
  • The division polynomials form a generic elliptic divisibility sequence over the ring .
  • If an elliptic curve is given in the Weierstrass form over some field , i.e. , one can use these values of and consider the division polynomials in the coordinate ring of . The roots of are the -coordinates of the points of , where is the torsion subgroup of . Similarly, the roots of are the -coordinates of the points of .
  • Given a point on the elliptic curve over some field , we can express the coordinates of the nth multiple of in terms of division polynomials:
where and are defined by:

Using the relation between and , along with the equation of the curve, the functions , , are all in .

Let be prime and let be an elliptic curve over the finite field , i.e., . The -torsion group of over is isomorphic to if , and to or if . Hence the degree of is equal to either , , 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.

See also

[edit]

References

[edit]
  • 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 . 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.