Elliptic-curve morphisms#

This class serves as a common parent for various specializations of morphisms between elliptic curves, with the aim of providing a common interface regardless of implementation details.

Current implementations of elliptic-curve morphisms (child classes):

AUTHORS:

class sage.schemes.elliptic_curves.hom.EllipticCurveHom(*args, **kwds)#

Bases: Morphism

Base class for elliptic-curve morphisms.

as_morphism()#

Return self as a morphism of projective schemes.

EXAMPLES:

sage: k = GF(11)
sage: E = EllipticCurve(k, [1,1])
sage: Q = E(6,5)
sage: phi = E.isogeny(Q)
sage: mor = phi.as_morphism()
sage: mor.domain() == E
True
sage: mor.codomain() == phi.codomain()
True
sage: mor(Q) == phi(Q)
True
characteristic_polynomial()#

Return the characteristic polynomial of this elliptic-curve morphism, which must be an endomorphism.

See also

EXAMPLES:

sage: E = EllipticCurve(QQ, [42, 42])
sage: m5 = E.scalar_multiplication(5)
sage: m5.characteristic_polynomial()
x^2 - 10*x + 25
sage: E = EllipticCurve(GF(71), [42, 42])
sage: pi = E.frobenius_endomorphism()
sage: pi.characteristic_polynomial()
x^2 - 8*x + 71
sage: E.frobenius().charpoly()
x^2 - 8*x + 71
degree()#

Return the degree of this elliptic-curve morphism.

EXAMPLES:

sage: E = EllipticCurve(QQ, [0,0,0,1,0])
sage: phi = EllipticCurveIsogeny(E, E((0,0)))
sage: phi.degree()
2
sage: phi = EllipticCurveIsogeny(E, [0,1,0,1])
sage: phi.degree()
4

sage: E = EllipticCurve(GF(31), [1,0,0,1,2])
sage: phi = EllipticCurveIsogeny(E, [17, 1])
sage: phi.degree()
3

Degrees are multiplicative, so the degree of a composite isogeny is the product of the degrees of the individual factors:

sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: E = EllipticCurve(GF(419), [1,0])
sage: P, = E.gens()
sage: phi = EllipticCurveHom_composite(E, P+P)
sage: phi.degree()
210
sage: phi.degree() == prod(f.degree() for f in phi.factors())
True

Isomorphisms always have degree \(1\) by definition:

sage: E1 = EllipticCurve([1,2,3,4,5])
sage: E2 = EllipticCurve_from_j(E1.j_invariant())
sage: E1.isomorphism_to(E2).degree()
1
dual()#

Return the dual of this elliptic-curve morphism.

Implemented by child classes. For examples, see:

formal(prec=20)#

Return the formal isogeny associated to this elliptic-curve morphism as a power series in the variable \(t=-x/y\) on the domain curve.

INPUT:

  • prec – (default: 20), the precision with which the computations in the formal group are carried out.

EXAMPLES:

sage: E = EllipticCurve(GF(13),[1,7])
sage: phi = E.isogeny(E(10,4))
sage: phi.formal()
t + 12*t^13 + 2*t^17 + 8*t^19 + 2*t^21 + O(t^23)
sage: E = EllipticCurve([0,1])
sage: phi = E.isogeny(E(2,3))
sage: phi.formal(prec=10)
t + 54*t^5 + 255*t^7 + 2430*t^9 + 19278*t^11 + O(t^13)
sage: E = EllipticCurve('11a2')
sage: R.<x> = QQ[]
sage: phi = E.isogeny(x^2 + 101*x + 12751/5)
sage: phi.formal(prec=7)
t - 2724/5*t^5 + 209046/5*t^7 - 4767/5*t^8 + 29200946/5*t^9 + O(t^10)
inseparable_degree()#

Return the inseparable degree of this isogeny.

Implemented by child classes. For examples, see:

is_injective()#

Determine whether or not this morphism has trivial kernel.

