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.

EXAMPLES:

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

sage: # needs sage.rings.finite_rings
sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
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: # needs sage.rings.finite_rings
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 : 346 : 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)                                             # needs sage.rings.finite_rings
True

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

sage: psi.factors()                                                                 # needs sage.rings.finite_rings
(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, velu_sqrt_bound=None)#

Bases: EllipticCurveHom

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.

The optional parameter velu_sqrt_bound prescribes the point in which the computation of a single isogeny should be performed using square root Velu instead of simple Velu. If not provided, the system default is used (see EllipticCurve_field.isogeny for a more detailed discussion.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(419), [1,0])                                     # needs sage.rings.finite_rings
sage: EllipticCurveHom_composite(E, E.lift_x(23))                           # needs sage.rings.finite_rings
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: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
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: # needs sage.rings.finite_rings
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().scalar_multiplication(phi.degree())
True
sage: phi * psi == psi.domain().scalar_multiplication(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: # needs sage.rings.finite_rings
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
inseparable_degree()#

Return the inseparable degree of this morphism.

Like the degree, the inseparable degree is multiplicative under composition, so this method returns the product of the inseparable degrees of the factors.

EXAMPLES:

sage: E = EllipticCurve(j=GF(11^5).random_element())
sage: phi = E.frobenius_isogeny(2) * E.scalar_multiplication(77)
sage: type(phi)
<class 'sage.schemes.elliptic_curves.hom_composite.EllipticCurveHom_composite'>
sage: phi.inseparable_degree()
1331
kernel_polynomial()#

Return the kernel polynomial of this composite isogeny.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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
rational_maps()#

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

EXAMPLES:

sage: # needs sage.rings.finite_rings
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: # needs sage.rings.finite_rings
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: # needs sage.rings.finite_rings
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