Division polynomials

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. \psi_{0} = 0 \psi_{1} = 1 \psi_{2} = 2y \psi_{3} = 3x^{4} + 6Ax^{2} + 12Bx - A^{2} \psi_{4} = 4y(x^{6} + 5Ax^{4} + 20Bx^{3} - 5A^{2}x^{2} - 4ABx - 8B^{2} - A^{3}) \vdots \psi_{2m+1} = \psi_{m+2} \psi_{m}^{ 3} - \psi_{m-1} \psi ^{ 3}_{ m+1} \text{ for } m \geq 2 \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 The polynomial \psi_n is called the n th division polynomial. In practice, one sets y^2=x^3+Ax+B , and then \psi_{2m+1}\in\mathbb{Z}[x,A,B] and \psi_{2m}\in 2y\mathbb{Z}[x,A,B] . The division polynomials form a generic elliptic divisibility sequence over the ring \mathbb{Q}[x,y,A,B]/(y^2-x^3-Ax-B) . If an elliptic curve 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[2n+1]\setminus \{O\} , where E[2n+1] is the (2n+1)^{\text{th}} torsion subgroup of E . Similarly, the roots of \psi_{2n}/y are the x -coordinates of the points of E[2n]\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 ( \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) where \phi_{n} and \omega_{n} are defined by: \phi_{n}=x\psi_{n}^{2} - \psi_{n+1}\psi_{n-1}, \omega_{n}=\frac{\psi_{n+2}\psi_{n-1}^{2}-\psi_{n-2}\psi_{n+1}^{2}}{4y}. Using the relation between \psi_{2m} and \psi _{2m + 1} , along with the equation of the curve, the functions \psi_{n}^{2} , \frac{\psi_{2n}}{y}, \psi_{2n + 1} , \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 \mathbb{F}_p , i.e., A,B \in \mathbb{F}_p . The \ell -torsion group of E over \bar{ \mathbb{F}}_p is isomorphic to \mathbb{Z}/\ell \times \mathbb{Z}/\ell if \ell\neq p , and to \mathbb{Z}/\ell or \{0\} if \ell=p . Hence the degree of \psi_\ell is equal to either \frac{1}{2}(l^2-1) , \frac{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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1289128105 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001289128105 · captured 1746544217.0 · version history

Cite this page as: encyclopegia.org, “Division polynomials”, snapshot enwiki-001289128105. https://encyclopegia.org/a/division-polynomials

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.