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
with
free variables that is recursively defined by:
![\psi _{{0}}=0](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ebd23bd9d43a40463a65b3184437e36a2604fd6)
![{\displaystyle \psi _{1}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/185d8a9e5d91f60349f4025399ba449a33417bb7)
![{\displaystyle \psi _{2}=2y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff504b23e75f26f65b5231e1de85591305b61c29)
![{\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35c58b542f03027d51493ad13282091b345a19c5)
![\psi _{{4}}=4y(x^{{6}}+5Ax^{{4}}+20Bx^{{3}}-5A^{{2}}x^{{2}}-4ABx-8B^{{2}}-A^{{3}})](https://wikimedia.org/api/rest_v1/media/math/render/svg/55c6b363fefb8004c887694d0c07a6ecd403e219)
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
![{\displaystyle \psi _{2m+1}=\psi _{m+2}\psi _{m}^{3}-\psi _{m-1}\psi _{m+1}^{3}{\text{ for }}m\geq 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31b366def0f19dcc640a11584174f1168eaaef2b)
![\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](https://wikimedia.org/api/rest_v1/media/math/render/svg/666d8a50e53842a78ee186c0afddcc15779839fc)
The polynomial
is called the nth division polynomial.
Properties
- 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:
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4db87be5b2af7935f994e7faf353a7cbd38ac3d0)
- where
and
are defined by:
![{\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a43772d4f9d56c85335b1df4d526ee0a721d5c78)
![{\displaystyle \omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2}}{4y}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5e0b52171d5d685313e9e5293828c6dc3ba5cce)
Using the relation between
and
, along with the equation of the curve, the functions
,
and
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
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
. 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.