Composite morphisms of elliptic curves

It is often computationally convenient (for example, in cryptography) to factor an isogeny of large degree into a composition of isogenies of smaller (prime) degree. This class implements such a decomposition while exposing (close to) the same interface as “normal”, unfactored elliptic-curve isogenies.

Warning

This module is currently considered experimental. It may change in a future release without prior warning, or even be removed altogether if things turn out to be unfixably broken.

EXAMPLES:

The following example would take quite literally forever with the straightforward EllipticCurveIsogeny implementation, but decomposing into prime steps is exponentially faster:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
doctest:warning
...
sage: p = 3 * 2^143 - 1
sage: GF(p^2).inject_variables()
Defining z2
sage: E = EllipticCurve(GF(p^2), [1,0])
sage: P = E.lift_x(31415926535897932384626433832795028841971 - z2)
sage: P.order().factor()
2^143
sage: EllipticCurveHom_composite(E, P)
Composite morphism of degree 11150372599265311570767859136324180752990208 = 2^143:
  From: Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 33451117797795934712303577408972542258970623^2
  To:   Elliptic Curve defined by y^2 = x^3 + (18676616716352953484576727486205473216172067*z2+32690199585974925193292786311814241821808308)*x + (3369702436351367403910078877591946300201903*z2+15227558615699041241851978605002704626689722) over Finite Field in z2 of size 33451117797795934712303577408972542258970623^2

Yet, the interface provided by EllipticCurveHom_composite is identical to EllipticCurveIsogeny and other instantiations of EllipticCurveHom:

sage: E = EllipticCurve(GF(419), [0,1])
sage: P = E.lift_x(33); P.order()
35
sage: psi = EllipticCurveHom_composite(E, P); psi
Composite morphism of degree 35 = 5*7:
  From: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 419
  To:   Elliptic Curve defined by y^2 = x^3 + 101*x + 285 over Finite Field of size 419
sage: psi(E.lift_x(11))
(352 : 73 : 1)
sage: psi.rational_maps()
((x^35 + 162*x^34 + 186*x^33 + 92*x^32 - ... + 44*x^3 + 190*x^2 + 80*x - 72)/(x^34 + 162*x^33 - 129*x^32 + 41*x^31 + ... + 66*x^3 - 191*x^2 + 119*x + 21),
 (x^51*y - 176*x^50*y + 115*x^49*y - 120*x^48*y + ... + 72*x^3*y + 129*x^2*y + 163*x*y + 178*y)/(x^51 - 176*x^50 + 11*x^49 + 26*x^48 - ... - 77*x^3 + 185*x^2 + 169*x - 128))
sage: psi.kernel_polynomial()
x^17 + 81*x^16 + 7*x^15 + 82*x^14 + 49*x^13 + 68*x^12 + 109*x^11 + 326*x^10 + 117*x^9 + 136*x^8 + 111*x^7 + 292*x^6 + 55*x^5 + 389*x^4 + 175*x^3 + 43*x^2 + 149*x + 373
sage: psi.dual()
Composite morphism of degree 35 = 7*5:
  From: Elliptic Curve defined by y^2 = x^3 + 101*x + 285 over Finite Field of size 419
  To:   Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 419
sage: psi.formal()
t + 211*t^5 + 417*t^7 + 159*t^9 + 360*t^11 + 259*t^13 + 224*t^15 + 296*t^17 + 139*t^19 + 222*t^21 + O(t^23)

Equality is decided correctly (and, in some cases, much faster than comparing EllipticCurveHom.rational_maps()) even when distinct factorizations of the same isogeny are compared:

sage: psi == EllipticCurveIsogeny(E, P)
True

We can easily obtain the individual factors of the composite map:

sage: psi.factors()
(Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 419 to Elliptic Curve defined by y^2 = x^3 + 140*x + 214 over Finite Field of size 419,
 Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 140*x + 214 over Finite Field of size 419 to Elliptic Curve defined by y^2 = x^3 + 101*x + 285 over Finite Field of size 419)

AUTHORS:

  • Lukas Zobernig (2020): initial proof-of-concept version

  • Lorenz Panny (2021): EllipticCurveHom interface, documentation and tests, equality testing

class sage.schemes.elliptic_curves.hom_composite.EllipticCurveHom_composite(E, kernel, codomain=None)

Bases: sage.schemes.elliptic_curves.hom.EllipticCurveHom

