Morphisms

Four types of maps between elliptic curves may be constructed: isogenies, isomorphisms, translations, and rational maps. Isogenies and isomorphisms are by far the most important and have the most functions associated to them. Isogenies are always surjective as scheme maps, even though the Magma parlance of a map from \(E({\mathbb{Q}})\rightarrow F({\mathbb{Q}})\) may seem to indicate that (for instance) the multiplication-by-two map is not surjective. There is an internal limit that the degrees of the polynomials defining an isogeny cannot be more than \(10^7\).

Creation Functions

Example: Parametrised Family of 2-Isogenies (ex-4a6549)

The following example gives a construction of a \(2\)-isogeny between elliptic curves. This example follows Example III 4.5 of Silverman [Sil86], and demonstrates a parametrised family of \(2\)-isogenies of elliptic curves together with its dual.

> FF := FiniteField(167);
> a := FF!2; b := FF!3; r := a^2 - 4*b;
> E1 := EllipticCurve([0, a, 0, b, 0]);
> E2 := EllipticCurve([0, -2*a, 0, r, 0]);
> _<x> := PolynomialRing(BaseRing(E1));
> Ff, f := IsogenyFromKernel(E1, x);
> Fg, g := IsogenyFromKernel(E2, x);
> b, m1 := IsIsomorphic(Ff, E2); assert b;
> b, m2 := IsIsomorphic(Fg, E1); assert b;
> // Verify that f and g are dual isogenies of degree 2
> &and[ m2(g(m1(f(P)))) eq 2*P : P in RationalPoints(E1) ];
true
> &and[ m1(f(m2(g(Q)))) eq 2*Q : Q in RationalPoints(E2) ];
true

Run in calculator (opens in a new tab)Copy input

Isomorphism(E, F, [r, s, t, u]): CrvEll, CrvEll, SeqEnum -> Map

Given elliptic curves \(E\) and \(F\) defined over the same field \(K\), and four elements \(r, s, t, u\) of \(K\) with \(u \ne 0\), this function returns the isomorphism \(E \rightarrow F\) mapping \(O_E \mapsto O_F\) and mapping \((x, y) \mapsto (u^2x + r, u^3y + su^2x + t)\). This function returns an error if the values passed do not define such an isomorphism.

Isomorphism(E, F): CrvEll, CrvEll -> Map

Given elliptic curves \(E\) and \(F\) defined over the same field \(K\), this function computes and returns an isomorphism from \(E\) to \(F\) where such an isomorphism exists. The map returned will be the same as the second return value of IsIsomorphic.

Automorphism(E, [r, s, t, u]): CrvEll, SeqEnum -> Map

Given an elliptic curve \(E\) defined over a field \(K\), and four elements \(r, s, t, u\) of \(K\) with \(u \ne 0\), this function returns the automorphism \(E \rightarrow E\) mapping \(O_E \mapsto O_E\) and mapping \((x, y) \mapsto (u^2x + r, u^3y + su^2x + t)\). This function returns an error if the values passed do not define such an automorphism.

IsomorphismData(I): Map -> [ RngElt ]

The sequence \([r, s, t, u]\) of elements defining the isomorphism \(I\).

Example: Testing Curves for Isomorphism (ex-3ea7a9)

Run in calculator (opens in a new tab)Copy input

We illustrate the isomorphism routines with some simple examples.

> K := GF(73);
> E1 := EllipticCurve([K | 3, 4, 2, 5, 1]);
> E2 := EllipticCurve([K | 8, 2, 29, 45, 28]);
> IsIsomorphic(E1, E2);
true
> m := Isomorphism(E1, E2, [3, 2, 1, 4]);
> m;
Elliptic curve isomorphism from: CrvEll: E1 to CrvEll: E2
Taking (x : y : 1) to (16*x + 3 : 64*y + 32*x + 1 : 1)
> P1 := Random(E1);
> P2 := Random(E1);
> m(P1 + P2) eq m(P1) + m(P2);
true