The kernel is trivial if and only if this morphism is a purely inseparable isogeny.

EXAMPLES:

sage: E = EllipticCurve('11a1')
sage: R.<x> = QQ[]
sage: f = x^2 + x - 29/5
sage: phi = EllipticCurveIsogeny(E, f)
sage: phi.is_injective()
False
sage: phi = EllipticCurveIsogeny(E, R(1))
sage: phi.is_injective()
True
sage: F = GF(7)
sage: E = EllipticCurve(j=F(0))
sage: phi = EllipticCurveIsogeny(E, [ E((0,-1)), E((0,1))])
sage: phi.is_injective()
False
sage: phi = EllipticCurveIsogeny(E, E(0))
sage: phi.is_injective()
True
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
sage: E = EllipticCurve(GF(23), [1,0])
sage: E.scalar_multiplication(4).is_injective()
False
sage: E.scalar_multiplication(5).is_injective()
False
sage: E.scalar_multiplication(1).is_injective()
True
sage: E.scalar_multiplication(-1).is_injective()
True
sage: E.scalar_multiplication(23).is_injective()
True
sage: E.scalar_multiplication(-23).is_injective()
True
sage: E.scalar_multiplication(0).is_injective()
False
sage: from sage.schemes.elliptic_curves.hom_frobenius import EllipticCurveHom_frobenius
sage: E = EllipticCurve(GF(11), [1,1])
sage: pi = EllipticCurveHom_frobenius(E, 5)
sage: pi.is_injective()
True
is_normalized()#

Determine whether this morphism is a normalized isogeny.

Note

An isogeny \(\varphi\colon E_1\to E_2\) between two given Weierstrass equations is said to be normalized if the \(\varphi^*(\omega_2) = \omega_1\), where \(\omega_1\) and \(\omega_2\) are the invariant differentials on \(E_1\) and \(E_2\) corresponding to the given equation.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
sage: R.<x> = GF(7)[]
sage: phi = EllipticCurveIsogeny(E, x)
sage: phi.is_normalized()
True
sage: isom = WeierstrassIsomorphism(phi.codomain(), (3, 0, 0, 0))
sage: phi = isom * phi
sage: phi.is_normalized()
False
sage: isom = WeierstrassIsomorphism(phi.codomain(), (5, 0, 0, 0))
sage: phi = isom * phi
sage: phi.is_normalized()
True
sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
sage: phi = isom * phi
sage: phi.is_normalized()
True
sage: F = GF(2^5, 'alpha'); alpha = F.gen()
sage: E = EllipticCurve(F, [1,0,1,1,1])
sage: R.<x> = F[]
sage: phi = EllipticCurveIsogeny(E, x+1)
sage: isom = WeierstrassIsomorphism(phi.codomain(), (alpha, 0, 0, 0))
sage: phi.is_normalized()
True
sage: phi = isom * phi
sage: phi.is_normalized()
False
sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/alpha, 0, 0, 0))
sage: phi = isom * phi
sage: phi.is_normalized()
True
sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
sage: phi = isom * phi
sage: phi.is_normalized()
True
sage: E = EllipticCurve('11a1')
sage: R.<x> = QQ[]
sage: f = x^3 - x^2 - 10*x - 79/4
sage: phi = EllipticCurveIsogeny(E, f)
sage: isom = WeierstrassIsomorphism(phi.codomain(), (2, 0, 0, 0))
sage: phi.is_normalized()
True
sage: phi = isom * phi
sage: phi.is_normalized()
False
sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/2, 0, 0, 0))
sage: phi = isom * phi
sage: phi.is_normalized()
True
sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
sage: phi = isom * phi
sage: phi.is_normalized()
True

ALGORITHM: We check if scaling_factor() returns \(1\).

is_separable()#

Determine whether or not this morphism is a separable isogeny.

EXAMPLES:

