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 \mathbb ,y,A,B/math> with $x, y, A, B$ free variables that is recursively defined by:

::$\psi_ = 0$

::$\psi_ = 1$

::$\psi_ = 2y$

::$\psi_ = 3x^ + 6Ax^ + 12Bx - A^$

::$\psi_ = 4y(x^ + 5Ax^ + 20Bx^ - 5A^x^ - 4ABx - 8B^ - A^)$

::$\vdots$

::$\psi_ = \psi_ \psi_^ - \psi_ \psi ^_ \text m \geq 2$

::$\psi_ = \left ( \frac \right ) \cdot ( \psi_\psi^_ - \psi_ \psi ^_) \text 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_\in\mathbb ,A,B/math> and \psi_\in 2y\mathbb ,A,B/math>.
* The division polynomials form a generic elliptic divisibility sequence over the ring \mathbb ,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_$ are the $x$-coordinates of the points of $E$n+1setminus \, where $E$n+1/math> is the $(2n+1)^$ torsion subgroup of $E$. Similarly, the roots of $\psi_/y$ are the $x$-coordinates of the points of E nsetminus E /math>.
*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, \frac \right) = \left( x - \frac , \frac \right)$
: where $\phi_$ and $\omega_$ are defined by:
::$\phi_=x\psi_^ - \psi_\psi_,$
::$\omega_=\frac.$

Using the relation between $\psi_$ and $\psi _$, along with the equation of the curve, the functions $\psi_^$ , $\frac, \psi_$, $\phi_$ are all in K /math>.

Let $p>3$ be prime and let $E:y^2=x^3+Ax+B$ be an elliptic curve over the finite field $\mathbb_p$, i.e., $A,B \in \mathbb_p$. The $\ell$-torsion group of $E$ over $\bar_p$ is isomorphic to $\mathbb/\ell \times \mathbb/\ell$ if $\ell\neq p$, and to $\mathbb/\ell$ or $\$ if $\ell=p$. Hence the degree of $\psi_\ell$ is equal to either $\frac(l^2-1)$, $\frac(l-1)$, or 0.

René Schoof

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases