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

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> p = Integer(3) * Integer(2)**Integer(143) - Integer(1)
>>> GF(p**Integer(2)).inject_variables()
Defining z2
>>> E = EllipticCurve(GF(p**Integer(2)), [Integer(1),Integer(0)])
>>> P = E.lift_x(Integer(31415926535897932384626433832795028841971) - z2)
>>> P.order().factor()
2^143
>>> 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

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
p = 3 * 2^143 - 1
GF(p^2).inject_variables()
E = EllipticCurve(GF(p^2), [1,0])
P = E.lift_x(31415926535897932384626433832795028841971 - z2)
P.order().factor()
EllipticCurveHom_composite(E, P)

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

Sage

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)

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(419)), [Integer(0),Integer(1)])
>>> P = E.lift_x(Integer(33)); P.order()
35
>>> 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
>>> psi(E.lift_x(Integer(11)))
(352 : 346 : 1)
>>> 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))
>>> 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
>>> 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
>>> 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)

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(419), [0,1])
P = E.lift_x(33); P.order()
psi = EllipticCurveHom_composite(E, P); psi
psi(E.lift_x(11))
psi.rational_maps()
psi.kernel_polynomial()
psi.dual()
psi.formal()

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

sage: psi == EllipticCurveIsogeny(E, P)                                             # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> psi == EllipticCurveIsogeny(E, P)                                             # needs sage.rings.finite_rings
True

Sage Live

psi == EllipticCurveIsogeny(E, P)                                             # needs sage.rings.finite_rings

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

Sage

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)

Python

>>> from sage.all import *
>>> 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)

Sage Live

psi.factors()                                                                 # needs sage.rings.finite_rings

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)[source]¶

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

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

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(419)), [Integer(1),Integer(0)])                                     # needs sage.rings.finite_rings
>>> EllipticCurveHom_composite(E, E.lift_x(Integer(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

Sage Live

from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
E = EllipticCurve(GF(419), [1,0])                                     # needs sage.rings.finite_rings
EllipticCurveHom_composite(E, E.lift_x(23))                           # needs sage.rings.finite_rings

The given kernel generators need not be independent:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) - x - Integer(5), names=('a',)); (a,) = K._first_ngens(1)
>>> E = EllipticCurve('210.b6').change_ring(K)
>>> 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
>>> 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

Sage Live

# needs sage.rings.number_field
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 - x - 5)
E = EllipticCurve('210.b6').change_ring(K)
E.torsion_subgroup()
EllipticCurveHom_composite(E, E.torsion_points())

dual()[source]¶

Return the dual of this composite isogeny.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> P = E.lift_x(Integer(7321))
>>> 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
>>> 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
>>> psi * phi == phi.domain().scalar_multiplication(phi.degree())
True
>>> phi * psi == psi.domain().scalar_multiplication(psi.degree())
True

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
E = EllipticCurve(GF(65537), [1,2,3,4,5])
P = E.lift_x(7321)
phi = EllipticCurveHom_composite(E, P); phi
psi = phi.dual(); psi
psi * phi == phi.domain().scalar_multiplication(phi.degree())
phi * psi == psi.domain().scalar_multiplication(psi.degree())

factors()[source]¶

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

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)

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(43)), [Integer(1),Integer(0)])
>>> P, = E.gens()
>>> phi = EllipticCurveHom_composite(E, P)
>>> 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)

Sage Live

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

formal(prec=20)[source]¶

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

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)

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> P = E.lift_x(Integer(7321))
>>> phi = EllipticCurveHom_composite(E, P)
>>> 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)
>>> (phi.dual() * phi).formal(prec=Integer(5))
9*t + 65501*t^2 + 65141*t^3 + 59183*t^4 + 21491*t^5 + 8957*t^6
 + 999*t^7 + O(t^8)

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
E = EllipticCurve(GF(65537), [1,2,3,4,5])
P = E.lift_x(7321)
phi = EllipticCurveHom_composite(E, P)
phi.formal()
(phi.dual() * phi).formal(prec=5)

classmethod from_factors(maps, E=None, strict=True)[source]¶

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 – boolean (default: True); if True, always return an EllipticCurveHom_composite object, else may return another EllipticCurveHom type

OUTPUT: the composite of maps

EXAMPLES:

Sage

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

Python

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

Sage Live

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

inseparable_degree()[source]¶

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

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(j=GF(Integer(11)**Integer(5)).random_element())
>>> phi = E.frobenius_isogeny(Integer(2)) * E.scalar_multiplication(Integer(77))
>>> type(phi)
<class 'sage.schemes.elliptic_curves.hom_composite.EllipticCurveHom_composite'>
>>> phi.inseparable_degree()
1331

Sage Live

E = EllipticCurve(j=GF(11^5).random_element())
phi = E.frobenius_isogeny(2) * E.scalar_multiplication(77)
type(phi)
phi.inseparable_degree()

kernel_polynomial()[source]¶

Return the kernel polynomial of this composite isogeny.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> P = E.lift_x(Integer(7321))
>>> 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
>>> phi.kernel_polynomial()
x^4 + 46500*x^3 + 19556*x^2 + 7643*x + 15952

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
E = EllipticCurve(GF(65537), [1,2,3,4,5])
P = E.lift_x(7321)
phi = EllipticCurveHom_composite(E, P); phi
phi.kernel_polynomial()

rational_maps()[source]¶

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> P = E.lift_x(Integer(7321))
>>> phi = EllipticCurveHom_composite(E, P)
>>> 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))

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
E = EllipticCurve(GF(65537), [1,2,3,4,5])
P = E.lift_x(7321)
phi = EllipticCurveHom_composite(E, P)
phi.rational_maps()

scaling_factor()[source]¶

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

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> P = E.lift_x(Integer(7321))
>>> phi = EllipticCurveHom_composite(E, P)
>>> phi = WeierstrassIsomorphism(phi.codomain(), [Integer(7),Integer(8),Integer(9),Integer(10)]) * phi
>>> 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)
>>> phi.scaling_factor()
7

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
E = EllipticCurve(GF(65537), [1,2,3,4,5])
P = E.lift_x(7321)
phi = EllipticCurveHom_composite(E, P)
phi = WeierstrassIsomorphism(phi.codomain(), [7,8,9,10]) * phi
phi.formal()
phi.scaling_factor()

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()[source]¶

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> P = E.lift_x(Integer(7321))
>>> phi = EllipticCurveHom_composite(E, P)
>>> phi.x_rational_map() == phi.rational_maps()[Integer(0)]
True

Sage Live

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