Construct a composite isogeny with given kernel (and optionally, prescribed codomain curve). The isogeny is decomposed into steps of prime degree.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(419), [1,0])
sage: EllipticCurveHom_composite(E, E.lift_x(23))
Composite morphism of degree 105 = 3*5*7:
  From: Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 419
  To:   Elliptic Curve defined by y^2 = x^3 + 373*x + 126 over Finite Field of size 419

The given kernel generators need not be independent:

sage: K.<a> = NumberField(x^2 - x - 5)
sage: E = EllipticCurve('210.b6').change_ring(K)
sage: E.torsion_subgroup()
Torsion Subgroup isomorphic to Z/12 + Z/2 associated to the Elliptic Curve defined by y^2 + x*y + y = x^3 + (-578)*x + 2756 over Number Field in a with defining polynomial x^2 - x - 5
sage: EllipticCurveHom_composite(E, E.torsion_points())
Composite morphism of degree 24 = 2^3*3:
  From: Elliptic Curve defined by y^2 + x*y + y = x^3 + (-578)*x + 2756 over Number Field in a with defining polynomial x^2 - x - 5
  To:   Elliptic Curve defined by y^2 + x*y + y = x^3 + (-89915533/16)*x + (-328200928141/64) over Number Field in a with defining polynomial x^2 - x - 5
degree()

Return the degree of this composite isogeny.

Degrees are multiplicative, so this is the product of the degrees of the individual factors.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(419), [1,0])
sage: P, = E.gens()
sage: phi = EllipticCurveHom_composite(E, P+P)
sage: phi.degree()
210
dual()

Return the dual of this composite isogeny.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: P = E.lift_x(7321)
sage: phi = EllipticCurveHom_composite(E, P); phi
Composite morphism of degree 9 = 3^2:
  From: Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 65537
  To:   Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 28339*x + 59518 over Finite Field of size 65537
sage: psi = phi.dual(); psi
Composite morphism of degree 9 = 3^2:
  From: Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 28339*x + 59518 over Finite Field of size 65537
  To:   Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 65537
sage: psi * phi == phi.domain().multiplication_by_m_isogeny(phi.degree())
True
sage: phi * psi == psi.domain().multiplication_by_m_isogeny(psi.degree())
True
factors()

Return the factors of this composite isogeny as a tuple.

The isogenies are returned in left-to-right order, i.e., the returned tuple \((f_1,...,f_n)\) corresponds to the map \(f_n \circ \dots \circ f_1\).

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(43), [1,0])
sage: P, = E.gens()
sage: phi = EllipticCurveHom_composite(E, P)
sage: phi.factors()
(Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 43 to Elliptic Curve defined by y^2 = x^3 + 39*x over Finite Field of size 43,
 Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 39*x over Finite Field of size 43 to Elliptic Curve defined by y^2 = x^3 + 42*x + 26 over Finite Field of size 43,
 Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + 42*x + 26 over Finite Field of size 43 to Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 43)
formal(prec=20)

Return the formal isogeny corresponding to this composite isogeny as a power series in the variable \(t=-x/y\) on the domain curve.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: P = E.lift_x(7321)
sage: phi = EllipticCurveHom_composite(E, P)
sage: phi.formal()
t + 54203*t^5 + 48536*t^6 + 40698*t^7 + 37808*t^8 + 21111*t^9 + 42381*t^10 + 46688*t^11 + 657*t^12 + 38916*t^13 + 62261*t^14 + 59707*t^15 + 30767*t^16 + 7248*t^17 + 60287*t^18 + 50451*t^19 + 38305*t^20 + 12312*t^21 + 31329*t^22 + O(t^23)
sage: (phi.dual() * phi).formal(prec=5)
9*t + 65501*t^2 + 65141*t^3 + 59183*t^4 + 21491*t^5 + 8957*t^6 + 999*t^7 + O(t^8)
classmethod from_factors(maps, E=None, strict=True)

This method constructs a EllipticCurveHom_composite object encapsulating a given sequence of compatible isogenies.

The isogenies are composed in left-to-right order, i.e., the resulting composite map equals \(f_{n-1} \circ \dots \circ f_0\) where \(f_i\) denotes maps[i].

INPUT:

OUTPUT: the composite of maps

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(43), [1,0])
sage: P, = E.gens()
sage: phi = EllipticCurveHom_composite(E, P)
sage: psi = EllipticCurveHom_composite.from_factors(phi.factors())
sage: psi == phi
True
is_injective()

Determine whether this composite morphism has trivial kernel.