From the isomorphism data we can apply the map by hand if desired:

> r, s, t, u := Explode(IsomorphismData(Inverse(m)));
> P3 := E2![ 69, 64 ];
> x, y := Explode(Eltseq(P3));
> E1 ! [ u^2*x + r, u^3*y + s*u^2*x + t ];
(68 : 32 : 1)
> m($1) eq P3;
true

Run in calculator (opens in a new tab)Copy input

IsIsomorphism(I): Map -> BoolElt, Map

This function returns true if and only if the isogeny \(I\) has the same action as some isomorphism; if so, the isomorphism is also returned.

IsomorphismToIsogeny(I): Map -> Map

This function takes a map \(I\) of type isomorphism and returns an equivalent map with type isogeny.

Example: Converting Isogenies and Isomorphisms (ex-f4901b)

Run in calculator (opens in a new tab)Copy input

An example of how to use the previous two functions to transform isogenies to isomorphisms and vice versa.

> FF := FiniteField(23);
> E0 := EllipticCurve([FF | 1, 1]);
> E1 := EllipticCurve([FF | 3, 2]);
> b, iso := IsIsomorphic(E0, E1);
> b;
true
> iso;
Elliptic curve isomorphism from: CrvEll: E0 to CrvEll: E1
Taking (x : y : 1) to (16*x : 18*y : 1)
> isog := IsomorphismToIsogeny(iso);
> isog;
Elliptic curve isogeny from: CrvEll: E0 to CrvEll: E1
taking (x : y : 1) to (16*x : 18*y : 1)
> b, new_iso := IsIsomorphism(isog);
> b;
true
> inv := Inverse(new_iso);
> P := Random(E0);
> inv(isog(P)) eq P;
true

Run in calculator (opens in a new tab)Copy input

TranslationMap(E, P): CrvEll, PtEll -> Map

Given a rational point \(P\) on the elliptic curve \(E\), this function returns the morphism \(t_P : E \rightarrow E\) defined by \(t_P(Q) = P + Q\) for all rational points \(Q\) of \(E\).

RationalMap(i, t): Map, Map -> Map

Let \(i\) be an isogeny and \(t\) be a translation map \(t_P: E \rightarrow E\) where \(t_P(Q) = P + Q\) for some rational point \(P \in E\). This function returns the rational map \(\phi : E \rightarrow F\) obtained by composing \(i\) and \(t\) (applying \(t\) first). Any rational map \(E \rightarrow F\) can be represented in this form.

TwoIsogeny(P): PtEll -> Map

Given a \(2\)-torsion point \(P\) of the elliptic curve \(E\), this function returns a \(2\)-isogeny on \(E\) with \(P\) as its kernel.

Example: Generic Maps Between Curves (ex-fccac1)

Run in calculator (opens in a new tab)Copy input

One may, of course, also define maps between elliptic curves using the generic map constructors, as the following examples show.

> E1 := EllipticCurve([ GF(23) | 1, 1 ]);
> E2 := EllipticCurve([ GF(23, 2) | 1, 1 ]);

The doubling map on \(E_1\) lifted to \(E_2\):

> f := map<E1 -> E2 | P :-> 2*P>;

Two slightly different ways to define the negation map on \(E_1\) lifted to \(E_2\):

> f := map<E1 -> E2 | P :-> E2![ P[1], -P[2], P[3] ]>;
> f := map<E1 -> E2 | P :-> (P eq E1!0) select E2!0
>                           else E2![ P[1], -P[2], 1 ]>;

Run in calculator (opens in a new tab)Copy input

IsogenyFromKernel(G): SchGrpEll -> CrvEll, Map

Let \(G\) be a subgroup scheme of an elliptic curve \(E\). There is a separable isogeny \(f: E \rightarrow E_f\) to some other elliptic curve \(E_f\), which has kernel \(G\). This function returns the curve \(E_f\) and the map \(f\) using Velu’s formulae.

IsogenyFromKernelFactored(G): SchGrpEll -> CrvEll, Map

