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

• EllipticCurveIsogeny

• WeierstrassIsomorphism

• EllipticCurveHom_composite

• EllipticCurveHom_scalar

• EllipticCurveHom_frobenius

• EllipticCurveHom_velusqrt

AUTHORS:

• See authors of EllipticCurveIsogeny. Some of the code in this class was lifted from there.

• Lorenz Panny (2021): Refactor isogenies and isomorphisms into the common EllipticCurveHom interface.

• Lorenz Panny (2022): matrix_on_subgroup()

• Lorenz Panny (2023): trace(), characteristic_polynomial()

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

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

characteristic_polynomial()

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

See also

• degree()

• trace()

EXAMPLES:

sage: E = EllipticCurve(QQ, [42, 42])
sage: m5 = E.scalar_multiplication(5)
sage: m5.characteristic_polynomial()
x^2 - 10*x + 25

E = EllipticCurve(QQ, [42, 42])
m5 = E.scalar_multiplication(5)
m5.characteristic_polynomial()

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

E = EllipticCurve(GF(71), [42, 42])
pi = E.frobenius_endomorphism()
pi.characteristic_polynomial()
E.frobenius().charpoly()

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

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

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

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

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

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

dual()

Return the dual of this elliptic-curve morphism.

Implemented by child classes. For examples, see:

• EllipticCurveIsogeny.dual()

• sage.schemes.elliptic_curves.weierstrass_morphism.WeierstrassIsomorphism.dual()

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

• sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar.dual()

• sage.schemes.elliptic_curves.hom_frobenius.EllipticCurveHom_frobenius.dual()

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)

E = EllipticCurve(GF(13),[1,7])
phi = E.isogeny(E(10,4))
phi.formal()

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)

E = EllipticCurve([0,1])
phi = E.isogeny(E(2,3))
phi.formal(prec=10)

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)

E = EllipticCurve('11a2')
R.<x> = QQ[]
phi = E.isogeny(x^2 + 101*x + 12751/5)
phi.formal(prec=7)

is_injective()

Determine whether or not this morphism has trivial kernel.

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

E = EllipticCurve('11a1')
R.<x> = QQ[]
f = x^2 + x - 29/5
phi = EllipticCurveIsogeny(E, f)
phi.is_injective()
phi = EllipticCurveIsogeny(E, R(1))
phi.is_injective()

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

F = GF(7)
E = EllipticCurve(j=F(0))
phi = EllipticCurveIsogeny(E, [ E((0,-1)), E((0,1))])
phi.is_injective()
phi = EllipticCurveIsogeny(E, E(0))
phi.is_injective()

is_normalized()

Determine whether this morphism is a normalized isogeny.

Note

An isogeny $\phi :E_1\to E_2$ between two given Weierstrass equations is said to be normalized if the ${\phi }^{\ast }({\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

from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
E = EllipticCurve(GF(7), [0,0,0,1,0])
R.<x> = GF(7)[]
phi = EllipticCurveIsogeny(E, x)
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (3, 0, 0, 0))
phi = isom * phi
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (5, 0, 0, 0))
phi = isom * phi
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
phi = isom * phi
phi.is_normalized()

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

F = GF(2^5, 'alpha'); alpha = F.gen()
E = EllipticCurve(F, [1,0,1,1,1])
R.<x> = F[]
phi = EllipticCurveIsogeny(E, x+1)
isom = WeierstrassIsomorphism(phi.codomain(), (alpha, 0, 0, 0))
phi.is_normalized()
phi = isom * phi
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (1/alpha, 0, 0, 0))
phi = isom * phi
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
phi = isom * phi
phi.is_normalized()

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

E = EllipticCurve('11a1')
R.<x> = QQ[]
f = x^3 - x^2 - 10*x - 79/4
phi = EllipticCurveIsogeny(E, f)
isom = WeierstrassIsomorphism(phi.codomain(), (2, 0, 0, 0))
phi.is_normalized()
phi = isom * phi
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (1/2, 0, 0, 0))
phi = isom * phi
phi.is_normalized()
isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
phi = isom * phi
phi.is_normalized()

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

is_separable()

Determine whether or not this morphism is separable.

Implemented by child classes. For examples, see:

• EllipticCurveIsogeny.is_separable()

• sage.schemes.elliptic_curves.weierstrass_morphism.WeierstrassIsomorphism.is_separable()

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

• sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar.is_separable()

• sage.schemes.elliptic_curves.hom_frobenius.EllipticCurveHom_frobenius.is_separable()

is_surjective()

Determine whether or not this morphism is surjective.

Note

This method currently always returns True, since a non-constant map of algebraic curves must be surjective, and Sage does not yet implement the constant zero map. This will probably change in the future.

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

E = EllipticCurve('11a1')
R.<x> = QQ[]
f = x^2 + x - 29/5
phi = EllipticCurveIsogeny(E, f)
phi.is_surjective()

sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
sage: phi.is_surjective()
True

E = EllipticCurve(GF(7), [0,0,0,1,0])
phi = EllipticCurveIsogeny(E,  E((0,0)))
phi.is_surjective()

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

F = GF(2^5, 'omega')
E = EllipticCurve(j=F(0))
R.<x> = F[]
phi = EllipticCurveIsogeny(E, x)
phi.is_surjective()

is_zero()

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

Note

