# 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 {Z} [x,y,A,B]$ with $x,y,A,B$ free variables that is recursively defined by:
       $\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 _{m+1}^{3}{\text{ for }}m\geq 2$
       $\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 $\psi _{n}$ is called the nth division polynomial.

## Properties

* 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 nth multiple of $P$ in terms of division polynomials:
       $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 $\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.