Returns a sequence of isogenies whose product is the isogeny returned by the invocation IsogenyFromKernel(G). These isogenies have either degree 2 or odd degree. This function was introduced because composing isogenies can be computationally expensive. The generic Expand function on a composition of maps can then be used if desired.

IsogenyFromKernel(E, psi): CrvEll, RngUPolElt -> CrvEll, Map

Given an elliptic curve \(E\) and a univariate polynomial \(psi\) which defines a subgroup scheme of \(E\), compute an isogeny using Velu’s formulae as above.

IsogenyFromKernelFactored(E, psi): SchGrpEll, RngUPolElt -> CrvEll, Map

Returns a sequence of isogenies whose product is the isogeny returned by the invocation IsogenyFromKernel(E, psi). These isogenies have either degree 2 or odd degree. This function was introduced because composing isogenies can be computationally expensive. The generic Expand function on a composition of maps can then be used if desired.

PushThroughIsogeny(I, v): Map, RngUPolElt -> RngUPolElt

PushThroughIsogeny(I, G): Map, SchGrpEll -> SchGrpEll

Given an isogeny \(I\) and a subgroup \(G\) which contains the kernel of \(I\), find the image of \(G\) under the action of \(I\). The subgroup \(G\) may be replaced by its defining polynomial \(v\).

DualIsogeny(phi): Map -> Map

Given an isogeny \(\phi : E_1 \rightarrow E_2\), the function returns another isogeny \(\phi^* : E_2 \rightarrow E_1\) such that \(\phi^* \circ \phi\) is multiplication by the degree of \(\phi\). The result is remembered and DualIsogeny(DualIsogeny(phi)) returns phi.

Example: Dual of an Isogeny (ex-b64f03)

Run in calculator (opens in a new tab)Copy input

We exhibit one way of calculating the dual of an isogeny. First we create a curve and an isogeny \(f\) with kernel equal to the full \(5\)-torsion polynomial.

> E := EllipticCurve([GF(97) | 2, 3]);
> E1, f := IsogenyFromKernel(E, DivisionPolynomial(E, 5));

The image curve \(E_1\) is isomorphic, but not equal, to the original curve \(E\). We proceed to find the dual of \(f\).

> deg := Degree(f);
> psi := DivisionPolynomial(E, deg);
> f1 := PushThroughIsogeny(f, psi);
> E2, g := IsogenyFromKernel(E1, f1);
> // Velu's formulae give an isomorphic curve, not the curve itself.
> IsIsomorphic(E2, E);
true
> h := Isomorphism(E2, E);
> f_dual := g*IsomorphismToIsogeny(h);

The latter isogeny is the dual of \(f\), as we verify:

> &and [ f_dual(f(P)) eq deg*P : P in RationalPoints(E) ];
true

A simpler way to verify this is just to check equality (note that both constructions of the dual involved an arbitrary choice of isomorphism):

> f_dual eq DualIsogeny(f);
true
> f_dual eq DualIsogeny(f) * NegationMap(E);
false;

Run in calculator (opens in a new tab)Copy input

Predicates on Isogenies

IsZero(I): Map -> BoolElt

IsConstant(I): Map -> BoolElt

Returns true if and only if the image of the isogeny \(I\) is the zero element of its codomain.

I eq J: Map, Map -> BoolElt

Returns true if and only if the isogenies \(I\) and \(J\) are equal.

Structure Operations

IsogenyMapPsi(I): Map -> RngUPolElt

Returns the univariate polynomial \(\psi\) used in defining the isogeny \(I\). The roots of \(\psi\) determine the kernel of \(I\).

IsogenyMapPsiMulti(I): Map -> RngUPolElt

Returns the polynomial \(\psi\) used in defining the isogeny \(I\) as a multivariate polynomial.

IsogenyMapPsiSquared(I): Map -> RngUPolElt

Returns the denominator of the fraction giving the image of the \(x\)-coordinate of a point under the isogeny \(I\) (the numerator is returned by IsogenyMapPhi(I)).