In other words, return True if and only if self is a purely inseparable isogeny.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve([1,0])
sage: phi = EllipticCurveHom_composite(E, E(0,0))
sage: phi.is_injective()
False
sage: E = EllipticCurve_from_j(GF(3).algebraic_closure()(0))
sage: nu = EllipticCurveHom_composite.from_factors(E.automorphisms())
sage: nu
Composite morphism of degree 1 = 1^12:
  From: Elliptic Curve defined by y^2 = x^3 + x over Algebraic closure of Finite Field of size 3
  To:   Elliptic Curve defined by y^2 = x^3 + x over Algebraic closure of Finite Field of size 3
sage: nu.is_injective()
True
is_separable()

Determine whether this composite isogeny is separable.

A composition of isogenies is separable if and only if all factors are.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(7^2), [3,2])
sage: P = E.lift_x(1)
sage: phi = EllipticCurveHom_composite(E, P); phi
Composite morphism of degree 7 = 7:
  From: Elliptic Curve defined by y^2 = x^3 + 3*x + 2 over Finite Field in z2 of size 7^2
  To:   Elliptic Curve defined by y^2 = x^3 + 3*x + 2 over Finite Field in z2 of size 7^2
sage: phi.is_separable()
True
kernel_polynomial()

Return the kernel polynomial of this composite isogeny.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: P = E.lift_x(7321)
sage: phi = EllipticCurveHom_composite(E, P); phi
Composite morphism of degree 9 = 3^2:
  From: Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 65537
  To:   Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 28339*x + 59518 over Finite Field of size 65537
sage: phi.kernel_polynomial()
x^4 + 46500*x^3 + 19556*x^2 + 7643*x + 15952
static make_default()

Calling this method will override the composition method of EllipticCurveHom such that it constructs a EllipticCurveHom_composite object by default, rather than a sage.categories.map.FormalCompositeMap.

Warning

This method exists only temporarily to make testing more convenient while EllipticCurveHom_composite is experimental.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(587), [1,0])
sage: P = E(3,404)
sage: phi = E.isogeny(7*P)
sage: psi = phi.codomain().isogeny(phi(P))
sage: psi * phi
Composite map:
  From: Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 587
  To:   Elliptic Curve defined by y^2 = x^3 + 296*x + 164 over Finite Field of size 587
  Defn:   Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 587 to Elliptic Curve defined by y^2 = x^3 + 126*x + 500 over Finite Field of size 587
        then
          Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 126*x + 500 over Finite Field of size 587 to Elliptic Curve defined by y^2 = x^3 + 296*x + 164 over Finite Field of size 587
sage: EllipticCurveHom_composite.make_default()
sage: psi * phi
Composite morphism of degree 49 = 7^2:
  From: Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 587
  To:   Elliptic Curve defined by y^2 = x^3 + 296*x + 164 over Finite Field of size 587
sage: (psi * phi).factors()
(Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 587 to Elliptic Curve defined by y^2 = x^3 + 126*x + 500 over Finite Field of size 587,
 Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 126*x + 500 over Finite Field of size 587 to Elliptic Curve defined by y^2 = x^3 + 296*x + 164 over Finite Field of size 587)
rational_maps()

Return the pair of explicit rational maps defining this composite isogeny.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: P = E.lift_x(7321)
sage: phi = EllipticCurveHom_composite(E, P)
sage: phi.rational_maps()
((x^9 + 27463*x^8 + 21204*x^7 - 5750*x^6 + 1610*x^5 + 14440*x^4 + 26605*x^3 - 15569*x^2 - 3341*x + 1267)/(x^8 + 27463*x^7 + 26871*x^6 + 5999*x^5 - 20194*x^4 - 6310*x^3 + 24366*x^2 - 20905*x - 13867),
 (x^12*y + 8426*x^11*y + 5667*x^11 + 27612*x^10*y + 26124*x^10 + 9688*x^9*y - 22715*x^9 + 19864*x^8*y + 498*x^8 + 22466*x^7*y - 14036*x^7 + 8070*x^6*y + 19955*x^6 - 20765*x^5*y - 12481*x^5 + 12672*x^4*y + 24142*x^4 - 23695*x^3*y + 26667*x^3 + 23780*x^2*y + 17864*x^2 + 15053*x*y - 30118*x + 17539*y - 23609)/(x^12 + 8426*x^11 + 21945*x^10 - 22587*x^9 + 22094*x^8 + 14603*x^7 - 26255*x^6 + 11171*x^5 - 16508*x^4 - 14435*x^3 - 2170*x^2 + 29081*x - 19009))
x_rational_map()

Return the \(x\)-coordinate rational map of this composite isogeny.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: P = E.lift_x(7321)
sage: phi = EllipticCurveHom_composite(E, P)
sage: phi.x_rational_map() == phi.rational_maps()[0]
True