sage: E = EllipticCurve(GF(17), [0,0,0,3,0])
sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
sage: phi.is_separable()
True
sage: E = EllipticCurve('11a1')
sage: phi = EllipticCurveIsogeny(E, E.torsion_points())
sage: phi.is_separable()
True
sage: E = EllipticCurve(GF(31337), [0,1])                                   # needs sage.rings.finite_rings
sage: {f.is_separable() for f in E.automorphisms()}                         # needs sage.rings.finite_rings
{True}
sage: # needs sage.rings.finite_rings
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:
  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
sage: E = EllipticCurve(GF(11), [4,4])
sage: E.scalar_multiplication(11).is_separable()
False
sage: E.scalar_multiplication(-11).is_separable()
False
sage: E.scalar_multiplication(777).is_separable()
True
sage: E.scalar_multiplication(-1).is_separable()
True
sage: E.scalar_multiplication(77).is_separable()
False
sage: E.scalar_multiplication(121).is_separable()
False
sage: from sage.schemes.elliptic_curves.hom_frobenius import EllipticCurveHom_frobenius
sage: E = EllipticCurve(GF(11), [1,1])
sage: pi = EllipticCurveHom_frobenius(E)
sage: pi.degree()
11
sage: pi.is_separable()
False
sage: pi = EllipticCurveHom_frobenius(E, 0)
sage: pi.degree()
1
sage: pi.is_separable()
True
sage: E = EllipticCurve(GF(17), [0,0,0,3,0])
sage: phi = E.isogeny(E((1,2)), algorithm='velusqrt')
sage: phi.is_separable()
True
is_surjective()#

Determine whether or not this morphism is surjective.

EXAMPLES:

sage: E = EllipticCurve('11a1')
sage: R.<x> = QQ[]
sage: f = x^2 + x - 29/5
sage: phi = EllipticCurveIsogeny(E, f)
sage: phi.is_surjective()
True
sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
sage: phi.is_surjective()
True
sage: F = GF(2^5, 'omega')
sage: E = EllipticCurve(j=F(0))
sage: R.<x> = F[]
sage: phi = EllipticCurveIsogeny(E, x)
sage: phi.is_surjective()
True
is_zero()#

Check whether this elliptic-curve morphism is the zero map.

EXAMPLES:

sage: E = EllipticCurve(j=GF(7)(0))
sage: phi = EllipticCurveIsogeny(E, [E(0,1), E(0,-1)])
sage: phi.is_zero()
False
kernel_polynomial()#

Return the kernel polynomial of this elliptic-curve morphism.

Implemented by child classes. For examples, see:

matrix_on_subgroup(domain_gens, codomain_gens=None)#

Return the matrix by which this isogeny acts on the \(n\)-torsion subgroup with respect to the given bases.

INPUT:

  • domain_gens – basis \((P,Q)\) of some \(n\)-torsion subgroup on the domain of this elliptic-curve morphism

  • codomain_gens – basis \((R,S)\) of the \(n\)-torsion on the codomain of this morphism, or (default) None if self is an endomorphism

OUTPUT:

A \(2\times 2\) matrix \(M\) over \(\ZZ/n\), such that the image of any point \([a]P + [b]Q\) under this morphism equals \([c]R + [d]S\) where \((c\ d)^T = (a\ b) M\).

EXAMPLES:

sage: F.<i> = GF(419^2, modulus=[1,0,1])
sage: E = EllipticCurve(F, [1,0])
sage: P = E(3, 176*i)
sage: Q = E(i+7, 67*i+48)
sage: P.weil_pairing(Q, 420).multiplicative_order()
420
sage: iota = E.automorphisms()[2]; iota
Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 419^2
  Via:  (u,r,s,t) = (i, 0, 0, 0)
sage: iota^2 == E.scalar_multiplication(-1)
True
sage: mat = iota.matrix_on_subgroup((P,Q)); mat
[301 386]
[ 83 119]
sage: mat.parent()
Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 420
sage: iota(P) == 301*P + 386*Q
True
sage: iota(Q) == 83*P + 119*Q
True
sage: a,b = 123, 456
sage: c,d = vector((a,b)) * mat; (c,d)
(111, 102)
sage: iota(a*P + b*Q) == c*P + d*Q
True