IsogenyMapPhi(I): Map -> RngUPolElt

Returns the univariate polynomial \(\phi\) used in defining the isogeny \(I\).

IsogenyMapPhiMulti(I): Map -> RngUPolElt

Returns the polynomial \(\phi\) used in defining the isogeny \(I\) as a multivariate polynomial.

IsogenyMapOmega(I): Map -> RngMPolElt

Returns the multivariate polynomial \(\omega\) used in defining the isogeny \(I\).

Kernel(I): Map -> SchGrpEll

Returns the subgroup of the domain consisting of the elements that map to zero under the isogeny \(I\).

Degree(I): Map -> RngIntElt

Returns the degree of the morphism \(I\).

Endomorphisms

Let \(E\) be an elliptic curve defined over the field \(K\). The set of endomorphisms \({\rm End}(E)\) of \(E\) to itself forms a ring under composition and addition of maps.

The endomorphism ring of \(E\) always contains a subring isomorphic to \({\mathbb{Z}}\). A curve \(E\) whose endomorphism ring contains additional isogenies is said to have complex multiplication. If \(E\) is defined over a finite field then \(E\) always has complex multiplication. The endomorphism ring of \(E\) is isomorphic to an order in either a quadratic number field or a quaternion algebra.

MultiplicationByMMap(E, m): CrvEll, RngIntElt -> Map

Returns the multiplication-by-\(m\) endomorphism \([m] : E \rightarrow E\) of the elliptic curve \(E\), such that \([m](P) = m*P\).

IdentityIsogeny(E): CrvEll -> Map

Returns the identity map \(E \rightarrow E\) of the elliptic curve \(E\) as an isogeny.

IdentityMap(E): CrvEll -> Map

Returns the identity map \(E \rightarrow E\) of the elliptic curve \(E\) as an isomorphism. The defining coefficients are \([r,s,t,u] = [0,0,0,1]\).

NegationMap(E): CrvEll -> Map

Returns the isomorphism of the elliptic curve \(E\) which maps \(P\) to \(-P\), for all \(P \in E\).

FrobeniusMap(E, i): CrvEll, RngIntElt -> Map

Returns the Frobenius isogeny \((x : y : 1) \mapsto (x^{p^i} : y^{p^i} : 1)\) of an elliptic curve \(E\) defined over a finite field of characteristic \(p\).

FrobeniusMap(E): CrvEll -> Map

Equivalent to FrobeniusMap(E, 1).

Example: Action of the Frobenius Map (ex-e6e186)

We check the action of the FrobeniusMap function.

> p := 23;
> FF1 := FiniteField(p);
> FF2 := FiniteField(p, 2);
> E1 := EllipticCurve([FF1 | 1, 3]);
> E2 := BaseExtend(E1, FF2);
> frob := FrobeniusMap(E2, 1);
> #{ E1!P : P in RationalPoints(E2) | P eq frob(P) } eq #E1;
true

Run in calculator (opens in a new tab)Copy input

Automorphisms

The functions in this section deal with automorphisms in the category of elliptic curves. For an elliptic curve \(E\) these are the automorphisms of the underlying curve that also preserve the group structure (equivalently, that send the identity \(O_E\) to itself).

Warning: The behaviour of these functions depends on the type of the input curve. For a general curve in Magma (an object that is a Crv but not a CrvEll) over a finite field, AutomorphismGroup and Automorphisms give automorphisms in the category of curves.

AutomorphismGroup(E): CrvEll -> Grp, Map

For an elliptic curve \(E\) over a general field \(K\), this function determines the group of automorphisms of \(E\) that are defined over \(K\). It returns an abstract group \(A\) (an abelian group or a polycyclic group), together with a map which sends elements of \(A\) to actual automorphisms of \(E\) (maps of schemes with domain and codomain \(E\)).

Automorphisms(E): CrvEll -> SeqEnum

For an elliptic curve \(E\) over a general field \(K\), this function returns a sequence containing the elements of the AutomorphismGroup of \(E.\)