# 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 ^{ 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 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^{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}$ and $\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.

• G. Musiker: Schoof's Algorithm for Counting Points on $E(\mathbb{F}_q)$. Available at http://www-math.mit.edu/~musiker/schoof.pdf