This function currently always returns True as Sage does not yet implement the constant zero morphism. This will probably change in the future.

EXAMPLES:

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

E = EllipticCurve(j=GF(7)(0))
phi = EllipticCurveIsogeny(E, [E(0,1), E(0,-1)])
phi.is_zero()

kernel_polynomial()

Return the kernel polynomial of this elliptic-curve morphism.

Implemented by child classes. For examples, see:

• EllipticCurveIsogeny.kernel_polynomial()

• sage.schemes.elliptic_curves.weierstrass_morphism.WeierstrassIsomorphism.kernel_polynomial()

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

• sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar.kernel_polynomial()

• sage.schemes.elliptic_curves.hom_frobenius.EllipticCurveHom_frobenius.kernel_polynomial()

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 $\mathbf{Z}/n$, such that the image of any point $[a]P+[b]Q$ under this morphism equals $[c]R+[d]S$ where $(cd{)}^T=(ab)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

F.<i> = GF(419^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
P = E(3, 176*i)
Q = E(i+7, 67*i+48)
P.weil_pairing(Q, 420).multiplicative_order()
iota = E.automorphisms()[2]; iota
iota^2 == E.scalar_multiplication(-1)
mat = iota.matrix_on_subgroup((P,Q)); mat
mat.parent()
iota(P) == 301*P + 386*Q
iota(Q) == 83*P + 119*Q
a,b = 123, 456
c,d = vector((a,b)) * mat; (c,d)
iota(a*P + b*Q) == c*P + d*Q

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

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

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

F.<a> = GF((101, 36))
E = EllipticCurve(GF(101), [1,1])
EE = E.change_ring(F)
P,Q = EE.torsion_basis(37)
pi = EE.frobenius_isogeny()
M = pi.matrix_on_subgroup((P,Q))
M.parent()
M.trace()
E.trace_of_frobenius()

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:

• EllipticCurveIsogeny.rational_maps()

• sage.schemes.elliptic_curves.weierstrass_morphism.WeierstrassIsomorphism.rational_maps()

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

• sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar.rational_maps()

• sage.schemes.elliptic_curves.hom_frobenius.EllipticCurveHom_frobenius.rational_maps()

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 ${\phi }^{\ast }{\omega }_2=u{\omega }_1$, where $\phi :E_1\to E_2$ is this morphism and ${\omega }_i$ are the standard Weierstrass differentials on $E_i$ defined by $\mathrm{d}x/(2y+a_{1}x+a_3)$.

Implemented by child classes. For examples, see:

• EllipticCurveIsogeny.scaling_factor()

• sage.schemes.elliptic_curves.weierstrass_morphism.WeierstrassIsomorphism.scaling_factor()

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

• sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar.scaling_factor()

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

E = EllipticCurve(QQ, [42, 42])
m5 = E.scalar_multiplication(5)
m5.trace()

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

E = EllipticCurve(GF(71^2), [45, 45])
P = E.lift_x(27)
P.order()
tau = E.isogeny(P, codomain=E)
tau.trace()

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:

• EllipticCurveIsogeny.x_rational_map()

• sage.schemes.elliptic_curves.weierstrass_morphism.WeierstrassIsomorphism.x_rational_map()

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

• sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar.x_rational_map()

• sage.schemes.elliptic_curves.hom_frobenius.EllipticCurveHom_frobenius.x_rational_map()

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:

• left, right – EllipticCurveHom objects

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

E = EllipticCurve(GF(83), [1,0])
phi = E.isogeny(12*E.0, model='montgomery'); phi
psi = phi.dual(); psi
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
mu = EllipticCurveHom_composite.from_factors([phi, psi])
from sage.schemes.elliptic_curves.hom import compare_via_evaluation
compare_via_evaluation(mu, E.scalar_multiplication(7))

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 ${\phi }^2(P)+[\mathrm{deg}(\phi )]P=[t_{\ell }]\phi (P)$. Then $t_{\ell }$ equals the trace of $\phi$ 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

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

It works over $\mathbf{Q}$:

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

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

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

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

sage.schemes.elliptic_curves.hom.find_post_isomorphism(phi, psi)

Given two isogenies $\varphi :E\to E^{\prime }$ 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^{\prime }\to E^{″}$ such that $\alpha \circ \varphi =\psi$.

ALGORITHM:

Start with a list of all isomorphisms $E^{\prime }\to E^{″}$. Then repeatedly evaluate $\varphi$ and $\psi$ at random points $P$ to filter the list for isomorphisms $\alpha$ with $\alpha (\varphi (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

from sage.schemes.elliptic_curves.hom import find_post_isomorphism
E = EllipticCurve(GF(7^2), [1,0])
f = E.scalar_multiplication(1)
g = choice(E.automorphisms())
find_post_isomorphism(f, g) == g

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)

from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
x = polygen(ZZ, 'x')
F.<i> = GF(883^2, modulus=x^2+1)
E = EllipticCurve(F, [1,0])
P = E.lift_x(117)
Q = E.lift_x(774)
w = WeierstrassIsomorphism(E, [i,0,0,0])
phi = EllipticCurveHom_composite(E, [P,w(Q)]) * w
psi = EllipticCurveHom_composite(E, [Q,w(P)])
phi.kernel_polynomial() == psi.kernel_polynomial()
find_post_isomorphism(phi, psi)

Make live