# 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, model=None)#

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

The codomain and model parameters have the same meaning as for EllipticCurveIsogeny.

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

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

scaling_factor()#

Return the Weierstrass scaling factor associated to this composite morphism.

The scaling factor is the constant $$u$$ (in the base field) such that $$\varphi^* \omega_2 = u \omega_1$$, where $$\varphi: E_1\to E_2$$ is this morphism and $$\omega_i$$ are the standard Weierstrass differentials on $$E_i$$ defined by $$\mathrm dx/(2y+a_1x+a_3)$$.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: P = E.lift_x(7321)
sage: phi = EllipticCurveHom_composite(E, P)
sage: phi = WeierstrassIsomorphism(phi.codomain(), [7,8,9,10]) * phi
sage: phi.formal()
7*t + 65474*t^2 + 511*t^3 + 61316*t^4 + 20548*t^5 + 45511*t^6 + 37285*t^7 + 48414*t^8 + 9022*t^9 + 24025*t^10 + 35986*t^11 + 55397*t^12 + 25199*t^13 + 18744*t^14 + 46142*t^15 + 9078*t^16 + 18030*t^17 + 47599*t^18 + 12158*t^19 + 50630*t^20 + 56449*t^21 + 43320*t^22 + O(t^23)
sage: phi.scaling_factor()
7


ALGORITHM: The scaling factor is multiplicative under composition, so we return the product of the individual scaling factors associated to each factor.

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