Isogenies#
An isogeny \(\varphi: E_1\to E_2\) between two elliptic curves \(E_1\) and \(E_2\) is a morphism of curves that sends the origin of \(E_1\) to the origin of \(E_2\). Such a morphism is automatically a morphism of group schemes and the kernel is a finite subgroup scheme of \(E_1\). Such a subscheme can either be given by a list of generators, which have to be torsion points, or by a polynomial in the coordinate \(x\) of the Weierstrass equation of \(E_1\).
The usual way to create and work with isogenies is illustrated with the following example:
sage: k = GF(11)
sage: E = EllipticCurve(k, [1,1])
sage: Q = E(6,5)
sage: phi = E.isogeny(Q)
sage: phi
Isogeny of degree 7
from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 11
to Elliptic Curve defined by y^2 = x^3 + 7*x + 8
over Finite Field of size 11
sage: P = E(4,5)
sage: phi(P)
(10 : 0 : 1)
sage: phi.codomain()
Elliptic Curve defined by y^2 = x^3 + 7*x + 8 over Finite Field of size 11
sage: phi.rational_maps()
((x^7 + 4*x^6 - 3*x^5 - 2*x^4
- 3*x^3 + 3*x^2 + x - 2)/(x^6 + 4*x^5 - 4*x^4 - 5*x^3 + 5*x^2),
(x^9*y - 5*x^8*y - x^7*y + x^5*y - x^4*y
- 5*x^3*y - 5*x^2*y - 2*x*y - 5*y)/(x^9 - 5*x^8 + 4*x^6 - 3*x^4 + 2*x^3))
The methods directly accessible from an elliptic curve E
over a
field are
isogeny()
and
isogeny_codomain()
.
The most useful methods that apply to isogenies are:
.domain()
.codomain()
Warning
This class only implements separable isogenies. When using Kohel’s algorithm, only cyclic isogenies can be computed (except for \([2]\)).
Working with other kinds of isogenies may be possible using other
child classes of EllipticCurveHom
.
Some algorithms may need the isogeny to be normalized.
AUTHORS:
Daniel Shumow <shumow@gmail.com>: 2009-04-19: initial version
Chris Wuthrich: 7/09: add check of input, not the full list is needed. 10/09: eliminating some bugs.
John Cremona 2014-08-08: tidying of code and docstrings, systematic use of univariate vs. bivariate polynomials and rational functions.
Lorenz Panny (2022-04): major cleanup of code and documentation
Lorenz Panny (2022): inseparable duals
Rémy Oudompheng (2023): implementation of the BMSS algorithm
- class sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny(E, kernel, codomain=None, degree=None, model=None, check=True)#
Bases:
EllipticCurveHom
This class implements separable isogenies of elliptic curves.
Several different algorithms for computing isogenies are available. These include:
Vélu’s Formulas: Vélu’s original formulas for computing isogenies. This algorithm is selected by giving as the
kernel
parameter a single point, or a list of points, generating a finite subgroup.Kohel’s Formulas: Kohel’s original formulas for computing isogenies. This algorithm is selected by giving as the
kernel
parameter a monic polynomial (or a coefficient list) which will define the kernel of the isogeny. Kohel’s algorithm is currently only implemented for cyclic isogenies, with the exception of \([2]\).
INPUT:
E
– an elliptic curve, the domain of the isogeny to initialize.kernel
– a kernel: either a point onE
, a list of points onE
, a monic kernel polynomial, orNone
. If initializing from a domain/codomain, this must beNone
.codomain
– an elliptic curve (default:None
).If
kernel
isNone
, thendegree
must be given as well and the givencodomain
must be the codomain of a cyclic, separable, normalized isogeny of the given degree.If
kernel
is notNone
, then this must be isomorphic to the codomain of the separable isogeny defined bykernel
; in this case, the isogeny is post-composed with an isomorphism so that the codomain equals the given curve.
degree
– an integer (default:None
).If
kernel
isNone
, then this is the degree of the isogeny fromE
tocodomain
.If
kernel
is notNone
, then this is used to determine whether or not to skip a \(\gcd\) of the given kernel polynomial with the two-torsion polynomial ofE
.
model
– a string (default:None
). Supported values (cf.compute_model()
):"minimal"
: IfE
is a curve over the rationals or over a number field, then the codomain is a global minimal model where this exists."short_weierstrass"
: The codomain is a short Weierstrass curve, assuming one exists."montgomery"
: The codomain is an (untwisted) Montgomery curve, assuming one exists over this field.
check
(default:True
) – check whether the input is valid. Setting this toFalse
can lead to significant speedups.
EXAMPLES:
A simple example of creating an isogeny of a field of small characteristic:
sage: E = EllipticCurve(GF(7), [0,0,0,1,0]) sage: phi = EllipticCurveIsogeny(E, E((0,0)) ); phi Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7 sage: phi.degree() == 2 True sage: phi.kernel_polynomial() x sage: phi.rational_maps() ((x^2 + 1)/x, (x^2*y - y)/x^2) sage: phi == loads(dumps(phi)) # known bug True
A more complicated example of a characteristic-2 field:
sage: # needs sage.rings.finite_rings sage: E = EllipticCurve(GF(2^4,'alpha'), [0,0,1,0,1]) sage: P = E((1,1)) sage: phi_v = EllipticCurveIsogeny(E, P); phi_v Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field in alpha of size 2^4 sage: phi_ker_poly = phi_v.kernel_polynomial() sage: phi_ker_poly x + 1 sage: phi_k = EllipticCurveIsogeny(E, phi_ker_poly) sage: phi_k == phi_v True sage: phi_k.rational_maps() ((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1)) sage: phi_v.rational_maps() ((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1)) sage: phi_k.degree() == phi_v.degree() == 3 True sage: phi_k.is_separable() True sage: phi_v(E(0)) (0 : 1 : 0) sage: alpha = E.base_field().gen() sage: Q = E((0, alpha*(alpha + 1))) sage: phi_v(Q) (1 : alpha^2 + alpha : 1) sage: phi_v(P) == phi_k(P) True sage: phi_k(P) == phi_v.codomain()(0) True
We can create an isogeny whose kernel equals the full 2-torsion:
sage: # needs sage.rings.finite_rings sage: E = EllipticCurve(GF((3,2)), [0,0,0,1,1]) sage: ker_poly = E.division_polynomial(2) sage: phi = EllipticCurveIsogeny(E, ker_poly); phi Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 3^2 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in z2 of size 3^2 sage: P1,P2,P3 = filter(bool, E(0).division_points(2)) sage: phi(P1) (0 : 1 : 0) sage: phi(P2) (0 : 1 : 0) sage: phi(P3) (0 : 1 : 0) sage: phi.degree() 4
We can also create trivial isogenies with the trivial kernel:
sage: E = EllipticCurve(GF(17), [11, 11, 4, 12, 10]) sage: phi_v = EllipticCurveIsogeny(E, E(0)) sage: phi_v.degree() 1 sage: phi_v.rational_maps() (x, y) sage: E == phi_v.codomain() True sage: P = E.random_point() sage: phi_v(P) == P True sage: E = EllipticCurve(GF(31), [23, 1, 22, 7, 18]) sage: phi_k = EllipticCurveIsogeny(E, [1]); phi_k Isogeny of degree 1 from Elliptic Curve defined by y^2 + 23*x*y + 22*y = x^3 + x^2 + 7*x + 18 over Finite Field of size 31 to Elliptic Curve defined by y^2 + 23*x*y + 22*y = x^3 + x^2 + 7*x + 18 over Finite Field of size 31 sage: phi_k.degree() 1 sage: phi_k.rational_maps() (x, y) sage: phi_k.codomain() == E True sage: phi_k.kernel_polynomial() 1 sage: P = E.random_point(); P == phi_k(P) True
Vélu and Kohel also work in characteristic \(0\):
sage: E = EllipticCurve(QQ, [0,0,0,3,4]) sage: P_list = E.torsion_points() sage: phi = EllipticCurveIsogeny(E, P_list); phi Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 27*x + 46 over Rational Field sage: P = E((0,2)) sage: phi(P) (6 : -10 : 1) sage: phi_ker_poly = phi.kernel_polynomial() sage: phi_ker_poly x + 1 sage: phi_k = EllipticCurveIsogeny(E, phi_ker_poly); phi_k Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 27*x + 46 over Rational Field sage: phi_k(P) == phi(P) True sage: phi_k == phi True sage: phi_k.degree() 2 sage: phi_k.is_separable() True
A more complicated example over the rationals (of odd degree):
sage: E = EllipticCurve('11a1') sage: P_list = E.torsion_points() sage: phi_v = EllipticCurveIsogeny(E, P_list); phi_v Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field sage: P = E((16,-61)) sage: phi_v(P) (0 : 1 : 0) sage: ker_poly = phi_v.kernel_polynomial(); ker_poly x^2 - 21*x + 80 sage: phi_k = EllipticCurveIsogeny(E, ker_poly); phi_k Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field sage: phi_k == phi_v True sage: phi_v(P) == phi_k(P) True sage: phi_k.is_separable() True
We can also do this same example over the number field defined by the irreducible two-torsion polynomial of \(E\):
sage: # needs sage.rings.number_field sage: E = EllipticCurve('11a1') sage: P_list = E.torsion_points() sage: x = polygen(ZZ, 'x') sage: K.<alpha> = NumberField(x^3 - 2* x^2 - 40*x - 158) sage: EK = E.change_ring(K) sage: P_list = [EK(P) for P in P_list] sage: phi_v = EllipticCurveIsogeny(EK, P_list); phi_v Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 to Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-7820)*x + (-263580) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 sage: P = EK((alpha/2,-1/2)) sage: phi_v(P) (122/121*alpha^2 + 1633/242*alpha - 3920/121 : -1/2 : 1) sage: ker_poly = phi_v.kernel_polynomial() sage: ker_poly x^2 - 21*x + 80 sage: phi_k = EllipticCurveIsogeny(EK, ker_poly); phi_k Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 to Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-7820)*x + (-263580) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 sage: phi_v == phi_k True sage: phi_k(P) == phi_v(P) True sage: phi_k == phi_v True sage: phi_k.degree() 5 sage: phi_v.is_separable() True
The following example shows how to specify an isogeny from domain and codomain:
sage: E = EllipticCurve('11a1') sage: R.<x> = QQ[] sage: f = x^2 - 21*x + 80 sage: phi = E.isogeny(f) sage: E2 = phi.codomain() sage: phi_s = EllipticCurveIsogeny(E, None, E2, 5); phi_s Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field sage: phi_s == phi True sage: phi_s.rational_maps() == phi.rational_maps() True
However, only cyclic normalized isogenies can be constructed this way. The non-cyclic multiplication-by-\(3\) isogeny won’t be found:
sage: E.isogeny(None, codomain=E, degree=9) Traceback (most recent call last): ... ValueError: the two curves are not linked by a cyclic normalized isogeny of degree 9
Non-normalized isogeny also won’t be found:
sage: E2.isogeny(None, codomain=E, degree=5) Traceback (most recent call last): ... ValueError: the two curves are not linked by a cyclic normalized isogeny of degree 5 sage: phihat = phi.dual(); phihat Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field sage: phihat.is_normalized() False
Here an example of a construction of a endomorphisms with cyclic kernel on a CM-curve:
sage: # needs sage.rings.number_field sage: K.<i> = NumberField(x^2 + 1) sage: E = EllipticCurve(K, [1,0]) sage: RK.<X> = K[] sage: f = X^2 - 2/5*i + 1/5 sage: phi= E.isogeny(f) sage: isom = phi.codomain().isomorphism_to(E) sage: phi = isom * phi sage: phi.codomain() == phi.domain() True sage: phi.rational_maps() (((4/25*i + 3/25)*x^5 + (4/5*i - 2/5)*x^3 - x)/(x^4 + (-4/5*i + 2/5)*x^2 + (-4/25*i - 3/25)), ((11/125*i + 2/125)*x^6*y + (-23/125*i + 64/125)*x^4*y + (141/125*i + 162/125)*x^2*y + (3/25*i - 4/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125)))
- dual()#
Return the isogeny dual to this isogeny.
Note
If \(\varphi\colon E \to E'\) is the given isogeny and \(n\) is its degree, then the dual is by definition the unique isogeny \(\hat\varphi\colon E'\to E\) such that the compositions \(\hat\varphi\circ\varphi\) and \(\varphi\circ\hat\varphi\) are the multiplication-by-\(n\) maps on \(E\) and \(E'\), respectively.
EXAMPLES:
sage: E = EllipticCurve('11a1') sage: R.<x> = QQ[] sage: f = x^2 - 21*x + 80 sage: phi = EllipticCurveIsogeny(E, f) sage: phi_hat = phi.dual() sage: phi_hat.domain() == phi.codomain() True sage: phi_hat.codomain() == phi.domain() True sage: (X, Y) = phi.rational_maps() sage: (Xhat, Yhat) = phi_hat.rational_maps() sage: Xm = Xhat.subs(x=X, y=Y) sage: Ym = Yhat.subs(x=X, y=Y) sage: (Xm, Ym) == E.multiplication_by_m(5) True sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) sage: R.<x> = GF(37)[] sage: f = x^3 + x^2 + 28*x + 33 sage: phi = EllipticCurveIsogeny(E, f) sage: phi_hat = phi.dual() sage: phi_hat.codomain() == phi.domain() True sage: phi_hat.domain() == phi.codomain() True sage: (X, Y) = phi.rational_maps() sage: (Xhat, Yhat) = phi_hat.rational_maps() sage: Xm = Xhat.subs(x=X, y=Y) sage: Ym = Yhat.subs(x=X, y=Y) sage: (Xm, Ym) == E.multiplication_by_m(7) True sage: E = EllipticCurve(GF(31), [0,0,0,1,8]) sage: R.<x> = GF(31)[] sage: f = x^2 + 17*x + 29 sage: phi = EllipticCurveIsogeny(E, f) sage: phi_hat = phi.dual() sage: phi_hat.codomain() == phi.domain() True sage: phi_hat.domain() == phi.codomain() True sage: (X, Y) = phi.rational_maps() sage: (Xhat, Yhat) = phi_hat.rational_maps() sage: Xm = Xhat.subs(x=X, y=Y) sage: Ym = Yhat.subs(x=X, y=Y) sage: (Xm, Ym) == E.multiplication_by_m(5) True
Inseparable duals should be computed correctly:
sage: # needs sage.rings.finite_rings sage: z2 = GF(71^2).gen() sage: E = EllipticCurve(j=57*z2+51) sage: E.isogeny(3*E.lift_x(0)).dual() Composite morphism of degree 71 = 71*1^2: From: Elliptic Curve defined by y^2 = x^3 + (32*z2+67)*x + (24*z2+37) over Finite Field in z2 of size 71^2 To: Elliptic Curve defined by y^2 = x^3 + (41*z2+56)*x + (18*z2+42) over Finite Field in z2 of size 71^2 sage: E.isogeny(E.lift_x(0)).dual() Composite morphism of degree 213 = 71*3: From: Elliptic Curve defined by y^2 = x^3 + (58*z2+31)*x + (34*z2+58) over Finite Field in z2 of size 71^2 To: Elliptic Curve defined by y^2 = x^3 + (41*z2+56)*x + (18*z2+42) over Finite Field in z2 of size 71^2
…even if pre- or post-isomorphisms are present:
sage: # needs sage.rings.finite_rings sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism sage: phi = E.isogeny(E.lift_x(0)) sage: pre = ~WeierstrassIsomorphism(phi.domain(), (z2,2,3,4)) sage: post = WeierstrassIsomorphism(phi.codomain(), (5,6,7,8)) sage: phi = post * phi * pre sage: phi.dual() Composite morphism of degree 213 = 71*3: From: Elliptic Curve defined by y^2 + 17*x*y + 45*y = x^3 + 30*x^2 + (6*z2+64)*x + (48*z2+65) over Finite Field in z2 of size 71^2 To: Elliptic Curve defined by y^2 + (60*z2+22)*x*y + (69*z2+37)*y = x^3 + (32*z2+48)*x^2 + (19*z2+58)*x + (56*z2+22) over Finite Field in z2 of size 71^2
- inseparable_degree()#
Return the inseparable degree of this isogeny.
Since this class only implements separable isogenies, this method always returns one.
- kernel_polynomial()#
Return the kernel polynomial of this isogeny.
EXAMPLES:
sage: E = EllipticCurve(QQ, [0,0,0,2,0]) sage: phi = EllipticCurveIsogeny(E, E((0,0))) sage: phi.kernel_polynomial() x sage: E = EllipticCurve('11a1') sage: phi = EllipticCurveIsogeny(E, E.torsion_points()) sage: phi.kernel_polynomial() x^2 - 21*x + 80 sage: E = EllipticCurve(GF(17), [1,-1,1,-1,1]) sage: phi = EllipticCurveIsogeny(E, [1]) sage: phi.kernel_polynomial() 1 sage: E = EllipticCurve(GF(31), [0,0,0,3,0]) sage: phi = EllipticCurveIsogeny(E, [0,3,0,1]) sage: phi.kernel_polynomial() x^3 + 3*x
- rational_maps()#
Return the pair of rational maps defining this isogeny.
Note
Both components are returned as elements of the function field \(F(x,y)\) in two variables over the base field \(F\), though the first only involves \(x\). To obtain the \(x\)-coordinate function as a rational function in \(F(x)\), use
x_rational_map()
.EXAMPLES:
sage: E = EllipticCurve(QQ, [0,2,0,1,-1]) sage: phi = EllipticCurveIsogeny(E, [1]) sage: phi.rational_maps() (x, y) sage: E = EllipticCurve(GF(17), [0,0,0,3,0]) sage: phi = EllipticCurveIsogeny(E, E((0,0))) sage: phi.rational_maps() ((x^2 + 3)/x, (x^2*y - 3*y)/x^2)
- scaling_factor()#
Return the Weierstrass scaling factor associated to this elliptic-curve isogeny.
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 isogeny 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: E = EllipticCurve(GF(257^2), [0,1]) sage: phi = E.isogeny(E.lift_x(240)) sage: phi.degree() 43 sage: phi.scaling_factor() 1 sage: phi.dual().scaling_factor() 43
ALGORITHM: The “inner” isogeny is normalized by construction, so we only need to account for the scaling factors of a pre- and post-isomorphism.
- x_rational_map()#
Return the rational map giving the \(x\)-coordinate of this isogeny.
Note
This function returns the \(x\)-coordinate component of the isogeny as a rational function in \(F(x)\), where \(F\) is the base field. To obtain both coordinate functions as elements of the function field \(F(x,y)\) in two variables, use
rational_maps()
.EXAMPLES:
sage: E = EllipticCurve(QQ, [0,2,0,1,-1]) sage: phi = EllipticCurveIsogeny(E, [1]) sage: phi.x_rational_map() x sage: E = EllipticCurve(GF(17), [0,0,0,3,0]) sage: phi = EllipticCurveIsogeny(E, E((0,0))) sage: phi.x_rational_map() (x^2 + 3)/x
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_codomain_formula(E, v, w)#
Compute the codomain curve given parameters \(v\) and \(w\) (as in Vélu/Kohel/etc. formulas).
INPUT:
E
– an elliptic curvev
,w
– elements of the base field ofE
OUTPUT:
The elliptic curve with invariants \([a_1,a_2,a_3,a_4-5v,a_6-(a_1^2+4a_2)v-7w]\) where \(E = [a_1,a_2,a_3,a_4,a_6]\).
EXAMPLES:
This formula is used by every invocation of the
EllipticCurveIsogeny
constructor:sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: phi = EllipticCurveIsogeny(E, E((1,2)) ) sage: phi.codomain() Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19 sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_formula sage: v = phi._EllipticCurveIsogeny__v sage: w = phi._EllipticCurveIsogeny__w sage: compute_codomain_formula(E, v, w) == phi.codomain() True
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_codomain_kohel(E, kernel)#
Compute the codomain from the kernel polynomial using Kohel’s formulas.
INPUT:
E
– domain elliptic curvekernel
(polynomial or list) – the kernel polynomial, or a list of its coefficients
OUTPUT:
(elliptic curve) The codomain elliptic curve of the isogeny defined by
kernel
.EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_kohel sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: phi = EllipticCurveIsogeny(E, [9,1]) sage: phi.codomain() == isogeny_codomain_from_kernel(E, [9,1]) True sage: compute_codomain_kohel(E, [9,1]) Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19 sage: R.<x> = GF(19)[] sage: E = EllipticCurve(GF(19), [18,17,16,15,14]) sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11) sage: phi.codomain() == isogeny_codomain_from_kernel(E, x^3 + 14*x^2 + 3*x + 11) True sage: compute_codomain_kohel(E, x^3 + 14*x^2 + 3*x + 11) Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19 sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12) sage: isogeny_codomain_from_kernel(E, x^3 + 7*x^2 + 15*x + 12) == phi.codomain() True sage: compute_codomain_kohel(E, x^3 + 7*x^2 + 15*x + 12) Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19
ALGORITHM:
This function uses the formulas of Section 2.4 of [Koh1996].
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_intermediate_curves(E1, E2)#
Return intermediate curves and isomorphisms.
Note
This is used to compute \(\wp\) functions from the short Weierstrass model more easily.
Warning
The base field must be of characteristic not equal to \(2\) or \(3\).
INPUT:
E1
,E2
– elliptic curves
OUTPUT:
A tuple (
pre_isomorphism
,post_isomorphism
,intermediate_domain
,intermediate_codomain
) where:intermediate_domain
is a short Weierstrass curve isomorphic toE1
;intermediate_codomain
is a short Weierstrass curve isomorphic toE2
;pre_isomorphism
is a normalized isomorphism fromE1
tointermediate_domain
;post_isomorphism
is a normalized isomorphism fromintermediate_codomain
toE2
.
EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_intermediate_curves sage: E = EllipticCurve(GF(83), [1,0,1,1,0]) sage: R.<x> = GF(83)[]; f = x + 24 sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: compute_intermediate_curves(E, E2) (Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83, Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83, Elliptic-curve morphism: From: Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 83 To: Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83 Via: (u,r,s,t) = (1, 76, 41, 3), Elliptic-curve morphism: From: Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83 To: Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 16 over Finite Field of size 83 Via: (u,r,s,t) = (1, 7, 42, 42)) sage: # needs sage.rings.number_field sage: R.<x> = QQ[] sage: K.<i> = NumberField(x^2 + 1) sage: E = EllipticCurve(K, [0,0,0,1,0]) sage: E2 = EllipticCurve(K, [0,0,0,16,0]) sage: compute_intermediate_curves(E, E2) (Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1, Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1, Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 Via: (u,r,s,t) = (1, 0, 0, 0), Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 Via: (u,r,s,t) = (1, 0, 0, 0))
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_isogeny_bmss(E1, E2, l)#
Compute the kernel polynomial of the unique normalized isogeny of degree
l
betweenE1
andE2
.Both curves must be given in short Weierstrass form, and the characteristic must be either \(0\) or no smaller than \(4l+4\).
ALGORITHM: [BMSS2006], algorithm fastElkies’.
EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_bmss sage: E1 = EllipticCurve(GF(167), [153, 112]) sage: E2 = EllipticCurve(GF(167), [56, 40]) sage: compute_isogeny_bmss(E1, E2, 13) x^6 + 139*x^5 + 73*x^4 + 139*x^3 + 120*x^2 + 88*x
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm=None)#
Return the kernel polynomial of a cyclic, separable, normalized isogeny of degree
ell
fromE1
toE2
.INPUT:
E1
– domain elliptic curve in short Weierstrass formE2
– codomain elliptic curve in short Weierstrass formell
– the degree of an isogeny fromE1
toE2
algorithm
–None
(default, choose automatically) or"bmss"
(compute_isogeny_bmss()
) or"stark"
(compute_isogeny_stark()
)
OUTPUT:
The kernel polynomial of an isogeny from
E1
toE2
.Note
If there is no degree-
ell
, cyclic, separable, normalized isogeny fromE1
toE2
, aValueError
will be raised.EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_kernel_polynomial sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) sage: R.<x> = GF(37)[] sage: f = (x + 14) * (x + 30) sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: compute_isogeny_kernel_polynomial(E, E2, 5) x^2 + 7*x + 13 sage: f x^2 + 7*x + 13 sage: # needs sage.rings.number_field sage: R.<x> = QQ[] sage: K.<i> = NumberField(x^2 + 1) sage: E = EllipticCurve(K, [0,0,0,1,0]) sage: E2 = EllipticCurve(K, [0,0,0,16,0]) sage: compute_isogeny_kernel_polynomial(E, E2, 4) x^3 + x
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_isogeny_stark(E1, E2, ell)#
Return the kernel polynomial of an isogeny of degree
ell
fromE1
toE2
.INPUT:
E1
– domain elliptic curve in short Weierstrass formE2
– codomain elliptic curve in short Weierstrass formell
– the degree of an isogeny fromE1
toE2
OUTPUT:
The kernel polynomial of an isogeny from
E1
toE2
.Note
If there is no degree-
ell
, cyclic, separable, normalized isogeny fromE1
toE2
, aValueError
will be raised.ALGORITHM:
This function uses Stark’s algorithm as presented in Section 6.2 of [BMSS2006].
Note
As published in [BMSS2006], the algorithm is incorrect, and a correct version (with slightly different notation) can be found in [Mo2009]. The algorithm originates in [Sta1973].
EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_stark, compute_sequence_of_maps sage: E = EllipticCurve(GF(97), [1,0,1,1,0]) sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21 sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: isom1, isom2, E1pr, E2pr, ker_poly = compute_sequence_of_maps(E, E2, 11) sage: compute_isogeny_stark(E1pr, E2pr, 11) x^10 + 37*x^9 + 53*x^8 + 66*x^7 + 66*x^6 + 17*x^5 + 57*x^4 + 6*x^3 + 89*x^2 + 53*x + 8 sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) sage: R.<x> = GF(37)[] sage: f = (x + 14) * (x + 30) sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: compute_isogeny_stark(E, E2, 5) x^4 + 14*x^3 + x^2 + 34*x + 21 sage: f**2 x^4 + 14*x^3 + x^2 + 34*x + 21 sage: E = EllipticCurve(QQ, [0,0,0,1,0]) sage: R.<x> = QQ[] sage: f = x sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: compute_isogeny_stark(E, E2, 2) x
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_sequence_of_maps(E1, E2, ell)#
Return intermediate curves, isomorphisms and kernel polynomial.
INPUT:
E1
,E2
– elliptic curvesell
– a prime such that there is a degree-ell
separable normalized isogeny fromE1
toE2
OUTPUT:
A tuple (
pre_isom
,post_isom
,E1pr
,E2pr
,ker_poly
) where:E1pr
is an elliptic curve in short Weierstrass form isomorphic toE1
;E2pr
is an elliptic curve in short Weierstrass form isomorphic toE2
;pre_isom
is a normalized isomorphism fromE1
toE1pr
;post_isom
is a normalized isomorphism fromE2pr
toE2
;ker_poly
is the kernel polynomial of anell
-isogeny fromE1pr
toE2pr
.
EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_sequence_of_maps sage: E = EllipticCurve('11a1') sage: R.<x> = QQ[]; f = x^2 - 21*x + 80 sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: compute_sequence_of_maps(E, E2, 5) (Elliptic-curve morphism: From: Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field To: Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field Via: (u,r,s,t) = (1, 1/3, 0, -1/2), Elliptic-curve morphism: From: Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field To: Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field Via: (u,r,s,t) = (1, -1/3, 0, 1/2), Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field, Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field, x^2 - 61/3*x + 658/9) sage: # needs sage.rings.number_field sage: K.<i> = NumberField(x^2 + 1) sage: E = EllipticCurve(K, [0,0,0,1,0]) sage: E2 = EllipticCurve(K, [0,0,0,16,0]) sage: compute_sequence_of_maps(E, E2, 4) (Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 Via: (u,r,s,t) = (1, 0, 0, 0), Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 Via: (u,r,s,t) = (1, 0, 0, 0), Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1, Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1, x^3 + x) sage: E = EllipticCurve(GF(97), [1,0,1,1,0]) sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21 sage: phi = EllipticCurveIsogeny(E, f) sage: E2 = phi.codomain() sage: compute_sequence_of_maps(E, E2, 11) (Elliptic-curve morphism: From: Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 97 To: Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97 Via: (u,r,s,t) = (1, 8, 48, 44), Elliptic-curve morphism: From: Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97 To: Elliptic Curve defined by y^2 + x*y + y = x^3 + 87*x + 26 over Finite Field of size 97 Via: (u,r,s,t) = (1, 89, 49, 49), Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97, Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97, x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69)
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4)#
Compute Vélu’s \((v,w)\) using Kohel’s formulas for isogenies of degree exactly divisible by \(2\).
INPUT:
x0
,y0
– coordinates of a 2-torsion point on an elliptic curve \(E\)a1
,a2
,a4
– invariants of \(E\)
OUTPUT:
(tuple) Vélu’s isogeny parameters \((v,w)\).
EXAMPLES:
This function will be implicitly called by the following example:
sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: phi = EllipticCurveIsogeny(E, [9,1]); phi Isogeny of degree 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 19 to Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19 sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg1 sage: a1,a2,a3,a4,a6 = E.a_invariants() sage: x0 = -9 sage: y0 = -(a1*x0 + a3)/2 sage: compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4) (18, 9)
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_vw_kohel_even_deg3(b2, b4, s1, s2, s3)#
Compute Vélu’s \((v,w)\) using Kohel’s formulas for isogenies of degree divisible by \(4\).
INPUT:
b2
,b4
– invariants of an elliptic curve \(E\)s1
,s2
,s3
– signed coefficients of the 2-division polynomial of \(E\)
OUTPUT:
(tuple) Vélu’s isogeny parameters \((v,w)\).
EXAMPLES:
This function will be implicitly called by the following example:
sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: R.<x> = GF(19)[] sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12); phi Isogeny of degree 4 from Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 19 to Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19 sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg3 sage: b2,b4 = E.b2(), E.b4() sage: s1, s2, s3 = -7, 15, -12 sage: compute_vw_kohel_even_deg3(b2, b4, s1, s2, s3) (4, 7)
- sage.schemes.elliptic_curves.ell_curve_isogeny.compute_vw_kohel_odd(b2, b4, b6, s1, s2, s3, n)#
Compute Vélu’s \((v,w)\) using Kohel’s formulas for isogenies of odd degree.
INPUT:
b2
,b4
,b6
– invariants of an elliptic curve \(E\)s1
,s2
,s3
– signed coefficients of lowest powers of \(x\) in the kernel polynomialn
(integer) – the degree
OUTPUT:
(tuple) Vélu’s isogeny parameters \((v,w)\).
EXAMPLES:
This function will be implicitly called by the following example:
sage: E = EllipticCurve(GF(19), [18,17,16,15,14]) sage: R.<x> = GF(19)[] sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11); phi Isogeny of degree 7 from Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 15*x + 14 over Finite Field of size 19 to Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19 sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_odd sage: b2,b4,b6 = E.b2(), E.b4(), E.b6() sage: s1,s2,s3 = -14,3,-11 sage: compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,3) (7, 1)
- sage.schemes.elliptic_curves.ell_curve_isogeny.fill_isogeny_matrix(M)#
Return a filled isogeny matrix giving all degrees from one giving only prime degrees.
INPUT:
M
– a square symmetric matrix whose off-diagonal \(i\), \(j\) entry is either a prime \(l\) if the \(i\)’th and \(j\)’th curves have an \(l\)-isogeny between them, otherwise \(0\)
OUTPUT:
(matrix) A square matrix with entries \(1\) on the diagonal, and in general the \(i\), \(j\) entry is \(d>0\) if \(d\) is the minimal degree of an isogeny from the \(i\)’th to the \(j\)’th curve.
EXAMPLES:
sage: M = Matrix([[0, 2, 3, 3, 0, 0], [2, 0, 0, 0, 3, 3], [3, 0, 0, 0, 2, 0], ....: [3, 0, 0, 0, 0, 2], [0, 3, 2, 0, 0, 0], [0, 3, 0, 2, 0, 0]]); M [0 2 3 3 0 0] [2 0 0 0 3 3] [3 0 0 0 2 0] [3 0 0 0 0 2] [0 3 2 0 0 0] [0 3 0 2 0 0] sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix sage: fill_isogeny_matrix(M) [ 1 2 3 3 6 6] [ 2 1 6 6 3 3] [ 3 6 1 9 2 18] [ 3 6 9 1 18 2] [ 6 3 2 18 1 9] [ 6 3 18 2 9 1]
- sage.schemes.elliptic_curves.ell_curve_isogeny.isogeny_codomain_from_kernel(E, kernel)#
Compute the isogeny codomain given a kernel.
INPUT:
E
– domain elliptic curvekernel
– either a list of points in the kernel of the isogeny,or a kernel polynomial (specified as either a univariate polynomial or a coefficient list)
OUTPUT:
(elliptic curve) The codomain of the separable normalized isogeny defined by this kernel.
EXAMPLES:
sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_codomain_from_kernel sage: E = EllipticCurve(GF(7), [1,0,1,0,1]) sage: R.<x> = GF(7)[] sage: isogeny_codomain_from_kernel(E, [4,1]) Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7 sage: (EllipticCurveIsogeny(E, [4,1]).codomain() ....: == isogeny_codomain_from_kernel(E, [4,1])) True sage: isogeny_codomain_from_kernel(E, x^3 + x^2 + 4*x + 3) Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7 sage: isogeny_codomain_from_kernel(E, x^3 + 2*x^2 + 4*x + 3) Elliptic Curve defined by y^2 + x*y + y = x^3 + 5*x + 2 over Finite Field of size 7 sage: # needs sage.rings.finite_rings sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: kernel_list = [E((15,10)), E((10,3)), E((6,5))] sage: isogeny_codomain_from_kernel(E, kernel_list) Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19
- sage.schemes.elliptic_curves.ell_curve_isogeny.two_torsion_part(E, psi)#
Return the greatest common divisor of
psi
and the 2-torsion polynomial of \(E\).INPUT:
E
– an elliptic curvepsi
– a univariate polynomial over the base field ofE
OUTPUT:
(polynomial) The \(\gcd\) of
psi
and the 2-torsion polynomial ofE
.EXAMPLES:
Every function that computes the kernel polynomial via Kohel’s formulas will call this function:
sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) sage: R.<x> = GF(19)[] sage: phi = EllipticCurveIsogeny(E, x + 13) sage: isogeny_codomain_from_kernel(E, x + 13) == phi.codomain() True sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part sage: two_torsion_part(E, x + 13) x + 13
- sage.schemes.elliptic_curves.ell_curve_isogeny.unfill_isogeny_matrix(M)#
Reverses the action of
fill_isogeny_matrix
.INPUT:
M
– a square symmetric matrix of integers
OUTPUT:
(matrix) A square symmetric matrix obtained from
M
by replacing non-prime entries with \(0\).EXAMPLES:
sage: M = Matrix([[0, 2, 3, 3, 0, 0], [2, 0, 0, 0, 3, 3], [3, 0, 0, 0, 2, 0], ....: [3, 0, 0, 0, 0, 2], [0, 3, 2, 0, 0, 0], [0, 3, 0, 2, 0, 0]]); M [0 2 3 3 0 0] [2 0 0 0 3 3] [3 0 0 0 2 0] [3 0 0 0 0 2] [0 3 2 0 0 0] [0 3 0 2 0 0] sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix, unfill_isogeny_matrix sage: M1 = fill_isogeny_matrix(M); M1 [ 1 2 3 3 6 6] [ 2 1 6 6 3 3] [ 3 6 1 9 2 18] [ 3 6 9 1 18 2] [ 6 3 2 18 1 9] [ 6 3 18 2 9 1] sage: unfill_isogeny_matrix(M1) [0 2 3 3 0 0] [2 0 0 0 3 3] [3 0 0 0 2 0] [3 0 0 0 0 2] [0 3 2 0 0 0] [0 3 0 2 0 0] sage: unfill_isogeny_matrix(M1) == M True