# Polynomials

The *torsion* or *division* polynomials are the polynomials defining the subschemes of $n$-torsion points on the elliptic curve.

## `DefiningPolynomial(E): CrvEll -> RngMPolElt`

Returns the homogeneous defining polynomial for the elliptic curve $E$.

## `DivisionPolynomial(E, n): CrvEll, RngIntElt -> RngUPolElt, RngUPolElt, RngUPolElt`

## `DivisionPolynomial(E, n, g): CrvEll, RngIntElt, RngUPolElt -> RngUPolElt, RngUPolElt, RngUPolElt`

Given an elliptic curve $E$ and an integer $n$, returns the $n$-th division polynomial as a univariate polynomial over the base ring of $E$; its roots are the $x$-coordinates of the nonzero $n$-torsion points, each occurring once. The second return value is this polynomial divided by the univariate $2$-torsion polynomial if $n$ is even. The third argument is the cofactor, equal to the univariate $2$-torsion polynomial if $n$ is even, and $1$ otherwise.

If a polynomial is passed as a third argument then the division polynomial is computed efficiently modulo that polynomial.

## `TwoTorsionPolynomial(E): CrvEll -> RngMPolElt`

Returns the multivariate $2$-torsion polynomial $2y+a_1x+a_3$ of the elliptic curve $E$, as a bivariate polynomial.

## `Example: Division Polynomial (ex-d2495b)`

Let $E$ be an elliptic curve over a finite field $K$. The following code fragment illustrates the relationship between the roots in $K$ of the $n$-th division polynomial for $E$, and the $x$-coordinates of the points of $n$-torsion on $E$.

```magma
> K := GF(101);
> E := EllipticCurve([ K | 1, 1]);
> Roots(DivisionPolynomial(E, 5));
[ <86, 1>, <46, 1> ]
> [ P : P in RationalPoints(E) | 5*P eq E!0 ];
[ (86 : 34 : 1), (0 : 1 : 0), (46 : 25 : 1), (86 : 67 : 1), (46 : 76 : 1) ]

```

It is worth noting that even if the roots of the division polynomial lie in the field, the corresponding points may not, lying instead in a quadratic extension.

```magma
> Roots(DivisionPolynomial(E, 9));
[ <4, 1>, <17, 1>, <28, 1>, <34, 1>, <77, 1> ]
> Points(E, 4);
[]
> K2<w> := ext<K | 2>;
> Points(E(K2), 4);
[ (4 : 82*w + 57 : 1), (4 : 19*w + 44 : 1) ]
> Order($1[1]);
9

```

## Complex Multiplication Division Polynomials

Let $E$ be an elliptic curve with complex multiplication by an order $O$ in an imaginary quadratic field $K$, and let $\alpha \in O$. The endomorphism $[\alpha] : E \to E$ acts on $x$-coordinates by a rational function $x([\alpha]P) = \phi_\alpha(x) / \psi_\alpha(x)^e$, generalising the classical division polynomials; here $e = 2$ when $N(\alpha)$ is odd and $e = 1$ when the kernel is entirely $2$-torsion (a prime above $2$), matching the convention of `MultiplicationByMMap`; for other even $N(\alpha)$, where the kernel mixes $2$-torsion with higher-order points, no single $e$ works and `CMEndomorphism` should be used for the map instead. The endomorphism is normalised so that $[\alpha]^* \omega = \alpha \omega$ on the invariant differential $\omega$; equivalently $\phi_\alpha$ has leading coefficient $1/\alpha^2$. The element $\alpha$ may be prime, a prime power, or composite: a composite $\alpha$ is handled by composing the prime endomorphisms, which requires $K$ to have class number $1$. Currently $E$ must be defined over ${\mathbb{Q}}$ or over a field containing the CM field $K$ (when $K$ has class number greater than $1$ the CM endomorphisms are defined over the ring class field, so $E$ must be given there), and positive characteristic (finite fields) is not supported.

### `DivisionPolynomial(E, alpha): CrvEll, RngOrdElt -> RngUPolElt`

