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:

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

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 on E, a list of points on E, a monic kernel polynomial, or None. If initializing from a domain/codomain, this must be None.

• codomain – an elliptic curve (default: None).

• If kernel is None, then degree must be given as well and the given codomain must be the codomain of a cyclic, separable, normalized isogeny of the given degree.

• If kernel is not None, then this must be isomorphic to the codomain of the separable isogeny defined by kernel; 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 is None, then this is the degree of the isogeny from E to codomain.

• If kernel is not None, then this is used to determine whether or not to skip a $$\gcd$$ of the given kernel polynomial with the two-torsion polynomial of E.

• model – a string (default: None). Supported values (cf. compute_model()):

• "minimal": If E 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 to False 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 curve

• v, w – elements of the base field of E

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 curve

• kernel (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 to E1;

• intermediate_codomain is a short Weierstrass curve isomorphic to E2;

• pre_isomorphism is a normalized isomorphism from E1 to intermediate_domain;

• post_isomorphism is a normalized isomorphism from intermediate_codomain to E2.

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 between E1 and E2.

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 from E1 to E2.

INPUT:

• E1 – domain elliptic curve in short Weierstrass form

• E2 – codomain elliptic curve in short Weierstrass form

• ell – the degree of an isogeny from E1 to E2

• algorithmNone (default, choose automatically) or

"bmss" (compute_isogeny_bmss()) or "stark" (compute_isogeny_stark())

OUTPUT:

The kernel polynomial of an isogeny from E1 to E2.

Note

If there is no degree-ell, cyclic, separable, normalized isogeny from E1 to E2, a ValueError 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 from E1 to E2.

INPUT:

• E1 – domain elliptic curve in short Weierstrass form

• E2 – codomain elliptic curve in short Weierstrass form

• ell – the degree of an isogeny from E1 to E2

OUTPUT:

The kernel polynomial of an isogeny from E1 to E2.

Note

If there is no degree-ell, cyclic, separable, normalized isogeny from E1 to E2, a ValueError 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 curves

• ell – a prime such that there is a degree-ell separable normalized isogeny from E1 to E2

OUTPUT:

A tuple (pre_isom, post_isom, E1pr, E2pr, ker_poly) where:

• E1pr is an elliptic curve in short Weierstrass form isomorphic to E1;

• E2pr is an elliptic curve in short Weierstrass form isomorphic to E2;

• pre_isom is a normalized isomorphism from E1 to E1pr;

• post_isom is a normalized isomorphism from E2pr to E2;

• ker_poly is the kernel polynomial of an ell-isogeny from E1pr to E2pr.

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 polynomial

• n (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 curve

• kernel – 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 curve

• psi – a univariate polynomial over the base field of E

OUTPUT:

(polynomial) The $$\gcd$$ of psi and the 2-torsion polynomial of E.

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