One important application of this is to compute generators of the kernel subgroup of an isogeny, when the \(n\)-torsion subgroup containing the kernel is accessible:

sage: K = E(83*i-16, 9*i-147)
sage: K.order()
7
sage: phi = E.isogeny(K)
sage: R,S = phi.codomain().gens()
sage: mat = phi.matrix_on_subgroup((P,Q), (R,S))
sage: mat  # random -- depends on R,S
[124 263]
[115 141]
sage: kermat = mat.left_kernel_matrix(); kermat
[300  60]
sage: ker = [ZZ(v[0])*P + ZZ(v[1])*Q for v in kermat]
sage: {phi(T) for T in ker}
{(0 : 1 : 0)}
sage: phi == E.isogeny(ker)
True

We can also compute the matrix of a Frobenius endomorphism (EllipticCurveHom_frobenius) on a large enough subgroup to verify point-counting results:

sage: F.<a> = GF((101, 36))
sage: E = EllipticCurve(GF(101), [1,1])
sage: EE = E.change_ring(F)
sage: P,Q = EE.torsion_basis(37)
sage: pi = EE.frobenius_isogeny()
sage: M = pi.matrix_on_subgroup((P,Q))
sage: M.parent()
Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 37
sage: M.trace()
34
sage: E.trace_of_frobenius()
-3

See also

To compute a basis of the \(n\)-torsion, you may use torsion_basis().

rational_maps()#

Return the pair of explicit rational maps defining this elliptic-curve morphism as fractions of bivariate polynomials in \(x\) and \(y\).

Implemented by child classes. For examples, see:

scaling_factor()#

Return the Weierstrass scaling factor associated to this elliptic-curve 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)\).

Implemented by child classes. For examples, see:

separable_degree()#

Return the separable degree of this isogeny.

The separable degree is the result of dividing the degree() by the inseparable_degree().

EXAMPLES:

sage: E = EllipticCurve(GF(11), [5,5])
sage: E.is_supersingular()
False
sage: E.scalar_multiplication(-77).separable_degree()
539
sage: E = EllipticCurve(GF(11), [5,0])
sage: E.is_supersingular()
True
sage: E.scalar_multiplication(-77).separable_degree()
49
trace()#

Return the trace of this elliptic-curve morphism, which must be an endomorphism.

ALGORITHM: compute_trace_generic()

EXAMPLES:

sage: E = EllipticCurve(QQ, [42, 42])
sage: m5 = E.scalar_multiplication(5)
sage: m5.trace()
10
sage: E = EllipticCurve(GF(71^2), [45, 45])
sage: P = E.lift_x(27)
sage: P.order()
71
sage: tau = E.isogeny(P, codomain=E)
sage: tau.trace()
-1
x_rational_map()#

Return the \(x\)-coordinate rational map of this elliptic-curve morphism as a univariate rational expression in \(x\).

Implemented by child classes. For examples, see:

sage.schemes.elliptic_curves.hom.compare_via_evaluation(left, right)#

Test if two elliptic-curve morphisms are equal by evaluating them at enough points.

INPUT:

ALGORITHM:

We use the fact that two isogenies of equal degree \(d\) must be the same if and only if they behave identically on more than \(4d\) points. (It suffices to check this on a few points that generate a large enough subgroup.)

If the domain curve does not have sufficiently many rational points, the base field is extended first: Taking an extension of degree \(O(\log(d))\) suffices.

EXAMPLES:

sage: E = EllipticCurve(GF(83), [1,0])
sage: phi = E.isogeny(12*E.0, model='montgomery'); phi
Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 83 to Elliptic Curve defined by y^2 = x^3 + 70*x^2 + x over Finite Field of size 83
sage: psi = phi.dual(); psi
Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 70*x^2 + x over Finite Field of size 83 to Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 83
sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: mu = EllipticCurveHom_composite.from_factors([phi, psi])
sage: from sage.schemes.elliptic_curves.hom import compare_via_evaluation
sage: compare_via_evaluation(mu, E.scalar_multiplication(7))
True