Given an elliptic curve $E$ with complex multiplication by an order containing $\alpha$, returns the complex multiplication division polynomial $\psi_\alpha$: the monic squarefree polynomial over the CM field $K$ whose roots are the $x$-coordinates of the nonzero points in the kernel of the endomorphism $[\alpha]$ (each occurring once). For a prime $\alpha$ lying above an odd rational prime $p$ its degree is $(p^2-1)/2$ when $p$ is inert and $(p-1)/2$ when $p$ splits or ramifies. For a prime above $2$ the degree is $3$ when $2$ is inert (the kernel is all of $E[2]$) and $1$ when $2$ splits or ramifies. For a split prime the two prime ideals above $p$ give distinct kernels, and the polynomial returned is the one belonging to the specific generator $\alpha$, its conjugate giving $\psi_{\bar\alpha}$.

### `DivisionPolynomial(E, a): CrvEll, RngOrdIdl -> RngUPolElt`

Given an elliptic curve $E$ with complex multiplication and an ideal $a$ of its CM order, returns the $a$-division polynomial: the monic polynomial whose roots are the $x$-coordinates of the nonzero points of the $a$-torsion $E[a]$ (the points killed by every element of $a$). For a principal ideal $a = (\alpha)$ this equals `DivisionPolynomial(E, alpha)` and depends only on $a$, not on the choice of generator. Non-principal ideals (which occur only when the CM field has class number greater than $1$) are not currently supported.

### `MultiplicationPolynomial(E, alpha): CrvEll, RngOrdElt -> RngUPolElt`

Given an elliptic curve $E$ with complex multiplication by an order containing $\alpha$, returns the numerator $\phi_\alpha$ of the multiplication-by-$\alpha$ map, so that $x([\alpha]P) = \phi_\alpha(x) / \psi_\alpha(x)^e$ where $\psi_\alpha$ is `DivisionPolynomial(E, alpha)` and $e = 2$ for $N(\alpha)$ odd, $e = 1$ when the kernel is entirely $2$-torsion (a prime above $2$). For other even $N(\alpha)$, where the kernel mixes $2$-torsion with higher-order points, no single $e$ reproduces $x([\alpha]P)$ from $\psi_\alpha$; use `CMEndomorphism` for the map in that case. This is the complex multiplication analogue of the multiplication map `MultiplicationByMMap(E, n)` for a rational integer $n$. The polynomial $\phi_\alpha$ has degree $N(\alpha)$ and leading coefficient $1/\alpha^2$.

### `CMEndomorphism(E, alpha): CrvEll, RngOrdElt -> Map`

Given an elliptic curve $E$ with complex multiplication by an order containing $\alpha$, returns the CM endomorphism $[\alpha] : E \to E$ as a map, normalised so that $[\alpha]^* \omega = \alpha \omega$ on the invariant differential. On $x$-coordinates it acts by the rational function of `MultiplicationPolynomial` and `DivisionPolynomial` above. This is the complex multiplication analogue of `MultiplicationByMMap(E, n)` for a rational integer $n$.

### `Example: CM Division Polynomial (ex-58df2e)`

We take the $j = 0$ curve $y^2 = x^3 - 1$, which has complex multiplication by the Eisenstein integers, and compute the division and multiplication polynomials of the endomorphism $[\alpha]$ for $\alpha = 2 + a$, where $a = (1 + \sqrt{-3})/2$; here $N(\alpha) = 7$.

```magma
> K<w> := QuadraticField(-3);
> O<a> := MaximalOrder(K);
> E := EllipticCurve([K | 0, 0, 0, 0, -1]);
> _, D := HasComplexMultiplication(E);
> D;
-3
> alpha := 2 + a;
> Norm(alpha);
7
> psi := DivisionPolynomial(E, alpha);
> psi;
x^3 + 1/7*(-6*w + 2)
> ChangeRing(DivisionPolynomial(E, 7), K) mod psi eq 0;
true
> phi := MultiplicationPolynomial(E, alpha);
> phi;
1/98*(-5*w + 11)*x^7 + 1/7*(26*w + 10)*x^4 + 1/7*(-16*w - 32)*x

```