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: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: p = 3 * 2^143 - 1
sage: GF(p^2).inject_variables()                                                    # optional - sage.rings.finite_rings
Defining z2
sage: E = EllipticCurve(GF(p^2), [1,0])                                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(31415926535897932384626433832795028841971 - z2)                  # optional - sage.rings.finite_rings
sage: P.order().factor()                                                            # optional - sage.rings.finite_rings
2^143
sage: EllipticCurveHom_composite(E, P)                                              # optional - sage.rings.finite_rings
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])                                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(33); P.order()                                                   # optional - sage.rings.finite_rings
35
sage: psi = EllipticCurveHom_composite(E, P); psi                                   # optional - sage.rings.finite_rings
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))                                                             # optional - sage.rings.finite_rings
(352 : 346 : 1)
sage: psi.rational_maps()                                                           # optional - sage.rings.finite_rings
((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()                                                       # optional - sage.rings.finite_rings
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()                                                                    # optional - sage.rings.finite_rings
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()                                                                  # optional - sage.rings.finite_rings
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)                                             # optional - sage.rings.finite_rings
True

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

sage: psi.factors()                                                                 # optional - 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)#

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.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(419), [1,0])                                     # optional - sage.rings.finite_rings
sage: EllipticCurveHom_composite(E, E.lift_x(23))                           # optional - 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: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 - x - 5)                                      # optional - sage.rings.number_field
sage: E = EllipticCurve('210.b6').change_ring(K)                            # optional - sage.rings.number_field
sage: E.torsion_subgroup()                                                  # optional - sage.rings.number_field
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())                     # optional - sage.rings.number_field
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])                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(7321)                                                    # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P); phi                           # optional - sage.rings.finite_rings
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                                                 # optional - sage.rings.finite_rings
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())         # optional - sage.rings.finite_rings
True
sage: phi * psi == psi.domain().scalar_multiplication(psi.degree())         # optional - sage.rings.finite_rings
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])                                      # optional - sage.rings.finite_rings
sage: P, = E.gens()                                                         # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P)                                # optional - sage.rings.finite_rings
sage: phi.factors()                                                         # optional - sage.rings.finite_rings
(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])                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(7321)                                                    # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P)                                # optional - sage.rings.finite_rings
sage: phi.formal()                                                          # optional - sage.rings.finite_rings
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)                                     # optional - sage.rings.finite_rings
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:

maps – sequence of EllipticCurveHom objects
E (optional) – the domain elliptic curve
strict (optional, default: True) – if True, always return an EllipticCurveHom_composite object; else may return another EllipticCurveHom type

OUTPUT: the composite of maps

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(43), [1,0])                                      # optional - sage.rings.finite_rings
sage: P, = E.gens()                                                         # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P)                                # optional - sage.rings.finite_rings
sage: psi = EllipticCurveHom_composite.from_factors(phi.factors())          # optional - sage.rings.finite_rings
sage: psi == phi                                                            # optional - sage.rings.finite_rings
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))                # optional - sage.rings.finite_rings
sage: nu = EllipticCurveHom_composite.from_factors(E.automorphisms())       # optional - sage.rings.finite_rings
sage: nu                                                                    # optional - sage.rings.finite_rings
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()                                                     # optional - sage.rings.finite_rings
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])                                     # optional - sage.rings.finite_rings
sage: P = E.lift_x(1)                                                       # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P); phi                           # optional - sage.rings.finite_rings
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()                                                    # optional - sage.rings.finite_rings
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])                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(7321)                                                    # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P); phi                           # optional - sage.rings.finite_rings
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()                                               # optional - sage.rings.finite_rings
x^4 + 46500*x^3 + 19556*x^2 + 7643*x + 15952

static make_default()#

This method does nothing and will be removed.

(It is a leftover from the time when EllipticCurveHom_composite wasn’t the default yet.)

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: EllipticCurveHom_composite.make_default()
doctest:warning ...

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])                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(7321)                                                    # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P)                                # optional - sage.rings.finite_rings
sage: phi.rational_maps()                                                   # optional - sage.rings.finite_rings
((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 $φ^{*} ω_{2} = u ω_{1}$ , where $φ : E_{1} \to E_{2}$ is this morphism and $ω_{i}$ are the standard Weierstrass differentials on $E_{i}$ defined by $d x / (2 y + a_{1} x + 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])                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(7321)                                                    # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P)                                # optional - sage.rings.finite_rings
sage: phi = WeierstrassIsomorphism(phi.codomain(), [7,8,9,10]) * phi        # optional - sage.rings.finite_rings
sage: phi.formal()                                                          # optional - sage.rings.finite_rings
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()                                                  # optional - sage.rings.finite_rings
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])                             # optional - sage.rings.finite_rings
sage: P = E.lift_x(7321)                                                    # optional - sage.rings.finite_rings
sage: phi = EllipticCurveHom_composite(E, P)                                # optional - sage.rings.finite_rings
sage: phi.x_rational_map() == phi.rational_maps()[0]                        # optional - sage.rings.finite_rings
True