See also

  • sage.schemes.elliptic_curves.hom_composite.EllipticCurveHom_composite._richcmp_()

sage.schemes.elliptic_curves.hom.compute_trace_generic(phi)#

Compute the trace of the given elliptic-curve endomorphism.

ALGORITHM: Simple variant of Schoof’s algorithm. For enough small primes \(\ell\), we find an order-\(\ell\) point \(P\) on \(E\) and use a discrete-logarithm calculation to find the unique scalar \(t_\ell \in \{0,...,\ell-1\}\) such that \(\varphi^2(P)+[\deg(\varphi)]P = [t_\ell]\varphi(P)\). Then \(t_\ell\) equals the trace of \(\varphi\) modulo \(\ell\), which can therefore be recovered using the Chinese remainder theorem.

EXAMPLES:

It works over finite fields:

sage: from sage.schemes.elliptic_curves.hom import compute_trace_generic
sage: E = EllipticCurve(GF(31337), [1,1])
sage: compute_trace_generic(E.frobenius_endomorphism())
314

It works over \(\QQ\):

sage: from sage.schemes.elliptic_curves.hom import compute_trace_generic
sage: E = EllipticCurve(QQ, [1,2,3,4,5])
sage: dbl = E.scalar_multiplication(2)
sage: compute_trace_generic(dbl)
4

It works over number fields (for a CM curve):

sage: from sage.schemes.elliptic_curves.hom import compute_trace_generic
sage: x = polygen(QQ)
sage: K.<t> = NumberField(5*x^2 - 2*x + 1)
sage: E = EllipticCurve(K, [1,0])
sage: phi = E.isogeny([t,0,1], codomain=E)  # phi = 2 + i
sage: compute_trace_generic(phi)
4
sage.schemes.elliptic_curves.hom.find_post_isomorphism(phi, psi)#

Given two isogenies \(\phi: E\to E'\) and \(\psi: E\to E''\) which are equal up to post-isomorphism defined over the same field, find that isomorphism.

In other words, this function computes an isomorphism \(\alpha: E'\to E''\) such that \(\alpha\circ\phi = \psi\).

ALGORITHM:

Start with a list of all isomorphisms \(E'\to E''\). Then repeatedly evaluate \(\phi\) and \(\psi\) at random points \(P\) to filter the list for isomorphisms \(\alpha\) with \(\alpha(\phi(P)) = \psi(P)\). Once only one candidate is left, return it. Periodically extend the base field to avoid getting stuck (say, if all candidate isomorphisms act the same on all rational points).

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom import find_post_isomorphism
sage: E = EllipticCurve(GF(7^2), [1,0])
sage: f = E.scalar_multiplication(1)
sage: g = choice(E.automorphisms())
sage: find_post_isomorphism(f, g) == g
True
sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
sage: from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
sage: x = polygen(ZZ, 'x')
sage: F.<i> = GF(883^2, modulus=x^2+1)
sage: E = EllipticCurve(F, [1,0])
sage: P = E.lift_x(117)
sage: Q = E.lift_x(774)
sage: w = WeierstrassIsomorphism(E, [i,0,0,0])
sage: phi = EllipticCurveHom_composite(E, [P,w(Q)]) * w
sage: psi = EllipticCurveHom_composite(E, [Q,w(P)])
sage: phi.kernel_polynomial() == psi.kernel_polynomial()
True
sage: find_post_isomorphism(phi, psi)
Elliptic-curve morphism:
  From: Elliptic Curve defined by y^2 = x^3 + 320*x + 482 over Finite Field in i of size 883^2
  To:   Elliptic Curve defined by y^2 = x^3 + 320*x + 401 over Finite Field in i of size 883^2
  Via:  (u,r,s,t) = (882*i, 0, 0, 0)