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 ${\displaystyle \mathbb {Z} [x,y,A,B]}$ with ${\displaystyle x,y,A,B}$ free variables that is recursively defined by:

${\displaystyle \psi _{0}=0}$

${\displaystyle \psi _{1}=1}$

${\displaystyle \psi _{2}=2y}$

${\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2))$

${\displaystyle \psi _{4}=4y(x^{6}+5Ax^{4}+20Bx^{3}-5A^{2}x^{2}-4ABx-8B^{2}-A^{3})}$

${\displaystyle \vdots }$

${\displaystyle \psi _{2m+1}=\psi _{m+2}\psi _{m}^{3}-\psi _{m-1}\psi _{m+1}^{3}{\text{ for ))m\geq 2}$

${\displaystyle \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}$

The polynomial ${\displaystyle \psi _{n))$ is called the n^th division polynomial.

Properties

• In practice, one sets ${\displaystyle y^{2}=x^{3}+Ax+B}$, and then ${\displaystyle \psi _{2m+1}\in \mathbb {Z} [x,A,B]}$ and ${\displaystyle \psi _{2m}\in 2y\mathbb {Z} [x,A,B]}$.
• The division polynomials form a generic elliptic divisibility sequence over the ring ${\displaystyle \mathbb {Q} [x,y,A,B]/(y^{2}-x^{3}-Ax-B)}$.
• If an elliptic curve ${\displaystyle E}$ is given in the Weierstrass form ${\displaystyle y^{2}=x^{3}+Ax+B}$ over some field ${\displaystyle K}$, i.e. ${\displaystyle A,B\in K}$, one can use these values of ${\displaystyle A,B}$ and consider the division polynomials in the coordinate ring of ${\displaystyle E}$. The roots of ${\displaystyle \psi _{2n+1))$ are the ${\displaystyle x}$-coordinates of the points of ${\displaystyle E[2n+1]\setminus \{O\))$, where ${\displaystyle E[2n+1]}$ is the ${\displaystyle (2n+1)^{\text{th))}$ torsion subgroup of ${\displaystyle E}$. Similarly, the roots of ${\displaystyle \psi _{2n}/y}$ are the ${\displaystyle x}$-coordinates of the points of ${\displaystyle E[2n]\setminus E[2]}$.
• Given a point ${\displaystyle P=(x_{P},y_{P})}$ on the elliptic curve ${\displaystyle E:y^{2}=x^{3}+Ax+B}$ over some field ${\displaystyle K}$, we can express the coordinates of the n^th multiple of ${\displaystyle P}$ 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)}$

where ${\displaystyle \phi _{n))$ and ${\displaystyle \omega _{n))$ are defined by:

${\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},}$

${\displaystyle \omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2)){4y)).}$

Using the relation between ${\displaystyle \psi _{2m))$ and ${\displaystyle \psi _{2m+1))$, along with the equation of the curve, the functions ${\displaystyle \psi _{n}^{2))$ , ${\displaystyle {\frac {\psi _{2n)){y)),\psi _{2n+1))$, ${\displaystyle \phi _{n))$ are all in ${\displaystyle K[x]}$.

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

René Schoof observed that working modulo the ${\displaystyle \ell }$th division polynomial allows one to work with all ${\displaystyle \ell }$-torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.