Английская Википедия: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 <math>\mathbb{Z}[x,y,A,B]</math> with <math>x, y, A, B</math> free variables that is recursively defined by:
- <math>\psi_{0} = 0 </math>
- <math>\psi_{1} = 1</math>
- <math>\psi_{2} = 2y</math>
- <math>\psi_{3} = 3x^{4} + 6Ax^{2} + 12Bx - A^{2}</math>
- <math>\psi_{4} = 4y(x^{6} + 5Ax^{4} + 20Bx^{3} - 5A^{2}x^{2} - 4ABx - 8B^{2} - A^{3}) </math>
- <math>\vdots</math>
- <math>\psi_{2m+1} = \psi_{m+2} \psi_{m}^{ 3} - \psi_{m-1} \psi ^{ 3}_{ m+1} \text{ for } m \geq 2</math>
- <math>\psi_{ 2m} = \left ( \frac { \psi_{m}}{2y} \right ) \cdot ( \psi_{m+2}\psi^{ 2}_{m-1} - \psi_{m-2} \psi ^{ 2}_{m+1}) \text{ for } m \geq 3</math>
The polynomial <math>\psi_n</math> is called the nth division polynomial.
Properties
- In practice, one sets <math>y^2=x^3+Ax+B</math>, and then <math>\psi_{2m+1}\in\mathbb{Z}[x,A,B]</math> and <math>\psi_{2m}\in 2y\mathbb{Z}[x,A,B]</math>.
- The division polynomials form a generic elliptic divisibility sequence over the ring <math>\mathbb{Q}[x,y,A,B]/(y^2-x^3-Ax-B)</math>.
- If an elliptic curve <math>E</math> is given in the Weierstrass form <math>y^2=x^3+Ax+B</math> over some field <math>K</math>, i.e. <math>A, B\in K</math>, one can use these values of <math>A, B</math> and consider the division polynomials in the coordinate ring of <math>E</math>. The roots of <math>\psi_{2n+1}</math> are the <math>x</math>-coordinates of the points of <math>E[2n+1]\setminus \{O\}</math>, where <math>E[2n+1]</math> is the <math>(2n+1)^{\text{th}}</math> torsion subgroup of <math>E</math>. Similarly, the roots of <math>\psi_{2n}/y</math> are the <math>x</math>-coordinates of the points of <math>E[2n]\setminus E[2]</math>.
- Given a point <math>P=(x_P,y_P)</math> on the elliptic curve <math>E:y^2=x^3+Ax+B</math> over some field <math>K</math>, we can express the coordinates of the nth multiple of <math>P</math> in terms of division polynomials:
- <math>nP= \left ( \frac{\phi_{n}(x)}{\psi_{n}^{2}(x)}, \frac{\omega_{n}(x,y)}{\psi^{3}_{n}(x,y)} \right) = \left( x - \frac {\psi_{n-1} \psi_{n+1}}{\psi^{2}_{n}(x)}, \frac{\psi_{2 n}(x,y)}{2\psi^{4}_{n}(x)} \right)</math>
- where <math>\phi_{n}</math> and <math>\omega_{n}</math> are defined by:
- <math>\phi_{n}=x\psi_{n}^{2} - \psi_{n+1}\psi_{n-1},</math>
- <math>\omega_{n}=\frac{\psi_{n+2}\psi_{n-1}^{2}-\psi_{n-2}\psi_{n+1}^{2}}{4y}.</math>
Using the relation between <math>\psi_{2m}</math> and <math>\psi _{2m + 1}</math>, along with the equation of the curve, the functions <math>\psi_{n}^{2}</math> , <math>\frac{\psi_{2n}}{y}, \psi_{2n + 1}</math>, <math>\phi_{n}</math> are all in <math>K[x]</math>.
Let <math>p>3</math> be prime and let <math>E:y^2=x^3+Ax+B</math> be an elliptic curve over the finite field <math>\mathbb{F}_p</math>, i.e., <math>A,B \in \mathbb{F}_p</math>. The <math>\ell</math>-torsion group of <math>E</math> over <math>\bar{ \mathbb{F}}_p</math> is isomorphic to <math>\mathbb{Z}/\ell \times \mathbb{Z}/\ell</math> if <math>\ell\neq p</math>, and to <math>\mathbb{Z}/\ell </math> or <math>\{0\}</math> if <math>\ell=p</math>. Hence the degree of <math>\psi_\ell</math> is equal to either <math>\frac{1}{2}(l^2-1)</math>, <math>\frac{1}{2}(l-1)</math>, or 0.
René Schoof observed that working modulo the <math>\ell</math>th division polynomial allows one to work with all <math>\ell</math>-torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.
See also
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 <math>E(\mathbb{F}_q)</math>. 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.
Шаблон:Algebraic curves navbox
