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\).

> 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) ]

Run in calculator

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.

> 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

Run in calculator

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\).

> 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

Run in calculator