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()
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):
EllipticCurveHominterface, documentation and tests, equality testing
- class sage.schemes.elliptic_curves.hom_composite.EllipticCurveHom_composite(E, kernel, codomain=None, model=None)#
Bases:
sage.schemes.elliptic_curves.hom.EllipticCurveHomConstruct a composite isogeny with given kernel (and optionally, prescribed codomain curve). The isogeny is decomposed into steps of prime degree.
The
codomainandmodelparameters have the same meaning as forEllipticCurveIsogeny.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_compositeobject 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 ofEllipticCurveHomobjectsE(optional) – the domain elliptic curvestrict(optional, default:True) – ifTrue, always return anEllipticCurveHom_compositeobject; else may return anotherEllipticCurveHomtype
OUTPUT: the composite of
mapsEXAMPLES:
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
Trueif and only ifselfis 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()#
This method does nothing and will be removed.
(It is a leftover from the time when
EllipticCurveHom_compositewasn’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]) 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