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: Isogeny (ex-4a6549)#

The following example gives a construction of a \(2\)-isogeny between elliptic curves. This example follows Example III 4.5 of Silverman [Silverman, 1986], 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

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: Isomorphisms (ex-3ea7a9)#

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

Run in calculator

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

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: Isomorphism (ex-f4901b)#

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

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: Map (ex-fccac1)#

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

Run in calculator

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

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

Run in calculator

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

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 Isogeny (ex-b64f03)#

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

Run in calculator

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

Run in calculator

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

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

Run in calculator

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

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: Frobenius (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

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