Path: blob/master/sage/schemes/elliptic_curves/ell_curve_isogeny.py
4156 views
r"""1Isogenies23An isogeny `\varphi: E_1\to E_2` between two elliptic curves `E_1` and4`E_2` is a morphism of curves that sends the origin of `E_1` to the5origin of `E_2`. Such a morphism is automatically a morphism of group6schemes and the kernel is a finite subgroup scheme of `E_1`. Such a7subscheme can either be given by a list of generators, which have to8be torsion points, or by a polynomial in the coordinate `x` of the9Weierstrass equation of `E_1`.1011The usual way to create and work with isogenies is illustrated with12the following example::1314sage: k = GF(11)15sage: E = EllipticCurve(k,[1,1])16sage: Q = E(6,5)17sage: phi = E.isogeny(Q)18sage: phi19Isogeny 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 1120sage: P = E(4,5)21sage: phi(P)22(10 : 0 : 1)23sage: phi.codomain()24Elliptic Curve defined by y^2 = x^3 + 7*x + 8 over Finite Field of size 1125sage: phi.rational_maps()26((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))2728The functions directly accessible from an elliptic curve ``E`` over a29field are ``isogeny`` and ``isogeny_codomain``.3031The most useful functions that apply to isogenies are3233- ``codomain``34- ``degree``35- ``domain``36- ``dual``37- ``rational_maps``38- ``kernel_polynomial``3940.. Warning::4142Only cyclic isogenies are implemented (except for [2]). Some43algorithms may need the isogeny to be normalized.4445AUTHORS:4647- Daniel Shumow <[email protected]>: 2009-04-19: initial version4849- Chris Wuthrich : 7/09: changes: add check of input, not the full list is needed.5010/09: eliminating some bugs.5152- John Cremona and Jenny Cooley: 2009-07..11: implement `l`-isogenies53for `l` = 2, 3, 5, 7 13 (the genus 0 cases) and also for `l` = 11,5417, 19, 37, 43, 67 or 163 over `\QQ` (the sporadic cases with only55finitely many `j`-invariants each).56"""5758#*****************************************************************************59# Copyright (C) 2009 Daniel Shumow <[email protected]>60#61# Distributed under the terms of the GNU General Public License (GPL)62# http://www.gnu.org/licenses/63#*****************************************************************************6465from copy import deepcopy, copy6667from sage.categories import homset6869from sage.categories.morphism import Morphism7071from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing72from sage.rings.polynomial.polynomial_ring import polygen73from sage.rings.all import Integer, ZZ74from sage.rings.laurent_series_ring import LaurentSeriesRing75from sage.rings.polynomial.all import is_Polynomial76from sage.schemes.elliptic_curves.all import EllipticCurve77from sage.schemes.elliptic_curves.all import is_EllipticCurve7879from sage.rings.number_field.number_field_base import is_NumberField8081from sage.rings.rational_field import is_RationalField, QQ8283from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism8485from sage.sets.set import Set8687from sage.misc.cachefunc import cached_function8889#90# Private function for parsing input to determine the type of91# algorithm92#93def isogeny_determine_algorithm(E, kernel, codomain, degree, model):94r"""95Helper function that allows the various isogeny functions to infer96the algorithm type from the parameters passed in.9798If ``kernel`` is a list of points on the EllipticCurve `E`, then99we assume the algorithm to use is Velu.100101If ``kernel`` is a list of coefficients or a univariate polynomial102we try to use the Kohel's algorithms.103104EXAMPLES:105106This helper function will be implicitly called by the following examples::107108sage: R.<x> = GF(5)[]109sage: E = EllipticCurve(GF(5), [0,0,0,1,0])110sage: phi = EllipticCurveIsogeny(E, x+3)111sage: phi2 = EllipticCurveIsogeny(E, [GF(5)(3),GF(5)(1)])112sage: phi == phi2113True114sage: phi3 = EllipticCurveIsogeny(E, E((2,0)) )115sage: phi3 == phi2116True117sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_determine_algorithm118sage: isogeny_determine_algorithm(E, x+3, None, None, None)119'kohel'120sage: isogeny_determine_algorithm(E, [3, 1], None, None, None)121'kohel'122sage: isogeny_determine_algorithm(E, E((2,0)), None, None, None)123'velu'124125"""126127kernel_is_list = (type(kernel) == list)128129if not kernel_is_list and kernel in E :130kernel = [kernel]131kernel_is_list = True132133if (is_Polynomial(kernel) or ( kernel_is_list) and (kernel[0] in E.base_ring()) ):134algorithm = "kohel"135elif (kernel_is_list) and (kernel[0] in E): # note that if kernel[0] is on an extension of E this condition will be false136algorithm = "velu"137else:138raise ValueError, "Invalid Parameters to EllipticCurveIsogeny constructor."139140return algorithm141142143def isogeny_codomain_from_kernel(E, kernel, degree=None):144r"""145This function computes the isogeny codomain given a kernel.146147INPUT:148149- ``E`` - The domain elliptic curve.150151- ``kernel`` - Either a list of points in the kernel of the isogeny, or a152kernel polynomial (specified as a either a univariate153polynomial or a coefficient list.)154155- ``degree`` - an integer, (default:``None``) optionally specified degree156of the kernel.157158OUTPUT:159160(elliptic curve) the codomain of the separable normalized isogeny161from this kernel162163EXAMPLES::164165sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_codomain_from_kernel166sage: E = EllipticCurve(GF(7), [1,0,1,0,1])167sage: R.<x> = GF(7)[]168sage: isogeny_codomain_from_kernel(E, [4,1], degree=3)169Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7170sage: EllipticCurveIsogeny(E, [4,1]).codomain() == isogeny_codomain_from_kernel(E, [4,1], degree=3)171True172sage: isogeny_codomain_from_kernel(E, x^3 + x^2 + 4*x + 3)173Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7174sage: isogeny_codomain_from_kernel(E, x^3 + 2*x^2 + 4*x + 3)175Elliptic Curve defined by y^2 + x*y + y = x^3 + 5*x + 2 over Finite Field of size 7176177sage: E = EllipticCurve(GF(19), [1,2,3,4,5])178sage: kernel_list = [E((15,10)), E((10,3)),E((6,5))]179sage: isogeny_codomain_from_kernel(E, kernel_list)180Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19181182"""183184algorithm = isogeny_determine_algorithm(E, kernel, None, degree, None);185186if ("velu"==algorithm):187# if we are using Velu's formula, just instantiate the isogeny188# and return the codomain189codomain = EllipticCurveIsogeny(E, kernel).codomain()190elif ("kohel"==algorithm):191codomain = compute_codomain_kohel(E, kernel, degree)192193return codomain194195196def compute_codomain_formula(E, v, w):197r"""198Given parameters `v` and `w` (as in Velu / Kohel / etc formulas)199computes the codomain curve.200201EXAMPLES:202203This formula is used by every Isogeny Instantiation::204205sage: E = EllipticCurve(GF(19), [1,2,3,4,5])206sage: phi = EllipticCurveIsogeny(E, E((1,2)) )207sage: phi.codomain()208Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19209sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_formula210sage: v = phi._EllipticCurveIsogeny__v211sage: w = phi._EllipticCurveIsogeny__w212sage: compute_codomain_formula(E, v, w)213Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19214215"""216217a1,a2,a3,a4,a6 = E.ainvs()218219A4 = a4 - 5*v220A6 = a6 - (a1**2 + 4*a2)*v - 7*w221222return EllipticCurve([a1, a2, a3, A4, A6])223224225def compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4):226r"""227The formula for computing `v` and `w` using Kohel's formulas for228isogenies of degree 2.229230EXAMPLES:231232This function will be implicitly called by the following example::233234sage: E = EllipticCurve(GF(19), [1,2,3,4,5])235sage: phi = EllipticCurveIsogeny(E, [9,1])236sage: phi237Isogeny 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 19238sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg1239sage: a1,a2,a3,a4,a6 = E.ainvs()240sage: x0 = -9241sage: y0 = -(a1*x0 + a3)/2242sage: compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4)243(18, 9)244245"""246247v = (3*x0**2 + 2*a2*x0 + a4 - a1*y0)248w = x0*v249250return (v,w)251252253def compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3):254r"""255The formula for computing `v` and `w` using Kohel's formulas for256isogenies of degree 3.257258EXAMPLES:259260This function will be implicitly called by the following example::261262sage: E = EllipticCurve(GF(19), [1,2,3,4,5])263sage: R.<x> = GF(19)[]264sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12)265sage: phi266Isogeny 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 19267sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg3268sage: (b2,b4) = (E.b2(), E.b4())269sage: (s1, s2, s3) = (-7, 15, -12)270sage: compute_vw_kohel_even_deg3(b2, b4, s1, s2, s3)271(4, 7)272273"""274275temp1 = (s1**2 - 2*s2)276v = 3*temp1 + b2*s1/2 + 3*b4/2277w = 3*(s1**3 - 3*s1*s2 + 3*s3) + b2*temp1/2 + b4*s1/2278279return (v,w)280281282def compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n):283r"""284This function computes the `v` and `w` according to Kohel's formulas.285286EXAMPLES:287288This function will be implicitly called by the following example::289290sage: E = EllipticCurve(GF(19), [18,17,16,15,14])291sage: R.<x> = GF(19)[]292sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11)293sage: phi294Isogeny 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 19295sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_odd296sage: (b2,b4,b6) = (E.b2(), E.b4(), E.b6())297sage: (s1,s2,s3) = (-14,3,-11)298sage: compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,3)299(7, 1)300301"""302303v = 6*(s1**2 - 2*s2) + b2*s1 + n*b4304w = 10*(s1**3 - 3*s1*s2 + 3*s3) + 2*b2*(s1**2 - 2*s2) + 3*b4*s1 + n*b6305306return (v,w)307308309def compute_codomain_kohel(E, kernel, degree):310r"""311This function computes the codomain from the kernel polynomial as312per Kohel's formulas.313314EXAMPLES::315316sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_kohel317sage: E = EllipticCurve(GF(19), [1,2,3,4,5])318sage: phi = EllipticCurveIsogeny(E, [9,1])319sage: phi.codomain() == isogeny_codomain_from_kernel(E, [9,1])320True321sage: compute_codomain_kohel(E, [9,1], 2)322Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19323sage: R.<x> = GF(19)[]324sage: E = EllipticCurve(GF(19), [18,17,16,15,14])325sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11)326sage: phi.codomain() == isogeny_codomain_from_kernel(E, x^3 + 14*x^2 + 3*x + 11)327True328sage: compute_codomain_kohel(E, x^3 + 14*x^2 + 3*x + 11, 7)329Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19330sage: E = EllipticCurve(GF(19), [1,2,3,4,5])331sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12)332sage: isogeny_codomain_from_kernel(E, x^3 + 7*x^2 + 15*x + 12) == phi.codomain()333True334sage: compute_codomain_kohel(E, x^3 + 7*x^2 + 15*x + 12,4)335Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19336337NOTES:338339This function uses the formulas of Section 2.4 of [K96].340341REFERENCES:342343- [K96] Kohel, "Endomorphism Rings of Elliptic Curves over Finite Fields"344345"""346347# First set up the polynomial ring348349base_field = E.base_ring()350351if (is_Polynomial(kernel)):352psi = kernel353kernel_list = psi.list()354poly_ring = psi.parent()355x = psi.variables()[0]356elif (list == type(kernel)) and (kernel[0] in base_field):357kernel_list = kernel358poly_ring = base_field.polynomial_ring()359psi = poly_ring(kernel_list)360x = poly_ring.gen()361else:362raise ValueError, "input not of correct type"363364365# next determine the even / odd part of the isogeny366psi_2tor = two_torsion_part(E, poly_ring, psi, degree)367368if (0 != psi_2tor.degree()): # even degree case369370psi_quo = poly_ring(psi/psi_2tor)371372if (0 != psi_quo.degree()):373raise ArithmeticError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion."374375n = psi_2tor.degree()376377if (1 == n):378379a1,a2,a3,a4,a6 = E.ainvs()380381x0 = -psi_2tor.constant_coefficient()382383# determine y0384if (2 == base_field.characteristic()):385y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt()386else:387y0 = -(a1*x0 + a3)/2388389(v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4)390391elif (3 == n):392393b2 = E.b2()394b4 = E.b4()395396s = psi_2tor.list()397s1 = -s[n-1]398s2 = s[n-2]399s3 = -s[n-3]400401(v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3)402403else:404405n = psi.degree()406407b2 = E.b2()408b4 = E.b4()409b6 = E.b6()410411s1 = 0; s2 = 0; s3 = 0412413if (1 <= n):414s1 = -kernel_list[n-1]415416if (2 <= n):417s2 = kernel_list[n-2]418419if (3 <= n):420s3 = -kernel_list[n-3]421422# initializing these allows us to calculate E2.423(v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n);424425return compute_codomain_formula(E, v, w)426427428def two_torsion_part(E, poly_ring, psi, degree):429r"""430431Returns the greatest common divisor of ``psi`` and the 2 torsion432polynomial of `E`.433434EXAMPLES:435436Every function that computes the kernel polynomial via Kohel's437formulas will call this function::438439sage: E = EllipticCurve(GF(19), [1,2,3,4,5])440sage: R.<x> = GF(19)[]441sage: phi = EllipticCurveIsogeny(E, x + 13)442sage: isogeny_codomain_from_kernel(E, x + 13) == phi.codomain()443True444sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part445sage: two_torsion_part(E, R, x+13, 2)446x + 13447448"""449if (None==degree) or (0 == degree % 2):450451x = poly_ring.gens()[0]452psi_2 = E.two_division_polynomial(x)453psi_G = poly_ring(psi.gcd(psi_2))454455else:456457psi_G = poly_ring(1)458459return psi_G460461462class EllipticCurveIsogeny(Morphism):463r"""464Class Implementing Isogenies of Elliptic Curves465466This class implements cyclic, separable, normalized isogenies of467elliptic curves.468469Several different algorithms for computing isogenies are470available. These include:471472- Velu's Formulas: Velu's original formulas for computing473isogenies. This algorithm is selected by giving as the474``kernel`` parameter a list of points which generate a finite475subgroup.476477- Kohel's Formulas: Kohel's original formulas for computing478isogenies. This algorithm is selected by giving as the479``kernel`` parameter a monic polynomial (or a coefficient list480(little endian)) which will define the kernel of the isogeny.481482INPUT:483484- ``E`` - an elliptic curve, the domain of the isogeny to485initialize.486487- ``kernel`` - a kernel, either a point in ``E``, a list of points488in ``E``, a monic kernel polynomial, or ``None``.489If initializing from a domain/codomain, this must be490set to None.491492- ``codomain`` - an elliptic curve (default:``None``). If ``kernel``493is ``None``, then this must be the codomain of a cyclic,494separable, normalized isogeny, furthermore, ``degree``495must be the degree of the isogeny from ``E`` to496``codomain``. If ``kernel`` is not ``None``, then this497must be isomorphic to the codomain of the cyclic normalized498separable isogeny defined by ``kernel``, in this case, the499isogeny is post composed with an isomorphism so that this500parameter is the codomain.501502- ``degree`` - an integer (default:``None``).503If ``kernel`` is ``None``, then this is the degree of the504isogeny from ``E`` to ``codomain``.505If ``kernel`` is not ``None``, then this is used to determine506whether or not to skip a gcd of the kernel polynomial with the507two torsion polynomial of ``E``.508509- ``model`` - a string (default:``None``). Only supported variable is510``minimal``, in which case if ``E`` is a curve over the511rationals, then the codomain is set to be the unique global512minimum model.513514- ``check`` (default: ``True``) checks if the input is valid to define an isogeny515516EXAMPLES:517518A simple example of creating an isogeny of a field of small519characteristic::520521sage: E = EllipticCurve(GF(7), [0,0,0,1,0])522sage: phi = EllipticCurveIsogeny(E, E((0,0)) ); phi523Isogeny 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 7524sage: phi.degree() == 2525True526sage: phi.kernel_polynomial()527x528sage: phi.rational_maps()529((x^2 + 1)/x, (x^2*y - y)/x^2)530sage: phi == loads(dumps(phi)) # optional - pickling http://trac.sagemath.org/sage_trac/ticket/11599531True532533A more complicated example of a characteristic 2 field::534535sage: E = EllipticCurve(GF(2^4,'alpha'), [0,0,1,0,1])536sage: P = E((1,1))537sage: phi_v = EllipticCurveIsogeny(E, P); phi_v538Isogeny 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^4539sage: phi_ker_poly = phi_v.kernel_polynomial()540sage: phi_ker_poly541x + 1542sage: ker_poly_list = phi_ker_poly.list()543sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list)544sage: phi_k == phi_v545True546sage: phi_k.rational_maps()547((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1))548sage: phi_v.rational_maps()549((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1))550sage: phi_k.degree() == phi_v.degree()551True552sage: phi_k.degree()5533554sage: phi_k.is_separable()555True556sage: phi_v(E(0))557(0 : 1 : 0)558sage: alpha = E.base_field().gen()559sage: Q = E((0, alpha*(alpha + 1)))560sage: phi_v(Q)561(1 : alpha^2 + alpha : 1)562sage: phi_v(P) == phi_k(P)563True564sage: phi_k(P) == phi_v.codomain()(0)565True566567We can create an isogeny that has kernel equal to the full 2568torsion::569570sage: E = EllipticCurve(GF(3), [0,0,0,1,1])571sage: ker_list = E.division_polynomial(2).list()572sage: phi = EllipticCurveIsogeny(E, ker_list); phi573Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3574sage: phi(E(0))575(0 : 1 : 0)576sage: phi(E((0,1)))577(1 : 0 : 1)578sage: phi(E((0,2)))579(1 : 0 : 1)580sage: phi(E((1,0)))581(0 : 1 : 0)582sage: phi.degree()5834584585We can also create trivial isogenies with the trivial kernel::586587sage: E = EllipticCurve(GF(17), [11, 11, 4, 12, 10])588sage: phi_v = EllipticCurveIsogeny(E, E(0))589sage: phi_v.degree()5901591sage: phi_v.rational_maps()592(x, y)593sage: E == phi_v.codomain()594True595sage: P = E.random_point()596sage: phi_v(P) == P597True598599sage: E = EllipticCurve(GF(31), [23, 1, 22, 7, 18])600sage: phi_k = EllipticCurveIsogeny(E, [1])601sage: phi_k602Isogeny 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 31603sage: phi_k.degree()6041605sage: phi_k.rational_maps()606(x, y)607sage: phi_k.codomain() == E608True609sage: phi_k.kernel_polynomial()6101611sage: P = E.random_point(); P == phi_k(P)612True613614Velu and Kohel also work in characteristic 0::615616sage: E = EllipticCurve(QQ, [0,0,0,3,4])617sage: P_list = E.torsion_points()618sage: phi = EllipticCurveIsogeny(E, P_list)619sage: phi620Isogeny 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 Field621sage: P = E((0,2))622sage: phi(P)623(6 : -10 : 1)624sage: phi_ker_poly = phi.kernel_polynomial()625sage: phi_ker_poly626x + 1627sage: ker_poly_list = phi_ker_poly.list()628sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k629Isogeny 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 Field630sage: phi_k(P) == phi(P)631True632sage: phi_k == phi633True634sage: phi_k.degree()6352636sage: phi_k.is_separable()637True638639A more complicated example over the rationals (of odd degree)::640641sage: E = EllipticCurve('11a1')642sage: P_list = E.torsion_points()643sage: phi_v = EllipticCurveIsogeny(E, P_list); phi_v644Isogeny 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 Field645sage: P = E((16,-61))646sage: phi_v(P)647(0 : 1 : 0)648sage: ker_poly = phi_v.kernel_polynomial(); ker_poly649x^2 - 21*x + 80650sage: ker_poly_list = ker_poly.list()651sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k652Isogeny 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 Field653sage: phi_k == phi_v654True655sage: phi_v(P) == phi_k(P)656True657sage: phi_k.is_separable()658True659660We can also do this same example over the number field defined by661the irreducible two torsion polynomial of `E`::662663sage: E = EllipticCurve('11a1')664sage: P_list = E.torsion_points()665sage: K.<alpha> = NumberField(x^3 - 2* x^2 - 40*x - 158)666sage: EK = E.change_ring(K)667sage: P_list = [EK(P) for P in P_list]668sage: phi_v = EllipticCurveIsogeny(EK, P_list); phi_v669Isogeny 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 - 158670sage: P = EK((alpha/2,-1/2))671sage: phi_v(P)672(122/121*alpha^2 + 1633/242*alpha - 3920/121 : -1/2 : 1)673sage: ker_poly = phi_v.kernel_polynomial()674sage: ker_poly675x^2 - 21*x + 80676sage: ker_poly_list = ker_poly.list()677sage: phi_k = EllipticCurveIsogeny(EK, ker_poly_list)678sage: phi_k679Isogeny 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 - 158680sage: phi_v == phi_k681True682sage: phi_k(P) == phi_v(P)683True684sage: phi_k == phi_v685True686sage: phi_k.degree()6875688sage: phi_v.is_separable()689True690691The following example shows how to specify an isogeny from domain692and codomain::693694sage: E = EllipticCurve('11a1')695sage: R.<x> = QQ[]696sage: f = x^2 - 21*x + 80697sage: phi = E.isogeny(f)698sage: E2 = phi.codomain()699sage: phi_s = EllipticCurveIsogeny(E, None, E2, 5)700sage: phi_s701Isogeny 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 Field702sage: phi_s == phi703True704sage: phi_s.rational_maps() == phi.rational_maps()705True706707However only cyclic normalized isogenies can be constructed this708way. So it won't find the isogeny [3]::709710sage: E.isogeny(None, codomain=E,degree=9)711Traceback (most recent call last):712...713ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 9714715Also the presumed isogeny between the domain and codomain must be716normalized::717718sage: E2.isogeny(None,codomain=E,degree=5)719Traceback (most recent call last):720...721ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 5722sage: phi.dual()723Isogeny 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 Field724sage: phi.dual().is_normalized()725False726727Here an example of a construction of a endomorphisms with cyclic728kernel on a CM-curve::729730sage: K.<i> = NumberField(x^2+1)731sage: E = EllipticCurve(K, [1,0])732sage: RK.<X> = K[]733sage: f = X^2 - 2/5*i + 1/5734sage: phi= E.isogeny(f)735sage: isom = phi.codomain().isomorphism_to(E)736sage: phi.set_post_isomorphism(isom)737sage: phi.codomain() == phi.domain()738True739sage: phi.rational_maps()740(((-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)),741((2/125*i - 11/125)*x^6*y + (64/125*i + 23/125)*x^4*y + (162/125*i - 141/125)*x^2*y + (-4/25*i - 3/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125)))742743"""744745####################746# member variables747####################748749__check = None750#751# variables common to all algorithms752#753__E1 = None # domain curve754__E2 = None # codomain curve755756__degree = None757758__separable = True # This class only implements separable isogenies (for now.)759760__algorithm = None761762__this_hash = None763764__check = None765#766# pre isomorphism767#768__intermediate_domain = None769__pre_isomorphism = None770__prei_x_coord_ratl_map = None771__prei_y_coord_ratl_map = None772773#774# post isomorphism775#776777__intermediate_codomain = None778__post_isomorphism = None779__posti_x_coord_ratl_map = None780__posti_y_coord_ratl_map = None781782#783# algebraic structs784#785__base_field = None786__poly_ring = None787__x_var = None788__y_var = None789790#791# Rational Maps792#793__rational_maps_initialized = False794__X_coord_rational_map = None795__Y_coord_rational_map = None796797#798# The dual799#800__dual = None801802#803# Kernel Data804#805806__kernel_list = None # list of elements in the kernel807808__kernel_polynomial_list = None # polynomial stored as a little endian list of coefficients809810__kernel_polynomial = None # polynomial with roots at x values for x-coordinate of points in the kernel811812__inner_kernel_polynomial = None # the inner kernel polynomial (ignoring preisomorphism)813814__n = None815816817#818# member variables common to Velu's formula819#820821# we keep track of the 2 torsion and non2torsion separately822__kernel_2tor = None823__kernel_non2tor = None824825# variables used in Velu's formula (as well as Kohel's variant)826__v = None827__w = None828829830#831# member variables specific to Kohel's algorithm.832#833834__psi = None # psi polynomial835__phi = None # phi polynomial836__omega = None # omega polynomial837838839#840# Python Special Functions841#842843def __init__(self, E, kernel, codomain=None, degree=None, model=None, check=True):844r"""845Constructor for EllipticCurveIsogeny class.846847EXAMPLES::848849sage: E = EllipticCurve(GF(2), [0,0,1,0,1])850sage: phi = EllipticCurveIsogeny(E, [1,1])851sage: phi852Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + 1 over Finite Field of size 2 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field of size 2853854sage: E = EllipticCurve(GF(31), [0,0,0,1,0])855sage: P = E((2,17))856sage: phi = EllipticCurveIsogeny(E, P)857sage: phi858Isogeny of degree 8 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 31 to Elliptic Curve defined by y^2 = x^3 + 10*x + 28 over Finite Field of size 31859860sage: E = EllipticCurve('17a1')861sage: phi = EllipticCurveIsogeny(E, [41/3, -55, -1, -1, 1])862sage: phi863Isogeny of degree 9 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - x - 14 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - 56*x - 10124 over Rational Field864865sage: E = EllipticCurve('37a1')866sage: triv = EllipticCurveIsogeny(E, E(0))867sage: triv868Isogeny of degree 1 from Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field869sage: triv.rational_maps()870(x, y)871872sage: E = EllipticCurve('49a3')873sage: R.<X> = QQ[]874sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False)875Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 107*x + 552 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 5252*x - 178837 over Rational Field876877"""878879if not is_EllipticCurve(E):880raise ValueError, "E parameter must be an EllipticCurve."881882if type(kernel) != type([1,1]) and kernel in E :883# a single point was given, we put it in a list884# the first condition assures that [1,1] is treated as x+1885kernel = [kernel]886887# if the kernel is None and the codomain isn't888# calculate the kernel polynomial889pre_isom = None890post_isom = None891892self.__check = check893894if (kernel is None) and (codomain is not None):895896if (degree is None):897raise ValueError, "If specifying isogeny by domain and codomain, degree parameter must be set."898899# save the domain/codomain: really used now (trac #7096)900old_domain = E901old_codomain = codomain902903(pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree)904905self.__init_algebraic_structs(E)906907algorithm = isogeny_determine_algorithm(E, kernel, codomain, degree, model);908909self.__algorithm = algorithm910911if ("velu"==algorithm):912self.__init_from_kernel_list(kernel)913elif ("kohel"==algorithm):914self.__init_from_kernel_polynomial(kernel, degree)915916self.__compute_E2()917918self.__setup_post_isomorphism(codomain, model)919920if (pre_isom is not None):921self.set_pre_isomorphism(pre_isom)922923if (post_isom is not None):924self.__set_post_isomorphism(old_codomain, post_isom) #(trac #7096)925926# Inheritance house keeping927928self.__perform_inheritance_housekeeping()929930return931932933def __call__(self, P, output_base_ring=None):934r"""935Function that implements the call-ability of elliptic curve936isogenies.937938EXAMPLES::939940sage: E = EllipticCurve(GF(17), [1, 9, 5, 4, 3])941sage: phi = EllipticCurveIsogeny(E, [6,13,1])942sage: phi(E((1,0)))943(15 : 13 : 1)944945sage: E = EllipticCurve(GF(23), [0,0,0,1,0])946sage: phi = EllipticCurveIsogeny(E, E((0,0)))947sage: phi(E((1,5)))948(2 : 0 : 1)949sage: phi(E(15,20), output_base_ring=GF(23^2,'alpha'))950(12 : 1 : 1)951952sage: E = EllipticCurve(QQ, [0,0,0,3,0])953sage: P = E((1,2))954sage: phi = EllipticCurveIsogeny(E, [0,1])955sage: phi(P)956(4 : -4 : 1)957sage: phi(-P)958(4 : 4 : 1)959960sage: E = EllipticCurve(GF(17), [0,-1,0,-3,-1])961sage: Q = E((16,0))962sage: tau = E.isogeny([Q],E)963sage: tau(Q)964(0 : 1 : 0)965966TESTS (trac 10888)::967968sage: K.<th> = NumberField(x^2+3)969sage: E = EllipticCurve(K,[7,0])970sage: phi = E.isogeny(E(0,0))971sage: P = E(-3,4*th)972sage: phi(P)973(-16/3 : 8/9*th : 1)974sage: Q = phi(P)975sage: phihat = phi.dual()976sage: phihat(Q)977(-1/48 : 127/576*th : 1)978979"""980E1 = self.__E1981E_P = P.curve()982change_output_ring = False983984# check that the parent curve of the input point is this curve985# or that the point is on the same curve but whose base ring986# is an extension of this ring987if (E1 != E_P):988if (E1.a_invariants() != E_P.a_invariants()) :989raise ValueError, "P must be on a curve with same Weierstrass model as the domain curve of this isogeny."990change_output_ring = True991992993if(P.is_zero()):994return self.__E2(0)995996(xP, yP) = P.xy()997998if not self.__E1.is_on_curve(xP,yP):999raise InputError, "Input point must be on the domain curve of this isogeny."10001001# if there is a pre isomorphism, apply it1002if (self.__pre_isomorphism is not None):1003temp_xP = self.__prei_x_coord_ratl_map(xP, yP)1004temp_yP = self.__prei_y_coord_ratl_map(xP, yP)1005(xP, yP) = (temp_xP, temp_yP)10061007if ("velu" == self.__algorithm):1008outP = self.__compute_via_velu_numeric(xP, yP)1009elif ("kohel" == self.__algorithm):1010outP = self.__compute_via_kohel_numeric(xP,yP)10111012# the intermediate functions return the point at infinity1013# if the input point is in the kernel1014if (outP == self.__intermediate_codomain(0)):1015return self.__E2(0)10161017# if there is a post isomorphism, apply it1018if (self.__post_isomorphism is not None):1019tempX = self.__posti_x_coord_ratl_map(outP[0], outP[1])1020tempY = self.__posti_y_coord_ratl_map(outP[0], outP[1])1021outP = [tempX, tempY]10221023if change_output_ring:1024if (output_base_ring is None):1025output_base_ring = E_P.base_ring()1026outE2 = self.__E2.change_ring(output_base_ring)1027else:1028output_base_ring = self.__E2.base_ring()1029outE2 = self.__E21030outP = self.__E2.point(outP,check=False)10311032R = output_base_ring10331034return outE2.point([R(outP[0]), R(outP[1]), R(1)], check=False)103510361037def __getitem__(self, i):1038self.__initialize_rational_maps()1039if (i < 0) or (i > 2):1040raise IndexError10411042if i == 0:1043return self.__X_coord_rational_map1044else:1045return self.__Y_coord_rational_map10461047def __iter__(self):1048self.__initialize_rational_maps()1049return iter((self.__X_coord_rational_map, self.__Y_coord_rational_map))10501051def __hash__(self):1052r"""1053Function that implements the hash ability of Isogeny objects.10541055This hashes the underlying kernel polynomial so that equal1056isogeny objects have the same hash value. Also, this hashes1057the base field, and domain and codomain curves as well, so1058that isogenies with the same kernel polynomial (over different1059base fields / curves) hash to different values.10601061EXAMPLES::10621063sage: E = EllipticCurve(QQ, [0,0,0,1,0])1064sage: phi_v = EllipticCurveIsogeny(E, E((0,0)))1065sage: phi_k = EllipticCurveIsogeny(E, [0,1])1066sage: phi_k.__hash__() == phi_v.__hash__()1067True1068sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,1])1069sage: phi_p = EllipticCurveIsogeny(E_F17, E_F17([0,1]))1070sage: phi_p.__hash__() == phi_v.__hash__()1071False10721073sage: E = EllipticCurve('49a3')1074sage: R.<X> = QQ[]1075sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False)1076Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 107*x + 552 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 5252*x - 178837 over Rational Field10771078"""10791080if (self.__this_hash is not None):1081return self.__this_hash10821083ker_poly_list = self.__kernel_polynomial_list10841085if (ker_poly_list is None):1086ker_poly_list = self.__init_kernel_polynomial()10871088this_hash = 010891090for a in ker_poly_list:1091this_hash = this_hash.__xor__(hash(a))10921093this_hash = this_hash.__xor__(hash(self.__E1))1094this_hash = this_hash.__xor__(hash(self.__E2))1095this_hash = this_hash.__xor__(hash(self.__base_field))10961097self.__this_hash = this_hash10981099return self.__this_hash110011011102def __cmp__(self, other):1103r"""1104Function that implements comparisons between isogeny objects.11051106This function works by comparing the underlying kernel1107objects.11081109EXAMPLES::11101111sage: E = EllipticCurve(QQ, [0,0,0,1,0])1112sage: phi_v = EllipticCurveIsogeny(E, E((0,0)))1113sage: phi_k = EllipticCurveIsogeny(E, [0,1])1114sage: phi_k == phi_v1115True1116sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,0])1117sage: phi_p = EllipticCurveIsogeny(E_F17, [0,1])1118sage: phi_p == phi_v1119False1120sage: E = EllipticCurve('11a1')1121sage: phi = E.isogeny(E(5,5))1122sage: psi = E.isogeny(phi.kernel_polynomial())1123sage: phi == psi1124True1125sage: phi.dual() == psi.dual()1126True112711281129"""1130if (not isinstance(other, EllipticCurveIsogeny)):1131return -111321133if (self.__kernel_polynomial is None):1134self.__init_kernel_polynomial()11351136return cmp(self.__kernel_polynomial, other.kernel_polynomial())113711381139def __neg__(self):1140r"""1141Function to implement unary negation (-) operator on1142isogenies. Returns a copy of this isogeny that has been1143negated.11441145EXAMPLES:11461147The following examples inherently exercise this function::11481149sage: E = EllipticCurve(j=GF(17)(0))1150sage: phi = EllipticCurveIsogeny(E, E((-1,0)) )1151sage: negphi = -phi1152sage: phi(E((0,1))) + negphi(E((0,1)))1153(0 : 1 : 0)11541155sage: E = EllipticCurve(j=GF(19)(1728))1156sage: R.<x> = GF(19)[]1157sage: phi = EllipticCurveIsogeny(E, x)1158sage: negphi = -phi1159sage: phi(E((3,7))) + negphi(E((3,12))) == phi(2*E((3,7)))1160True1161sage: negphi(E((18,6)))1162(17 : 0 : 1)11631164sage: R.<x> = QQ[]1165sage: E = EllipticCurve('17a1')1166sage: R.<x> = QQ[]1167sage: f = x - 11/41168sage: phi = EllipticCurveIsogeny(E, f)1169sage: negphi = -phi1170sage: phi.rational_maps()[0] == negphi.rational_maps()[0]1171True1172sage: P = E((7,13))1173sage: phi(P) + negphi(P)1174(0 : 1 : 0)11751176"""1177# save off the kernel lists1178kernel_list = self.__kernel_list1179self.__kernel_list = None11801181output = deepcopy(self)11821183# reset the kernel lists1184output.__kernel_list = copy(kernel_list)1185self.__kernel_list = kernel_list11861187output.switch_sign()1188return output1189119011911192#1193# Sage Special Functions1194#11951196def _repr_(self):1197r"""1198Special sage specific function that implement the1199functionality to display the isogeny self as a string.12001201EXAMPLES::12021203sage: E = EllipticCurve(GF(31), [1,0,1,1,0])1204sage: phi = EllipticCurveIsogeny(E, E((0,0)) )1205sage: phi._repr_()1206'Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 31 to Elliptic Curve defined by y^2 + x*y + y = x^3 + 14*x + 9 over Finite Field of size 31'12071208sage: E = EllipticCurve(QQ, [1,0,0,1,9])1209sage: phi = EllipticCurveIsogeny(E, [2,1])1210sage: phi._repr_()1211'Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y = x^3 + x + 9 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - 59*x + 165 over Rational Field'12121213"""1214return 'Isogeny of degree ' + self.__degree.__repr__() + ' from ' + \1215self.__E1.__repr__() + ' to ' + self.__E2.__repr__()121612171218def _latex_(self):1219r"""1220Special sage specific function that implements functionality1221to display an isogeny object as a latex string.12221223This function returns a latex string representing the isogeny1224self as the `x` and `y` coordinate rational functions.12251226EXAMPLES::12271228sage: E = EllipticCurve(QQ, [0,0,0,1,-1])1229sage: phi = EllipticCurveIsogeny(E, E(0))1230sage: phi._latex_()1231'\\left( x , y \\right)'12321233sage: E = EllipticCurve(GF(17), [0,0,0,1,-1])1234sage: R.<X> = GF(17)[]1235sage: phi = EllipticCurveIsogeny(E, X+11)1236sage: phi._latex_()1237'\\left( \\frac{x^{2} + 11 x + 7}{x + 11} , \\frac{x^{2} y + 5 x y + 12 y}{x^{2} + 5 x + 2} \\right)'123812391240"""1241ratl_maps = self.rational_maps()1242return '\\left( %s , %s \\right)' % (ratl_maps[0]._latex_(), ratl_maps[1]._latex_())124312441245###########################1246# Private Common Functions1247###########################12481249# delete the hash value1250def __clear_cached_values(self):1251r"""1252A private function to clear the hash if the codomain has been1253modified by a pre or post isomorphism.12541255EXAMPLES::12561257sage: F = GF(7);1258sage: E = EllipticCurve(j=F(0))1259sage: phi = EllipticCurveIsogeny(E, [E((0,-1)), E((0,1))])1260sage: old_hash = hash(phi)1261sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1262sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,2,-3,4)))1263sage: hash(phi) == old_hash1264False12651266sage: R.<x> = QQ[]1267sage: E = EllipticCurve(QQ, [0,0,0,1,0])1268sage: phi = EllipticCurveIsogeny(E, x)1269sage: old_ratl_maps = phi.rational_maps()1270sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1271sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,0,0,0)))1272sage: old_ratl_maps == phi.rational_maps()1273False1274sage: old_ratl_maps[1] == -phi.rational_maps()[1]1275True12761277sage: F = GF(127); R.<x> = F[]1278sage: E = EllipticCurve(j=F(1728))1279sage: f = x^5 + 43*x^4 + 97*x^3 + 81*x^2 + 42*x + 821280sage: phi = EllipticCurveIsogeny(E, f)1281sage: old_hash = hash(phi)1282sage: old_ratl_maps = phi.rational_maps()1283sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1284sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-13,13,-13,13)))1285sage: old_hash == hash(phi)1286False1287sage: old_ratl_maps == phi.rational_maps()1288False1289sage: phi._EllipticCurveIsogeny__clear_cached_values()12901291"""1292self.__this_hash = None1293self.__rational_maps_initialized = False1294self.__X_coord_rational_map = None1295self.__Y_coord_rational_map = None1296self.__dual129712981299# performs the inheritance house keeping1300def __perform_inheritance_housekeeping(self):1301r"""1302Internal helper function, sets values on the super classes of1303this class.13041305EXAMPLES:13061307The following examples will implicitly exercise this1308function::13091310sage: E = EllipticCurve(GF(43), [2,3,5,7,11])1311sage: R.<x> = GF(43)[]; f = x + 421312sage: phi = EllipticCurveIsogeny(E, f)1313sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping()1314sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1315sage: E2 = phi.codomain()1316sage: post_isom = WeierstrassIsomorphism(E2, (41, 37, 31, 29))1317sage: phi.set_post_isomorphism(post_isom)1318sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain()1319sage: pre_isom = E1pr.isomorphism_to(E)1320sage: phi.set_pre_isomorphism(pre_isom)13211322"""13231324# one of the superclasses uses these fields1325self._domain = self.__E11326self._codomain = self.__E213271328# sets up the parent1329parent = homset.Hom(self.__E1(0).parent(), self.__E2(0).parent())1330Morphism.__init__(self, parent)13311332return133313341335# initializes the base field1336def __init_algebraic_structs(self, E):1337r"""1338An internal function for EllipticCurveIsogeny objects that1339sets up the member variables necessary for algebra.13401341EXAMPLES:13421343The following tests inherently exercise this function::13441345sage: E = EllipticCurve(j=GF(17)(0))1346sage: phi = EllipticCurveIsogeny(E, E((-1,0)))1347sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)13481349sage: E = EllipticCurve(QQ, [0,0,0,1,0])1350sage: phi = EllipticCurveIsogeny(E, E((0,0)))1351sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)13521353sage: F = GF(19); R.<x> = F[]1354sage: E = EllipticCurve(j=GF(19)(0))1355sage: phi = EllipticCurveIsogeny(E, x)1356sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)13571358"""1359self.__E1 = E1360self.__base_field = E.base_ring()13611362poly_ring = self.__poly_ring = PolynomialRing(self.__base_field, ['x','y'])13631364self.__x_var = poly_ring('x')1365self.__y_var = poly_ring('y')13661367self.__intermediate_domain = E13681369return137013711372def __compute_E2(self):1373r"""1374Private function that computes and sets the isogeny codomain.13751376EXAMPLES:13771378These examples inherently exercise this function::13791380sage: E = EllipticCurve(j=GF(7)(1728))1381sage: phi = EllipticCurveIsogeny(E, E((0,0)))1382sage: phi.codomain()1383Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 71384sage: phi._EllipticCurveIsogeny__compute_E2()13851386sage: R.<x> = GF(7)[]1387sage: phi = EllipticCurveIsogeny(E, x)1388sage: phi.codomain()1389Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 71390sage: phi._EllipticCurveIsogeny__compute_E2()13911392"""13931394if ("velu" == self.__algorithm):1395E2 = self.__compute_E2_via_velu()1396elif ("kohel" == self.__algorithm):1397E2 = self.__compute_E2_via_kohel()13981399self.__E2 = E21400self.__intermediate_codomain = E214011402return140314041405# initializes the rational maps fields1406def __initialize_rational_maps(self, precomputed_maps=None):1407r"""1408Private function that computes and initializes the rational1409maps.14101411INPUT:14121413- ``14141415EXAMPLES:14161417The following examples inherently exercise this function::14181419sage: E = EllipticCurve(j=GF(7)(1728))1420sage: phi = EllipticCurveIsogeny(E, E((0,0)))1421sage: phi._EllipticCurveIsogeny__initialize_rational_maps()1422sage: phi.rational_maps()1423((x^2 + 1)/x, (x^2*y - y)/x^2)14241425sage: R.<x> = GF(7)[]1426sage: phi = EllipticCurveIsogeny(E, x)1427sage: phi = EllipticCurveIsogeny(E, x)1428sage: phi.rational_maps()1429((x^2 + 1)/x, (x^2*y - y)/x^2)1430sage: phi._EllipticCurveIsogeny__initialize_rational_maps()14311432sage: E = EllipticCurve([1,2,3,4,5])1433sage: Eshort = E.short_weierstrass_model()1434sage: phi = E.isogeny(E(0), Eshort)1435sage: phiX, phiY = phi.rational_maps()1436sage: phiX(1,2), phiY(1,2)1437(63, 864)1438"""1439if self.__rational_maps_initialized:1440return14411442if precomputed_maps is None:1443if ("velu"==self.__algorithm):1444(X_map, Y_map) = self.__initialize_rational_maps_via_velu()1445if ("kohel"==self.__algorithm):1446(X_map, Y_map) = self.__initialize_rational_maps_via_kohel()1447else:1448X_map, Y_map = precomputed_maps14491450if self.__prei_x_coord_ratl_map is not None:1451prei_X_map = self.__prei_x_coord_ratl_map1452prei_Y_map = self.__prei_y_coord_ratl_map1453X_map, Y_map = X_map.subs(x=prei_X_map, y=prei_Y_map), \1454Y_map.subs(x=prei_X_map, y=prei_Y_map)14551456if self.__posti_x_coord_ratl_map is not None:1457X_map, Y_map = \1458self.__posti_x_coord_ratl_map.subs(x=X_map, y=Y_map), \1459self.__posti_y_coord_ratl_map.subs(x=X_map, y=Y_map)14601461self.__X_coord_rational_map = X_map1462self.__Y_coord_rational_map = Y_map1463self.__rational_maps_initialized = True146414651466def __init_kernel_polynomial(self):1467r"""1468Private function that initializes the kernel polynomial (if1469the algorithm does not take it as a parameter.)14701471EXAMPLES:14721473The following examples inherently exercise this function::14741475sage: E = EllipticCurve(j=GF(7)(1728))1476sage: phi = EllipticCurveIsogeny(E, E((0,0)))1477sage: phi.kernel_polynomial()1478x1479sage: phi._EllipticCurveIsogeny__init_kernel_polynomial()1480[0, 1]14811482"""14831484if (self.__kernel_polynomial_list is not None):1485return self.__kernel_polynomial_list14861487if ("velu" == self.__algorithm):1488ker_poly_list = self.__init_kernel_polynomial_velu()1489else:1490raise InputError, "The kernel polynomial should already be defined!"14911492return ker_poly_list149314941495def __set_pre_isomorphism(self, domain, isomorphism):1496r"""1497Private function to set the pre isomorphism and domain (and1498keep track of the domain of the isogeny.)14991500EXAMPLES::15011502sage: E = EllipticCurve(GF(43), [2,3,5,7,11])1503sage: R.<x> = GF(43)[]; f = x + 421504sage: phi = EllipticCurveIsogeny(E, f)1505sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping()1506sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1507sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain()1508sage: pre_isom = E1pr.isomorphism_to(E)1509sage: phi.set_pre_isomorphism(pre_isom)1510sage: phi._EllipticCurveIsogeny__set_pre_isomorphism(E, WeierstrassIsomorphism(E, (-1, 3, -3, 4)))1511sage: E == phi.domain()1512True15131514"""15151516self.__E1 = domain15171518# set the isomorphism1519self.__pre_isomorphism = isomorphism15201521# calculate the isomorphism as a rational map.15221523(u, r, s, t) = isomorphism.tuple()15241525x = self.__x_var;1526y = self.__y_var;15271528self.__prei_x_coord_ratl_map = (x - r)/u**21529self.__prei_y_coord_ratl_map = (y - s*(x-r) - t)/u**315301531if (self.__kernel_polynomial is not None):1532ker_poly = self.__kernel_polynomial1533ker_poly = ker_poly.subs(x=self.__prei_x_coord_ratl_map)1534kp_lc = ker_poly.univariate_polynomial().leading_coefficient()1535ker_poly = (1/kp_lc)*ker_poly1536self.__kernel_polynomial = ker_poly15371538self.__perform_inheritance_housekeeping()15391540return;154115421543def __set_post_isomorphism(self, codomain, isomorphism):1544r"""1545Private function to set the post isomorphism and codomain (and1546keep track of the codomain of the isogeny.)15471548EXAMPLES:15491550The following examples inherently exercise this function::15511552sage: E = EllipticCurve(j=GF(7)(1728))1553sage: phi = EllipticCurveIsogeny(E, E((0,0)))1554sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1555sage: E2 = phi.codomain()1556sage: isom = WeierstrassIsomorphism(E2, (-1,2,-3,4))1557sage: phi.set_post_isomorphism(isom)1558sage: phi._EllipticCurveIsogeny__set_post_isomorphism(E2, WeierstrassIsomorphism(phi.codomain(), (1,-2,3,-4)))1559sage: E2 == phi.codomain()1560True15611562"""15631564# set the codomains1565self.__E2 = codomain15661567# set the isomorphism1568self.__post_isomorphism = isomorphism15691570# calculate the isomorphism as a rational map.15711572(u, r, s, t) = isomorphism.tuple()15731574x = self.__x_var;1575y = self.__y_var;15761577self.__posti_x_coord_ratl_map = (x - r)/u**21578self.__posti_y_coord_ratl_map = (y - s*(x-r) - t)/u**315791580self.__perform_inheritance_housekeeping()15811582return;158315841585def __setup_post_isomorphism(self, codomain, model):1586r"""1587Private function to set up the post isomorphism given the1588codomain.15891590EXAMPLES:15911592The following examples inherently exercise this function::15931594sage: E = EllipticCurve(j=GF(7)(1728))1595sage: E2 = EllipticCurve(GF(7), [0,0,0,5,0])1596sage: phi = EllipticCurveIsogeny(E, E((0,0)), E2); phi1597Isogeny 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 + 5*x over Finite Field of size 71598sage: E3 = EllipticCurve(GF(7), [0,0,0,6,0])1599sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(E3, None)1600sage: phi1601Isogeny 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 + 6*x over Finite Field of size 716021603sage: R.<x> = QQ[]1604sage: E = EllipticCurve(j=1728)1605sage: f = x^3 - x1606sage: phi = EllipticCurveIsogeny(E, f, model='minimal'); phi1607Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 - x over Rational Field to Elliptic Curve defined by y^2 = x^3 - x over Rational Field16081609sage: phi = EllipticCurveIsogeny(E, f, model=None)1610sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(None, 'minimal')1611sage: phi1612Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 - x over Rational Field to Elliptic Curve defined by y^2 = x^3 - x over Rational Field16131614"""16151616# TODO: add checks to make sure that1617# codomain and model parameters are consistent with the1618# algorithm used.16191620post_isom = None1621newE2 = None16221623oldE2 = self.__E216241625if (model is not None):16261627if (codomain is not None):1628raise ValueError, "Cannot specify a codomain and model flag simultaneously."16291630if ('minimal' == model):16311632if (not is_RationalField(oldE2.base_field())):1633raise ValueError, "specifying minimal for model flag only valid with curves over the rational numbers."16341635newE2 = oldE2.minimal_model()1636post_isom = oldE2.isomorphism_to(newE2)16371638else:1639raise ValueError, "Unknown value of model flag."16401641elif (codomain is not None):1642if (not is_EllipticCurve(codomain)):1643raise ValueError, "Codomain parameter must be an elliptic curve."16441645if (not oldE2.is_isomorphic(codomain)):1646raise ValueError, "Codomain parameter must be isomorphic to computed codomain isogeny"16471648newE2 = codomain1649post_isom = oldE2.isomorphism_to(newE2)16501651if (post_isom is not None):1652self.__set_post_isomorphism(newE2, post_isom)16531654return165516561657###########################1658# Velu's Formula Functions1659###########################16601661#1662# Setup function for Velu's formula1663#16641665def __init_from_kernel_list(self, kernel_gens):1666r"""1667Private function that initializes the isogeny from a list of1668points which generate the kernel (For Velu's formulas.)16691670EXAMPLES:16711672The following example inherently exercises this function::16731674sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1675sage: phi = EllipticCurveIsogeny(E, E((0,0))); phi1676Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 71677sage: phi._EllipticCurveIsogeny__init_from_kernel_list([E(0), E((0,0))])16781679"""1680if self.__check :1681for P in kernel_gens:1682if not P.has_finite_order():1683raise ValueError, "The points in the kernel must be of finite order."1684# work around the current implementation of torsion points. When they are done better this could be1685# reduced but it won't speed things up too much.1686kernel_list = Set([self.__E1(0)])1687for P in kernel_gens:1688points_to_add = []1689for j in range(P.order()):1690for Q in kernel_list:1691points_to_add.append(j*P+Q)1692kernel_list += Set(points_to_add)16931694self.__kernel_list = kernel_list.list()1695self.__kernel_2tor = {}1696self.__kernel_non2tor = {}16971698self.__degree = len(kernel_list)16991700self.__sort_kernel_list()17011702return170317041705#1706# Precompute the values in Velu's Formula.1707#1708def __sort_kernel_list(self):1709r"""1710Private function that sorts the list of points in the kernel1711(For Velu's formulas). Sorts out the 2 torsion points, and1712puts them in a dictionary.17131714EXAMPLES:17151716The following example inherently exercises this function::17171718sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1719sage: P = E((4,2))1720sage: phi = EllipticCurveIsogeny(E, P); phi1721Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 71722sage: phi._EllipticCurveIsogeny__kernel_2tor = {}1723sage: phi._EllipticCurveIsogeny__kernel_non2tor = {}1724sage: phi._EllipticCurveIsogeny__sort_kernel_list()17251726"""17271728a1,a2,a3,a4,a6 = self.__E1.ainvs()17291730v = 01731w = 017321733for Q in self.__kernel_list:17341735if Q.is_zero():1736continue17371738(xQ,yQ) = Q.xy()17391740gxQ = 3*xQ**2 + 2*a2*xQ + a4 - a1*yQ1741gyQ = -2*yQ - a1*xQ - a317421743uQ = gyQ**217441745# sort torsion points:1746if (2*yQ == -a1*xQ - a3): # Q is 2-torsion1747vQ = gxQ1748self.__kernel_2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ)1749v = v + vQ1750w = w + (uQ + xQ*vQ)1751elif (not self.__kernel_non2tor.has_key(xQ)): # Q is not a 2-torsion1752vQ = 2*gxQ - a1*gyQ1753self.__kernel_non2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ)1754v = v + vQ1755w = w + (uQ + xQ*vQ)17561757self.__v = v1758self.__w = w17591760return176117621763#1764# Velu's formula computing the codomain curve1765#1766def __compute_E2_via_velu(self):1767r"""1768Private function that computes the codomain via Velu's1769formulas.17701771EXAMPLES:17721773The following example inherently exercises this function::17741775sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1776sage: P = E((4,2))1777sage: phi = EllipticCurveIsogeny(E, P);1778sage: phi.codomain()1779Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 71780sage: phi._EllipticCurveIsogeny__compute_E2_via_velu()1781Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 717821783"""1784v = self.__v1785w = self.__w17861787return compute_codomain_formula(self.__E1, v,w)178817891790def __velu_sum_helper(self, Qvalues, a1, a3, x, y):1791r"""1792Private function for Velu's formulas, helper function to help1793perform the summation.17941795EXAMPLES:17961797The following example inherently exercises this function::17981799sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1800sage: P = E((4,2))1801sage: phi = EllipticCurveIsogeny(E, P);1802sage: Q = E((0,0)); phi(Q)1803(0 : 0 : 1)1804sage: phi.rational_maps()1805((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1806(x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))18071808sage: E = EllipticCurve(GF(7), [0,0,0,1,0])1809sage: phi = EllipticCurveIsogeny(E, E((0,0)) )1810sage: Qvals = phi._EllipticCurveIsogeny__kernel_2tor[0]1811sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, 5, 5)1812(3, 3)1813sage: R.<x,y> = GF(7)[]1814sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, x, y)1815(1/x, y/x^2)18161817"""1818xQ = Qvalues[0]1819yQ = Qvalues[1]1820gxQ = Qvalues[2]1821gyQ = Qvalues[3]1822vQ = Qvalues[4]1823uQ = Qvalues[5]18241825t1 = x - xQ1826inv_t1 = t1**-11827inv_t1_2 = inv_t1**21828inv_t1_3 = inv_t1_2*inv_t118291830tX = vQ*inv_t1 + uQ*(inv_t1_2)18311832tY0 = uQ*(2*y + a1*x + a3)1833tY1 = vQ*(a1*t1 + y - yQ)1834tY2 = a1*uQ - gxQ*gyQ18351836tY = ( tY0*inv_t1_3 + (tY1 + tY2)*inv_t1_2 )18371838return (tX, tY)183918401841def __compute_via_velu_numeric(self, xP, yP):1842r"""1843Private function that sorts the list of points in the kernel1844(for Velu's formulas). Sorts out the 2 torsion points, and1845puts them in a diction18461847EXAMPLES:18481849The following example inherently exercises this function::18501851sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1852sage: P = E((4,2))1853sage: phi = EllipticCurveIsogeny(E, P);1854sage: Q = E((0,0)); phi(Q)1855(0 : 0 : 1)1856sage: Q = E((-1,0)); phi(Q)1857(0 : 0 : 1)1858sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(0, 0)1859(0, 0)1860sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(-1, 0)1861(0, 0)18621863"""1864# first check if the point is in the kernel1865if ( self.__kernel_2tor.has_key(xP) or self.__kernel_non2tor.has_key(xP) ) :1866return self.__intermediate_codomain(0)18671868outP = self.__compute_via_velu(xP,yP)18691870return outP187118721873def __compute_via_velu(self, xP, yP):1874r"""1875Private function for Velu's formulas, to perform the1876summation.18771878EXAMPLES:18791880The following example inherently exercises this function::18811882sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1883sage: P = E((4,2))1884sage: phi = EllipticCurveIsogeny(E, P);1885sage: Q = E((0,0)); phi(Q)1886(0 : 0 : 1)1887sage: phi.rational_maps()1888((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1889(x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))1890sage: phi._EllipticCurveIsogeny__compute_via_velu(0, 0)1891(0, 0)1892sage: R.<x,y> = GF(7)[]1893sage: phi._EllipticCurveIsogeny__compute_via_velu(x, y)1894((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1895(x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))18961897"""18981899ker_2tor = self.__kernel_2tor1900ker_non2tor = self.__kernel_non2tor19011902X = 01903Y = 019041905a1 = self.__E1.a1()1906a3 = self.__E1.a3()19071908# next iterate over the 2torsion points of the kernel1909for Qvalues in ker_2tor.itervalues():1910(tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP)1911X = X + tX1912Y = Y + tY19131914for Qvalues in ker_non2tor.itervalues():1915(tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP)1916X = X + tX1917Y = Y + tY19181919X = xP + X1920Y = yP - Y19211922return (X,Y)192319241925def __initialize_rational_maps_via_velu(self):1926r"""1927Private function for Velu's formulas, helper function to initialize the rational maps.19281929EXAMPLES:19301931The following example inherently exercises this function::19321933sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1934sage: P = E((4,2))1935sage: phi = EllipticCurveIsogeny(E, P);1936sage: phi.rational_maps()1937((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1938(x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))1939sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_velu()1940((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1941(x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))19421943"""19441945x = self.__x_var1946y = self.__y_var19471948return self.__compute_via_velu(x,y)194919501951def __init_kernel_polynomial_velu(self):1952r"""1953Private function for Velu's formulas, helper function to1954initialize the rational maps.19551956EXAMPLES:19571958The following example inherently exercises this function::19591960sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1961sage: P = E((4,2))1962sage: phi = EllipticCurveIsogeny(E, P);1963sage: phi.kernel_polynomial()1964x^2 + 2*x + 41965sage: phi._EllipticCurveIsogeny__init_kernel_polynomial_velu()1966[4, 2, 1]19671968"""19691970poly_ring = self.__poly_ring1971x = self.__x_var19721973invX = 019741975if (self.__pre_isomorphism is not None):1976pre_isom = self.__pre_isomorphism1977u = pre_isom.u1978r = pre_isom.r1979invX = (u**2)*x + r1980else:1981invX = x19821983psi = poly_ring(1)19841985for Qvalues in self.__kernel_2tor.itervalues():1986xQ = invX(x=Qvalues[0])1987psi = psi*(x - xQ)19881989for Qvalues in self.__kernel_non2tor.itervalues():1990xQ = invX(x=Qvalues[0])1991psi = psi*(x - xQ)19921993ker_poly_list = psi.univariate_polynomial().list()19941995self.__kernel_polynomial_list = ker_poly_list1996self.__kernel_polynomial = psi19971998return ker_poly_list1999200020012002###################################2003# Kohel's Variant of Velu's Formula2004###################################20052006def __init_from_kernel_polynomial(self, kernel_polynomial, degree=None):2007r"""2008Private function that initializes the isogeny from a kernel2009polynomial.20102011EXAMPLES:20122013These examples inherently exercise this private function::20142015sage: R.<x> = GF(7)[]2016sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])2017sage: phi = EllipticCurveIsogeny(E, x);phi2018Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 720192020sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x)20212022sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2023sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi2024Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 720252026sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x+6, degree=3)20272028"""20292030poly_ring = self.__poly_ring2031x = self.__x_var20322033E = self.__E120342035if(is_Polynomial(kernel_polynomial)):2036kernel_polynomial = kernel_polynomial.list()20372038n = len(kernel_polynomial)-120392040if kernel_polynomial[-1] != 1:2041raise ValueError, "The kernel polynomial must be monic."20422043self.__kernel_polynomial_list = kernel_polynomial20442045psi = 02046for j in xrange(len(kernel_polynomial)):2047psi = psi*x + kernel_polynomial[n-j]204820492050#2051# Determine if kernel polynomial is entirely a two torsion2052#2053psi_G = two_torsion_part(E, poly_ring, psi, degree);20542055# force this polynomial to be monic:2056psi_G = psi_G/psi_G.univariate_polynomial().leading_coefficient()20572058if (0 != psi_G.degree()): # even degree case20592060psi_quo = poly_ring(psi/psi_G)20612062if (0 != psi_quo.degree()):2063raise NotImplementedError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion."20642065(phi, omega, v, w, n, d) = self.__init_even_kernel_polynomial(E, psi_G)20662067else: # odd degree case20682069(phi, omega, v, w, n, d) = self.__init_odd_kernel_polynomial(E, psi)207020712072#2073# Set up the necessary instance variables2074#20752076self.__kernel_polynomial = psi2077self.__inner_kernel_polynomial = psi20782079self.__n = n2080self.__degree = d20812082self.__psi = psi2083self.__phi = phi2084self.__omega = omega20852086self.__v = v2087self.__w = w20882089return209020912092def __init_even_kernel_polynomial(self, E, psi_G):2093r"""2094Private function that initializes the isogeny from a kernel2095polynomial, for Kohel's algorithm in the even degree case.20962097EXAMPLES:20982099These examples inherently exercise this private function::21002101sage: R.<x> = GF(7)[]2102sage: E = EllipticCurve(GF(7), [-1,0])2103sage: phi = EllipticCurveIsogeny(E, x);phi2104Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 721052106sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part2107sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var)2108sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)2109(x^3 - x, x^3*y + x*y, 6, 0, 1, 2)21102111sage: F = GF(2^4, 'alpha'); R.<x> = F[]2112sage: E = EllipticCurve(F, [1,1,0,1,0])2113sage: phi = EllipticCurveIsogeny(E, x); phi2114Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + x over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + 1 over Finite Field in alpha of size 2^421152116sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var)2117sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)2118(x^3 + x, x^3*y + x^2 + x*y, 1, 0, 1, 2)21192120sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2121sage: R.<x> = GF(7)[]2122sage: f = x^3 + 6*x^2 + 12123sage: phi = EllipticCurveIsogeny(E, f); phi2124Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 2*x + 5 over Finite Field of size 72125sage: psig = two_torsion_part(E,R,f,None)2126sage: psig = two_torsion_part(E,R,f,None)(phi._EllipticCurveIsogeny__x_var)2127sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)2128(x^7 - 2*x^6 + 2*x^5 - x^4 + 3*x^3 - 2*x^2 - x + 3,2129x^9*y - 3*x^8*y + 2*x^7*y - 3*x^3*y + 2*x^2*y + x*y - y,21301,21316,21323,21334)213421352136"""213721382139#check if the polynomial really divides the two_torsion_polynomial2140if self.__check and E.division_polynomial(2, x=self.__x_var) % psi_G != 0 :2141raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve."21422143n = psi_G.degree()2144d = n+121452146base_field = self.__base_field2147char = base_field.characteristic()21482149x = self.__x_var2150y = self.__y_var21512152a1,a2,a3,a4,a6 = E.ainvs()21532154b2 = E.b2()2155b4 = E.b4()21562157if (1 == n):2158x0 = -psi_G.constant_coefficient()21592160# determine y02161if (2 == char):2162y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt()2163else:2164y0 = -(a1*x0 + a3)/221652166(v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4)21672168phi = (x*psi_G + v)*psi_G2169omega = (y*psi_G**2 - v*(a1*psi_G + (y - y0)))*psi_G21702171elif (3 == n):2172s = psi_G.univariate_polynomial().list()2173s1 = -s[n-1]2174s2 = s[n-2]2175s3 = -s[n-3]21762177psi_G_pr = psi_G.derivative(x)2178psi_G_prpr = psi_G_pr.derivative(x)21792180phi = (psi_G_pr**2) + (-2*psi_G_prpr + (4*x - s1))*psi_G21812182phi_pr = phi.derivative(x)21832184psi_2 = 2*y + a1*x + a321852186omega = (psi_2*(phi_pr*psi_G - phi*psi_G_pr) - (a1*phi + a3*psi_G)*psi_G)/221872188phi = phi*psi_G2189omega = omega*psi_G21902191(v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3)21922193else:2194raise ValueError, "input polynomial must be of degree 1 or 3, not %d" % n21952196return (phi, omega, v, w, n, d)219721982199def __init_odd_kernel_polynomial(self, E, psi):2200r"""2201Private function that initializes the isogeny from a kernel2202polynomial.22032204EXAMPLES:22052206These examples inherently exercise this private function::22072208sage: R.<x> = GF(7)[]2209sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2210sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi2211Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 722122213sage: R.<x,y> = GF(7)[]2214sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, x+6)2215(x^3 - 2*x^2 + 3*x + 2, x^3*y - 3*x^2*y + x*y, 2, 6, 1, 3)22162217sage: F = GF(2^4, 'alpha'); R.<x> = F[]2218sage: alpha = F.gen()2219sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1])2220sage: f = x + alpha^2 + 12221sage: phi = EllipticCurveIsogeny(E, f); phi2222Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + (alpha^2+1)*x + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + alpha*x + alpha^3 over Finite Field in alpha of size 2^422232224sage: R.<x,y> = F[]2225sage: f = x + alpha^2 + 12226sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, f)2227(x^3 + (alpha^2 + 1)*x + (alpha^3 + alpha^2 + alpha),2228x^3*y + (alpha^2 + 1)*x^2*y + (alpha^2 + alpha + 1)*x^2 + (alpha^2 + 1)*x*y + (alpha^2 + alpha)*x + (alpha)*y + (alpha),2229alpha^2 + alpha + 1,2230alpha^3 + alpha^2 + alpha,22311,22323)22332234sage: E = EllipticCurve(j=-262537412640768000)2235sage: f = (E.isogenies_prime_degree()[0]).kernel_polynomial()2236sage: f.degree()2237812238sage: E.isogeny(kernel=f) # long time (21s)2239Isogeny of degree 163 from Elliptic Curve defined by y^2 + y = x^3 - 2174420*x + 1234136692 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 57772164980*x - 5344733777551611 over Rational Field22402241"""2242n = psi.degree()2243d = 2*n + 122442245# check if the polynomial really divides the torsion polynomial :2246if self.__check:2247alpha = psi.parent().quotient(psi).gen()2248if not E.division_polynomial(d, x=alpha).is_zero():2249raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve."22502251x = self.__x_var22522253b2 = E.b2()2254b4 = E.b4()2255b6 = E.b6()22562257psi_coeffs = psi.univariate_polynomial().list()22582259s1 = 0; s2 = 0; s3 = 022602261if (1 <= n):2262s1 = -psi_coeffs[n-1]22632264if (2 <= n):2265s2 = psi_coeffs[n-2]22662267if (3 <= n):2268s3 = -psi_coeffs[n-3]22692270# initializing these allows us to calculate E2.2271(v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n);22722273# initialize the polynomial temporary variables22742275psi_pr = psi.derivative(x)2276psi_prpr = psi_pr.derivative(x)22772278phi = (4*x**3 + b2*x**2 + 2*b4*x + b6)*(psi_pr**2 - psi_prpr*psi) - \2279(6*x**2 + b2*x + b4)*psi_pr*psi + (d*x - 2*s1)*psi**222802281phi_pr = phi.derivative(x)22822283omega = 02284if (2 != self.__base_field.characteristic()):2285omega = self.__compute_omega_fast(E, psi, psi_pr, phi, phi_pr)2286else:2287omega = self.__compute_omega_general(E, psi, psi_pr, phi, phi_pr)22882289return (phi, omega, v, w, n, d)229022912292#2293# This is the fast omega computation that works when characteristic is not 22294#2295def __compute_omega_fast(self, E, psi, psi_pr, phi, phi_pr):2296r"""2297Private function that initializes the omega polynomial (from2298Kohel's formulas) in the case that the characteristic of the2299underlying field is not 2.23002301EXAMPLES:23022303These examples inherently exercise this private function::23042305sage: R.<x> = GF(7)[]2306sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2307sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi2308Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 723092310sage: R.<x,y> = GF(7)[]2311sage: psi = phi._EllipticCurveIsogeny__psi2312sage: psi_pr = psi.derivative(x)2313sage: fi = phi._EllipticCurveIsogeny__phi2314sage: fi_pr = fi.derivative(x)2315sage: phi._EllipticCurveIsogeny__compute_omega_fast(E, psi, psi_pr, fi, fi_pr)2316x^3*y - 3*x^2*y + x*y23172318"""23192320a1 = E.a1()2321a3 = E.a3()23222323x = self.__x_var; # 'x'2324y = self.__y_var; # 'y'23252326psi_2 = 2*y + a1*x + a323272328# note, the formula below is correct2329# the formula in Kohel's thesis has some typos2330# notably the first plus sign should be a minus2331# as it is here below.23322333omega = phi_pr*psi*psi_2/2 - phi*psi_pr*psi_2 - \2334(a1*phi + a3*psi**2)*psi/223352336return omega233723382339def __compute_omega_general(self, E, psi, psi_pr, phi, phi_pr):2340r"""2341Private function that initializes the omega polynomial (from2342Kohel's formulas) in the case of general characteristic of the2343underlying field.23442345EXAMPLES:23462347These examples inherently exercise this private function::23482349sage: F = GF(2^4, 'alpha'); R.<x> = F[]2350sage: alpha = F.gen()2351sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1])2352sage: f = x + alpha^2 + 12353sage: phi = EllipticCurveIsogeny(E, f); phi2354Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + (alpha^2+1)*x + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + alpha*x + alpha^3 over Finite Field in alpha of size 2^423552356sage: R.<x,y> = F[]2357sage: psi = phi._EllipticCurveIsogeny__psi2358sage: psi_pr = psi.derivative(x)2359sage: fi = phi._EllipticCurveIsogeny__phi2360sage: fi_pr = fi.derivative(x)2361sage: phi._EllipticCurveIsogeny__compute_omega_general(E, psi, psi_pr, fi, fi_pr)2362x^3*y + (alpha^2 + 1)*x^2*y + (alpha^2 + alpha + 1)*x^2 + (alpha^2 + 1)*x*y + (alpha^2 + alpha)*x + (alpha)*y + (alpha)23632364A bug fixed in ticket #7907::23652366sage: F = GF(128,'a')2367sage: a = F.gen()2368sage: E = EllipticCurve([1,0,0,0,(a**6+a**4+a**2+a)])2369sage: x = polygen(F)2370sage: ker = (x^6 + (a^6 + a^5 + a^4 + a^3 + a^2 + a)*x^5 + (a^6 + a^5 + a^2 + 1)*x^4 + (a^6 + a^5 + a^4 + a^3 + a^2 + 1)*x^3 + (a^6 + a^3 + a)*x^2 + (a^4 + a^3 + 1)*x + a^5 + a^4 + a)2371sage: E.isogeny(ker)2372Isogeny of degree 13 from Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^4+a^2+a) over Finite Field in a of size 2^7 to Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^5+a^4+a^3+a^2+a)*x + (a^5+a^3) over Finite Field in a of size 2^7237323742375"""23762377a1,a2,a3,a4,a6 = E.ainvs()23782379b2 = E.b2()2380b4 = E.b4()23812382n = psi.degree()2383d = 2*n+123842385x = self.__x_var2386y = self.__y_var23872388psi_2 = 2*y + a1*x + a323892390psi_coeffs = psi.univariate_polynomial().list()23912392if (0 < n):2393s1 = -psi_coeffs[n-1]2394else:2395s1 = 023962397psi_prpr = 02398cur_x_pow = 123992400#2401# Note: we now get the "derivatives" of psi2402# these are not actually the derivatives2403# furthermore, the formulas in Kohel's2404# thesis are wrong, the correct formulas2405# are coded below2406#2407from sage.rings.arith import binomial24082409for j in xrange(0,n-1):2410psi_prpr = psi_prpr + \2411binomial(j+2,2)*psi_coeffs[(j+2)]*cur_x_pow2412cur_x_pow = x*cur_x_pow24132414psi_prprpr = 02415cur_x_pow = 124162417for j in xrange(0,n-2):2418psi_prprpr = psi_prprpr + \2419(3*binomial(j+3,3))*psi_coeffs[(j+3)]*cur_x_pow2420cur_x_pow = x*cur_x_pow242124222423omega = phi_pr*psi*y - phi*psi_pr*psi_2 + \2424((a1*x + a3)*(psi_2**2)*(psi_prpr*psi_pr-psi_prprpr*psi) + \2425(a1*psi_2**2 - 3*(a1*x + a3)*(6*x**2 + b2*x + b4))*psi_prpr*psi + \2426(a1*x**3 + 3*a3*x**2 + (2*a2*a3 - a1*a4)*x + (a3*a4 - 2*a1*a6))*psi_pr**2 + \2427(-(3*a1*x**2 + 6*a3*x + (-a1*a4 + 2*a2*a3)) + \2428(a1*x + a3)*(d*x - 2*s1) )*psi_pr*psi + (a1*s1 + a3*n)*psi**2)*psi24292430return omega243124322433def __compute_via_kohel_numeric(self, xP, yP):2434r"""2435Private function that computes a numeric result of this2436isogeny (via Kohel's formulas.)24372438EXAMPLES:24392440These examples inherently exercise this private function::24412442sage: R.<x> = GF(7)[]2443sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2444sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2445sage: P = E((0,1)); phi(P)2446(2 : 0 : 1)2447sage: P = E((1,1)); phi(P)2448(0 : 1 : 0)2449sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(0, 1)2450(2, 0)2451sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(1, 1)2452(0 : 1 : 0)24532454"""24552456# first check if this is a kernel point2457# to avoid a divide by 0 error later2458if(0 == self.__inner_kernel_polynomial(x=xP)):2459return self.__intermediate_codomain(0)24602461(xP_out, yP_out) = self.__compute_via_kohel(xP,yP)24622463# for some dang reason in some cases2464# when the base_field is a number field2465# xP_out and yP_out do not get evaluated to field elements2466# but rather constant polynomials.2467# So in this case, we do some explicit casting to make sure2468# everything comes out right24692470if is_NumberField(self.__base_field) and (1 < self.__base_field.degree()) :2471xP_out = self.__poly_ring(xP_out).constant_coefficient()2472yP_out = self.__poly_ring(yP_out).constant_coefficient()24732474return (xP_out,yP_out)247524762477def __compute_via_kohel(self, xP, yP):2478r"""2479Private function that applies Kohel's formulas.24802481EXAMPLES:24822483These examples inherently exercise this private function::24842485sage: R.<x> = GF(7)[]2486sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2487sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2488sage: P = E((0,1)); phi(P)2489(2 : 0 : 1)2490sage: phi.rational_maps()2491((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2492(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))2493sage: phi._EllipticCurveIsogeny__compute_via_kohel(0,1)2494(2, 0)2495sage: R.<x,y> = GF(7)[]2496sage: phi._EllipticCurveIsogeny__compute_via_kohel(x,y)2497((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2498(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))24992500"""25012502x = self.__x_var2503y = self.__y_var25042505psi_out = self.__psi(xP,yP)2506phi_out = self.__phi(xP,yP)2507omega_out =self.__omega(xP, yP)25082509psi_inv_out = 1/psi_out25102511psi_inv_sq_out = psi_inv_out**225122513X_out = phi_out*(psi_inv_sq_out)2514Y_out = omega_out*(psi_inv_sq_out*psi_inv_out)25152516return (X_out, Y_out)251725182519def __initialize_rational_maps_via_kohel(self):2520r"""2521Private function that computes and initializes the rational2522maps of this isogeny.25232524EXAMPLES:25252526These examples inherently exercise this private function::25272528sage: R.<x> = GF(7)[]2529sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2530sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2531sage: phi.rational_maps()2532((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2533(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))2534sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_kohel()2535((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2536(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))253725382539"""2540x = self.__x_var2541y = self.__y_var25422543(X,Y) = self.__compute_via_kohel(x,y)25442545return (X,Y)254625472548#2549# Kohel's formula computing the codomain curve2550#2551def __compute_E2_via_kohel(self):2552r"""2553Private function that computes and initializes the codomain of2554the isogeny (via Kohel's.)25552556EXAMPLES:25572558These examples inherently exercise this private function::25592560sage: R.<x> = GF(7)[]2561sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2562sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2563sage: phi.codomain()2564Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 72565sage: phi._EllipticCurveIsogeny__compute_E2_via_kohel()2566Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 725672568"""25692570v = self.__v2571w = self.__w25722573return compute_codomain_formula(self.__E1, v,w)2574257525762577#2578# public isogeny methods2579#25802581def domain(self):2582r"""2583Returns the domain curve of this isogeny.25842585EXAMPLES::25862587sage: E = EllipticCurve(QQ, [0,0,0,1,0])2588sage: phi = EllipticCurveIsogeny(E, E(0,0))2589sage: phi.domain() == E2590True25912592sage: E = EllipticCurve(GF(31), [1,0,0,1,2])2593sage: phi = EllipticCurveIsogeny(E, [17, 1])2594sage: phi.domain()2595Elliptic Curve defined by y^2 + x*y = x^3 + x + 2 over Finite Field of size 3125962597"""2598return self.__E1259926002601def codomain(self):2602r"""2603Returns the codomain (range) curve of this isogeny.26042605EXAMPLES::26062607sage: E = EllipticCurve(QQ, [0,0,0,1,0])2608sage: phi = EllipticCurveIsogeny(E, E((0,0)))2609sage: phi.codomain()2610Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field26112612sage: E = EllipticCurve(GF(31), [1,0,0,1,2])2613sage: phi = EllipticCurveIsogeny(E, [17, 1])2614sage: phi.codomain()2615Elliptic Curve defined by y^2 + x*y = x^3 + 24*x + 6 over Finite Field of size 3126162617"""2618return self.__E2261926202621def degree(self):2622r"""2623Returns the degree of this isogeny.26242625EXAMPLES::26262627sage: E = EllipticCurve(QQ, [0,0,0,1,0])2628sage: phi = EllipticCurveIsogeny(E, E((0,0)))2629sage: phi.degree()263022631sage: phi = EllipticCurveIsogeny(E, [0,1,0,1])2632sage: phi.degree()2633426342635sage: E = EllipticCurve(GF(31), [1,0,0,1,2])2636sage: phi = EllipticCurveIsogeny(E, [17, 1])2637sage: phi.degree()2638326392640"""2641return self.__degree264226432644def rational_maps(self):2645r"""2646This function returns this isogeny as a pair of rational maps.26472648EXAMPLES::26492650sage: E = EllipticCurve(QQ, [0,2,0,1,-1])2651sage: phi = EllipticCurveIsogeny(E, [1])2652sage: phi.rational_maps()2653(x, y)26542655sage: E = EllipticCurve(GF(17), [0,0,0,3,0])2656sage: phi = EllipticCurveIsogeny(E, E((0,0)))2657sage: phi.rational_maps()2658((x^2 + 3)/x, (x^2*y - 3*y)/x^2)265926602661"""2662if (not self.__rational_maps_initialized):2663self.__initialize_rational_maps()2664return (self.__X_coord_rational_map, self.__Y_coord_rational_map)266526662667def is_separable(self):2668r"""2669This function returns a bool indicating whether or not this2670isogeny is separable.26712672This function always returns ``True`` as currently this class2673only implements separable isogenies.26742675EXAMPLES::26762677sage: E = EllipticCurve(GF(17), [0,0,0,3,0])2678sage: phi = EllipticCurveIsogeny(E, E((0,0)))2679sage: phi.is_separable()2680True26812682sage: E = EllipticCurve('11a1')2683sage: phi = EllipticCurveIsogeny(E, E.torsion_points())2684sage: phi.is_separable()2685True268626872688"""2689return self.__separable269026912692def kernel_polynomial(self):2693r"""2694Returns the kernel polynomial of this isogeny.26952696EXAMPLES::26972698sage: E = EllipticCurve(QQ, [0,0,0,2,0])2699sage: phi = EllipticCurveIsogeny(E, E((0,0)))2700sage: phi.kernel_polynomial()2701x27022703sage: E = EllipticCurve('11a1')2704sage: phi = EllipticCurveIsogeny(E, E.torsion_points())2705sage: phi.kernel_polynomial()2706x^2 - 21*x + 8027072708sage: E = EllipticCurve(GF(17), [1,-1,1,-1,1])2709sage: phi = EllipticCurveIsogeny(E, [1])2710sage: phi.kernel_polynomial()2711127122713sage: E = EllipticCurve(GF(31), [0,0,0,3,0])2714sage: phi = EllipticCurveIsogeny(E, [0,3,0,1])2715sage: phi.kernel_polynomial()2716x^3 + 3*x271727182719"""2720if (self.__kernel_polynomial is None):2721self.__init_kernel_polynomial()27222723return self.__kernel_polynomial.univariate_polynomial()272427252726def set_pre_isomorphism(self, preWI):2727r"""2728Modifies this isogeny object to pre compose with the given2729Weierstrass isomorphism.27302731EXAMPLES::27322733sage: E = EllipticCurve(GF(31), [1,1,0,1,-1])2734sage: R.<x> = GF(31)[]2735sage: f = x^3 + 9*x^2 + x + 302736sage: phi = EllipticCurveIsogeny(E, f)2737sage: Epr = E.short_weierstrass_model()2738sage: isom = Epr.isomorphism_to(E)2739sage: phi.set_pre_isomorphism(isom)2740sage: phi.rational_maps()2741((-6*x^4 - 3*x^3 + 12*x^2 + 10*x - 1)/(x^3 + x - 12),2742(3*x^7 + x^6*y - 14*x^6 - 3*x^5 + 5*x^4*y + 7*x^4 + 8*x^3*y - 8*x^3 - 5*x^2*y + 5*x^2 - 14*x*y + 14*x - 6*y - 6)/(x^6 + 2*x^4 + 7*x^3 + x^2 + 7*x - 11))2743sage: phi(Epr((0,22)))2744(13 : 21 : 1)2745sage: phi(Epr((3,7)))2746(14 : 17 : 1)27472748sage: E = EllipticCurve(GF(29), [0,0,0,1,0])2749sage: R.<x> = GF(29)[]2750sage: f = x^2 + 52751sage: phi = EllipticCurveIsogeny(E, f)2752sage: phi2753Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 20*x over Finite Field of size 292754sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2755sage: inv_isom = WeierstrassIsomorphism(E, (1,-2,5,10))2756sage: Epr = inv_isom.codomain().codomain()2757sage: isom = Epr.isomorphism_to(E)2758sage: phi.set_pre_isomorphism(isom); phi2759Isogeny of degree 5 from Elliptic Curve defined by y^2 + 10*x*y + 20*y = x^3 + 27*x^2 + 6 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 20*x over Finite Field of size 292760sage: phi(Epr((12,1)))2761(26 : 0 : 1)2762sage: phi(Epr((2,9)))2763(0 : 0 : 1)2764sage: phi(Epr((21,12)))2765(3 : 0 : 1)2766sage: phi.rational_maps()[0]2767(x^5 - 10*x^4 - 6*x^3 - 7*x^2 - x + 3)/(x^4 - 8*x^3 + 5*x^2 - 14*x - 6)27682769sage: E = EllipticCurve('11a1')2770sage: R.<x> = QQ[]2771sage: f = x^2 - 21*x + 802772sage: phi = EllipticCurveIsogeny(E, f); phi2773Isogeny 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 Field2774sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2775sage: Epr = E.short_weierstrass_model()2776sage: isom = Epr.isomorphism_to(E)2777sage: phi.set_pre_isomorphism(isom)2778sage: phi2779Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 - 13392*x - 1080432 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field2780sage: phi(Epr((168,1188)))2781(0 : 1 : 0)27822783"""27842785WIdom = preWI.domain().codomain()2786WIcod = preWI.codomain().codomain()27872788if (type(preWI) != WeierstrassIsomorphism):2789raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism."27902791if (self.__E1 != WIcod):2792raise ValueError, "Invalid parameter: isomorphism must have codomain curve equal to this isogenies' domain."27932794if (self.__pre_isomorphism is None):2795isom = preWI2796domain = WIdom2797else:2798isom = self.__pre_isomorphism*preWI2799domain = WIdom28002801self.__clear_cached_values()28022803self.__set_pre_isomorphism(domain, isom)28042805return280628072808def set_post_isomorphism(self, postWI):2809r"""2810Modifies this isogeny object to post compose with the given2811Weierstrass isomorphism.28122813EXAMPLES::28142815sage: E = EllipticCurve(j=GF(31)(0))2816sage: R.<x> = GF(31)[]2817sage: phi = EllipticCurveIsogeny(E, x+18)2818sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2819sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (6,8,10,12)))2820sage: phi2821Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 31 to Elliptic Curve defined by y^2 + 24*x*y + 7*y = x^3 + 22*x^2 + 16*x + 20 over Finite Field of size 3128222823sage: E = EllipticCurve(j=GF(47)(0))2824sage: f = E.torsion_polynomial(3)/32825sage: phi = EllipticCurveIsogeny(E, f)2826sage: E2 = phi.codomain()2827sage: post_isom = E2.isomorphism_to(E)2828sage: phi.set_post_isomorphism(post_isom)2829sage: phi.rational_maps() == E.multiplication_by_m(3)2830False2831sage: phi.switch_sign()2832sage: phi.rational_maps() == E.multiplication_by_m(3)2833True28342835Example over a number field::28362837sage: R.<x> = QQ[]2838sage: K.<a> = NumberField(x^2 + 2)2839sage: E = EllipticCurve(j=K(1728))2840sage: ker_list = E.torsion_points()2841sage: phi = EllipticCurveIsogeny(E, ker_list)2842sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2843sage: post_isom = WeierstrassIsomorphism(phi.codomain(), (a,2,3,5))2844sage: phi2845Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^2 + 2 to Elliptic Curve defined by y^2 = x^3 + (-44)*x + 112 over Number Field in a with defining polynomial x^2 + 228462847"""28482849WIdom = postWI.domain().codomain()2850WIcod = postWI.codomain().codomain()28512852if (type(postWI) != WeierstrassIsomorphism):2853raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism."28542855if (self.__E2 != WIdom):2856raise ValueError, "Invalid parameter: isomorphism must have domain curve equal to this isogenies' codomain."28572858if (self.__post_isomorphism is None):2859isom = postWI2860codomain = WIcod2861else:2862isom = postWI*self.__post_isomorphism2863codomain = WIcod28642865self.__clear_cached_values()28662867self.__set_post_isomorphism(codomain, isom)28682869return287028712872def get_pre_isomorphism(self):2873r"""2874Returns the pre-isomorphism of this isogeny. If there has2875been no pre-isomorphism set, this returns ``None``.28762877EXAMPLES::28782879sage: E = EllipticCurve(GF(31), [1,1,0,1,-1])2880sage: R.<x> = GF(31)[]2881sage: f = x^3 + 9*x^2 + x + 302882sage: phi = EllipticCurveIsogeny(E, f)2883sage: phi.get_post_isomorphism()2884sage: Epr = E.short_weierstrass_model()2885sage: isom = Epr.isomorphism_to(E)2886sage: phi.set_pre_isomorphism(isom)2887sage: isom == phi.get_pre_isomorphism()2888True28892890sage: E = EllipticCurve(GF(83), [1,0,1,1,0])2891sage: R.<x> = GF(83)[]; f = x+242892sage: phi = EllipticCurveIsogeny(E, f)2893sage: E2 = phi.codomain()2894sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2)2895sage: phi2.get_pre_isomorphism()2896Generic morphism:2897From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 832898To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 832899Via: (u,r,s,t) = (1, 76, 41, 3)2900290129022903"""2904return self.__pre_isomorphism290529062907def get_post_isomorphism(self):2908r"""2909Returns the post-isomorphism of this isogeny. If there has2910been no post-isomorphism set, this returns ``None``.29112912EXAMPLES::29132914sage: E = EllipticCurve(j=GF(31)(0))2915sage: R.<x> = GF(31)[]2916sage: phi = EllipticCurveIsogeny(E, x+18)2917sage: phi.get_post_isomorphism()2918sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2919sage: isom = WeierstrassIsomorphism(phi.codomain(), (6,8,10,12))2920sage: phi.set_post_isomorphism(isom)2921sage: isom == phi.get_post_isomorphism()2922True29232924sage: E = EllipticCurve(GF(83), [1,0,1,1,0])2925sage: R.<x> = GF(83)[]; f = x+242926sage: phi = EllipticCurveIsogeny(E, f)2927sage: E2 = phi.codomain()2928sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2)2929sage: phi2.get_post_isomorphism()2930Generic morphism:2931From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 832932To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 832933Via: (u,r,s,t) = (1, 7, 42, 80)29342935"""2936return self.__post_isomorphism293729382939def switch_sign(self):2940r"""2941This function composes the isogeny with `[-1]` (flipping the2942coefficient between +/-1 on the `y` coordinate rational map).29432944EXAMPLES::29452946sage: E = EllipticCurve(GF(23), [0,0,0,1,0])2947sage: f = E.torsion_polynomial(3)/32948sage: phi = EllipticCurveIsogeny(E, f, E)2949sage: phi.rational_maps() == E.multiplication_by_m(3)2950False2951sage: phi.switch_sign()2952sage: phi.rational_maps() == E.multiplication_by_m(3)2953True29542955sage: E = EllipticCurve(GF(17), [-2, 3, -5, 7, -11])2956sage: R.<x> = GF(17)[]2957sage: f = x+62958sage: phi = EllipticCurveIsogeny(E, f)2959sage: phi2960Isogeny of degree 2 from Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 7*x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 4*x + 8 over Finite Field of size 172961sage: phi.rational_maps()2962((x^2 + 6*x + 4)/(x + 6), (x^2*y - 5*x*y + 8*x - 2*y)/(x^2 - 5*x + 2))2963sage: phi.switch_sign()2964sage: phi2965Isogeny of degree 2 from Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 7*x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 4*x + 8 over Finite Field of size 172966sage: phi.rational_maps()2967((x^2 + 6*x + 4)/(x + 6),2968(2*x^3 - x^2*y - 5*x^2 + 5*x*y - 4*x + 2*y + 7)/(x^2 - 5*x + 2))29692970sage: E = EllipticCurve('11a1')2971sage: R.<x> = QQ[]2972sage: f = x^2 - 21*x + 802973sage: phi = EllipticCurveIsogeny(E, f)2974sage: (xmap1, ymap1) = phi.rational_maps()2975sage: phi.switch_sign()2976sage: (xmap2, ymap2) = phi.rational_maps()2977sage: xmap1 == xmap22978True2979sage: ymap1 == -ymap2 - E.a1()*xmap2 - E.a3()2980True29812982sage: K.<a> = NumberField(x^2 + 1)2983sage: E = EllipticCurve(K, [0,0,0,1,0])2984sage: R.<x> = K[]2985sage: phi = EllipticCurveIsogeny(E, x-a)2986sage: phi.rational_maps()2987((x^2 + (-a)*x - 2)/(x + (-a)), (x^2*y + (-2*a)*x*y + y)/(x^2 + (-2*a)*x - 1))2988sage: phi.switch_sign()2989sage: phi.rational_maps()2990((x^2 + (-a)*x - 2)/(x + (-a)), (-x^2*y + (2*a)*x*y - y)/(x^2 + (-2*a)*x - 1))29912992"""2993self.set_post_isomorphism(WeierstrassIsomorphism(self.__E2, (-1,0,-self.__E2.a1(),-self.__E2.a3())))29942995def is_normalized(self, via_formal=True, check_by_pullback=True):2996r"""2997Returns ``True`` if this isogeny is normalized. An isogeny2998`\varphi\colon E\to E_2` between two given Weierstrass2999equations is said to be normalized if the constant `c` is `1`3000in `\varphi*(\omega_2) = c\cdot\omega`, where `\omega` and3001`omega_2` are the invariant differentials on `E` and `E_2`3002corresponding to the given equation.30033004INPUT:30053006- ``via_formal`` - (default: ``True``) If ``True`` it simply checks if3007the leading term of the formal series is 1. Otherwise3008it uses a deprecated algorithm involving the second3009optional argument.30103011- ``check_by_pullback`` - (default:``True``) Deprecated.30123013EXAMPLES::30143015sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism3016sage: E = EllipticCurve(GF(7), [0,0,0,1,0])3017sage: R.<x> = GF(7)[]3018sage: phi = EllipticCurveIsogeny(E, x)3019sage: phi.is_normalized()3020True3021sage: isom = WeierstrassIsomorphism(phi.codomain(), (3, 0, 0, 0))3022sage: phi.set_post_isomorphism(isom)3023sage: phi.is_normalized()3024False3025sage: isom = WeierstrassIsomorphism(phi.codomain(), (5, 0, 0, 0))3026sage: phi.set_post_isomorphism(isom)3027sage: phi.is_normalized()3028True3029sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))3030sage: phi.set_post_isomorphism(isom)3031sage: phi.is_normalized()3032True30333034sage: F = GF(2^5, 'alpha'); alpha = F.gen()3035sage: E = EllipticCurve(F, [1,0,1,1,1])3036sage: R.<x> = F[]3037sage: phi = EllipticCurveIsogeny(E, x+1)3038sage: isom = WeierstrassIsomorphism(phi.codomain(), (alpha, 0, 0, 0))3039sage: phi.is_normalized()3040True3041sage: phi.set_post_isomorphism(isom)3042sage: phi.is_normalized()3043False3044sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/alpha, 0, 0, 0))3045sage: phi.set_post_isomorphism(isom)3046sage: phi.is_normalized()3047True3048sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))3049sage: phi.set_post_isomorphism(isom)3050sage: phi.is_normalized()3051True30523053sage: E = EllipticCurve('11a1')3054sage: R.<x> = QQ[]3055sage: f = x^3 - x^2 - 10*x - 79/43056sage: phi = EllipticCurveIsogeny(E, f)3057sage: isom = WeierstrassIsomorphism(phi.codomain(), (2, 0, 0, 0))3058sage: phi.is_normalized()3059True3060sage: phi.set_post_isomorphism(isom)3061sage: phi.is_normalized()3062False3063sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/2, 0, 0, 0))3064sage: phi.set_post_isomorphism(isom)3065sage: phi.is_normalized()3066True3067sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))3068sage: phi.set_post_isomorphism(isom)3069sage: phi.is_normalized()3070True30713072"""3073# easy algorithm using the formal expansion.3074if via_formal:3075phi_formal = self.formal(prec=5)3076return phi_formal[1] == 130773078# this is the old algorithm. it should be deprecated.3079check_prepost_isomorphism = False30803081f_normalized = True30823083if (check_by_pullback):30843085(Xmap, Ymap) = self.rational_maps()30863087E1 = self.__E13088E2 = self.__E230893090a1 = E1.a1()3091a3 = E1.a3()30923093a1pr = E2.a1()3094a3pr = E2.a3()30953096x = self.__x_var3097y = self.__y_var30983099Xmap_pr = Xmap.derivative(x)31003101domain_inv_diff = 1/(2*y + a1*x + a3)3102codomain_inv_diff = Xmap_pr/(2*Ymap + a1pr*Xmap + a3pr)31033104inv_diff_quo = domain_inv_diff/codomain_inv_diff31053106if (1 == inv_diff_quo):3107f_normalized = True3108else:3109# For some reason, in certain cases, when the isogeny3110# is pre or post composed with a translation the3111# resulting rational functions are too complicated for3112# sage to simplify down to a constant in this case, we3113# do some cheating by checking if the post-composition3114# by isogeny has a non 1 scaling factor3115if ( inv_diff_quo.numerator().is_constant() and (inv_diff_quo.denominator().is_constant) ):3116f_normalized = False3117else:3118check_prepost_isomorphism = True3119else:3120check_prepost_isomorphism = True31213122# If we skip checking by the pullback of the invariant3123# differential OR if that was inconclusive We explicitly check3124# if there is a post isomorphism and if it has a non 1 scaling3125# factor or if it is a just a translation. NOTE: This only3126# works because we are using algorithms for calculating the3127# isogenies that calculate a separable normalized isogeny, if3128# this changes, this check will no longer be correct.3129#3130if (check_prepost_isomorphism):3131post_isom = self.__post_isomorphism3132if (post_isom is not None):3133if (1 == self.__base_field(post_isom.u)):3134f_post_normalized = True3135else:3136f_post_normalized = False3137else:3138f_post_normalized = True31393140pre_isom = self.__pre_isomorphism3141if (pre_isom is not None):3142if (1 == self.__base_field(pre_isom.u)):3143f_pre_normalized = True3144else:3145f_pre_normalized = False3146else:3147f_pre_normalized = True31483149f_normalized = f_pre_normalized and f_post_normalized31503151return f_normalized31523153def dual(self):3154r"""3155Computes and returns the dual isogeny of this isogeny. If3156`\varphi\colon E \to E_2` is the given isogeny, then the dual3157is by definition the unique isogeny `\hat\varphi\colon E_2\to3158E` such that the compositions `\hat\varphi\circ\varphi` and3159`\varphi\circ\hat\varphi` are the multiplication `[n]` by the3160degree of `\varphi` on `E` and `E_2` respectively.31613162EXAMPLES::31633164sage: E = EllipticCurve('11a1')3165sage: R.<x> = QQ[]3166sage: f = x^2 - 21*x + 803167sage: phi = EllipticCurveIsogeny(E, f)3168sage: phi_hat = phi.dual()3169sage: phi_hat.domain() == phi.codomain()3170True3171sage: phi_hat.codomain() == phi.domain()3172True3173sage: (X, Y) = phi.rational_maps()3174sage: (Xhat, Yhat) = phi_hat.rational_maps()3175sage: Xm = Xhat.subs(x=X, y=Y)3176sage: Ym = Yhat.subs(x=X, y=Y)3177sage: (Xm, Ym) == E.multiplication_by_m(5)3178True31793180sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3181sage: R.<x> = GF(37)[]3182sage: f = x^3 + x^2 + 28*x + 333183sage: phi = EllipticCurveIsogeny(E, f)3184sage: phi_hat = phi.dual()3185sage: phi_hat.codomain() == phi.domain()3186True3187sage: phi_hat.domain() == phi.codomain()3188True3189sage: (X, Y) = phi.rational_maps()3190sage: (Xhat, Yhat) = phi_hat.rational_maps()3191sage: Xm = Xhat.subs(x=X, y=Y)3192sage: Ym = Yhat.subs(x=X, y=Y)3193sage: (Xm, Ym) == E.multiplication_by_m(7)3194True31953196sage: E = EllipticCurve(GF(31), [0,0,0,1,8])3197sage: R.<x> = GF(31)[]3198sage: f = x^2 + 17*x + 293199sage: phi = EllipticCurveIsogeny(E, f)3200sage: phi_hat = phi.dual()3201sage: phi_hat.codomain() == phi.domain()3202True3203sage: phi_hat.domain() == phi.codomain()3204True3205sage: (X, Y) = phi.rational_maps()3206sage: (Xhat, Yhat) = phi_hat.rational_maps()3207sage: Xm = Xhat.subs(x=X, y=Y)3208sage: Ym = Yhat.subs(x=X, y=Y)3209sage: (Xm, Ym) == E.multiplication_by_m(5)3210True32113212Test (for trac ticket 7096)::32133214sage: E = EllipticCurve('11a1')3215sage: phi = E.isogeny(E(5,5))3216sage: phi.dual().dual() == phi3217True32183219sage: k = GF(103)3220sage: E = EllipticCurve(k,[11,11])3221sage: phi = E.isogeny(E(4,4))3222sage: phi3223Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x + 11 over Finite Field of size 103 to Elliptic Curve defined by y^2 = x^3 + 25*x + 80 over Finite Field of size 1033224sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism3225sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(),(5,0,1,2)))3226sage: phi.dual().dual() == phi3227True32283229sage: E = EllipticCurve(GF(103),[1,0,0,1,-1])3230sage: phi = E.isogeny(E(60,85))3231sage: phi.dual()3232Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 84*x + 34 over Finite Field of size 103 to Elliptic Curve defined by y^2 + x*y = x^3 + x + 102 over Finite Field of size 10332333234"""32353236if (self.__base_field.characteristic() in [2,3]):3237raise NotImplemented32383239if (self.__dual is not None):3240return self.__dual32413242# trac 70963243(E1, E2pr, pre_isom, post_isom) = compute_intermediate_curves(self.codomain(), self.domain())32443245F = self.__base_field32463247d = self.__degree32483249# trac 70963250if F(d) == 0:3251raise NotImplementedError, "The dual isogeny is not separable, but only separable isogenies are implemented so far"32523253# trac 70963254# this should take care of the case when the isogeny is not normalized.3255u = self.formal(prec=5)[1]3256isom = WeierstrassIsomorphism(E2pr, (u/F(d), 0, 0, 0))32573258E2 = isom.codomain().codomain()32593260pre_isom = self.__E2.isomorphism_to(E1)3261post_isom = E2.isomorphism_to(self.__E1)32623263phi_hat = EllipticCurveIsogeny(E1, None, E2, d)32643265phi_hat.set_pre_isomorphism(pre_isom)3266phi_hat.set_post_isomorphism(post_isom)3267phi_hat.__perform_inheritance_housekeeping()32683269assert phi_hat.codomain() == self.domain()32703271# trac 7096 : this adjust a posteriori the automorphism3272# on the codomain of the dual isogeny.3273# we used _a_ Weierstrass isomorphism to get to the original3274# curve, but we may have to change it my an automorphism.3275# we impose that the composition has the degree3276# as a leading coefficient in the formal expansion.32773278phi_sc = self.formal(prec=5)[1]3279phihat_sc = phi_hat.formal(prec=5)[1]32803281sc = phi_sc * phihat_sc/F(d)32823283if sc != 1:3284auts = phi_hat.codomain().automorphsims()3285aut = [a for a in auts if a.u == sc]3286if len(aut) != 1:3287raise ValueError, "There is a bug in dual()."3288phi_hat.set_post_isomorphism(a[0])32893290self.__dual = phi_hat32913292return phi_hat32933294def formal(self,prec=20):3295r"""3296Computes the formal isogeny as a power series in the variable3297`t=-x/y` on the domain curve.32983299INPUT:33003301- ``prec`` - (default = 20), the precision with which the computations3302in the formal group are carried out.33033304EXAMPLES::33053306sage: E = EllipticCurve(GF(13),[1,7])3307sage: phi = E.isogeny(E(10,4))3308sage: phi.formal()3309t + 12*t^13 + 2*t^17 + 8*t^19 + 2*t^21 + O(t^23)33103311sage: E = EllipticCurve([0,1])3312sage: phi = E.isogeny(E(2,3))3313sage: phi.formal(prec=10)3314t + 54*t^5 + 255*t^7 + 2430*t^9 + 19278*t^11 + O(t^13)33153316sage: E = EllipticCurve('11a2')3317sage: R.<x> = QQ[]3318sage: phi = E.isogeny(x^2 + 101*x + 12751/5)3319sage: phi.formal(prec=7)3320t - 2724/5*t^5 + 209046/5*t^7 - 4767/5*t^8 + 29200946/5*t^9 + O(t^10)332133223323"""3324Eh = self.__E1.formal()3325f, g = self.rational_maps()3326xh = Eh.x(prec=prec)3327yh = Eh.y(prec=prec)3328fh = f(xh,yh)3329gh = g(xh,yh)3330return -fh/gh33313332#3333# Overload Morphism methods that we want to3334#33353336def _composition_(self, right, homset):3337r"""3338Composition operator function inherited from morphism class.33393340EXAMPLES::33413342sage: E = EllipticCurve(j=GF(7)(0))3343sage: phi = EllipticCurveIsogeny(E, [E(0), E((0,1)), E((0,-1))])3344sage: phi*phi3345Traceback (most recent call last):3346...3347NotImplementedError3348sage: phi._composition_(phi, phi.parent())3349Traceback (most recent call last):3350...3351NotImplementedError33523353"""3354raise NotImplementedError335533563357def is_injective(self):3358r"""3359Method inherited from the morphism class. Returns ``True`` if3360and only if this isogeny has trivial kernel.33613362EXAMPLES::33633364sage: E = EllipticCurve('11a1')3365sage: R.<x> = QQ[]3366sage: f = x^2 + x - 29/53367sage: phi = EllipticCurveIsogeny(E, f)3368sage: phi.is_injective()3369False3370sage: phi = EllipticCurveIsogeny(E, R(1))3371sage: phi.is_injective()3372True33733374sage: F = GF(7)3375sage: E = EllipticCurve(j=F(0))3376sage: phi = EllipticCurveIsogeny(E, [ E((0,-1)), E((0,1))])3377sage: phi.is_injective()3378False3379sage: phi = EllipticCurveIsogeny(E, E(0))3380sage: phi.is_injective()3381True33823383"""33843385if (1 < self.__degree): return False3386return True338733883389def is_surjective(self):3390r"""3391For elliptic curve isogenies, always returns ``True`` (as a3392non-constant map of algebraic curves must be surjective).33933394EXAMPLES::33953396sage: E = EllipticCurve('11a1')3397sage: R.<x> = QQ[]3398sage: f = x^2 + x - 29/53399sage: phi = EllipticCurveIsogeny(E, f)3400sage: phi.is_surjective()3401True34023403sage: E = EllipticCurve(GF(7), [0,0,0,1,0])3404sage: phi = EllipticCurveIsogeny(E, E((0,0)))3405sage: phi.is_surjective()3406True34073408sage: F = GF(2^5, 'omega')3409sage: E = EllipticCurve(j=F(0))3410sage: R.<x> = F[]3411sage: phi = EllipticCurveIsogeny(E, x)3412sage: phi.is_surjective()3413True34143415"""3416return True34173418def is_zero(self):3419r"""3420Member function inherited from morphism class.34213422EXAMPLES::34233424sage: E = EllipticCurve(j=GF(7)(0))3425sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3426sage: phi.is_zero()3427Traceback (most recent call last):3428...3429NotImplementedError3430"""3431raise NotImplementedError34323433def post_compose(self, left):3434r"""3435Member function inherited from morphism class.34363437EXAMPLES::34383439sage: E = EllipticCurve(j=GF(7)(0))3440sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3441sage: phi.post_compose(phi)3442Traceback (most recent call last):3443...3444NotImplementedError34453446"""3447raise NotImplementedError344834493450def pre_compose(self, right):3451r"""3452Member function inherited from morphism class.34533454EXAMPLES::34553456sage: E = EllipticCurve(j=GF(7)(0))3457sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3458sage: phi.pre_compose(phi)3459Traceback (most recent call last):3460...3461NotImplementedError34623463"""3464raise NotImplementedError346534663467def n(self):3468r"""3469Numerical Approximation inherited from Map (through morphism),3470nonsensical for isogenies.34713472EXAMPLES::34733474sage: E = EllipticCurve(j=GF(7)(0))3475sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3476sage: phi.n()3477Traceback (most recent call last):3478...3479NotImplementedError: Numerical approximations do not make sense for Elliptic Curve Isogenies34803481"""3482raise NotImplementedError, "Numerical approximations do not make sense for Elliptic Curve Isogenies"34833484# no longer needed (trac 7096)3485# def starks_find_r_and_t(T, Z):34863487def compute_isogeny_starks(E1, E2, ell):3488r"""3489Computes the degree ``ell`` isogeny between ``E1`` and ``E2`` via3490Stark's algorithm. There must be a degree ``ell``, separable,3491normalized cyclic isogeny from ``E1`` to ``E2``.34923493INPUT:34943495- ``E1`` - an elliptic curve in short Weierstrass form.3496- ``E2`` - an elliptic curve in short Weierstrass form.3497- ``ell`` - the degree of the isogeny from E1 to E2.34983499OUTPUT:35003501polynomial -- over the field of definition of ``E1``, ``E2``, that is the3502kernel polynomial of the isogeny from ``E1`` to ``E2``.35033504ALGORITHM:35053506This function uses Starks Algorithm as presented in section 6.2 of3507[BMSS].35083509.. note::35103511As published there, the algorithm is incorrect, and a correct3512version (with slightly different notation) can be found in3513[M09]. The algorithm originates in [S72]35143515REFERENCES:35163517- [BMSS] Boston, Morain, Salvy, Schost, "Fast Algorithms for Isogenies."3518- [M09] Moody, "The Diffie-Hellman Problem and Generalization of Verheul's Theorem"3519- [S72] Stark, "Class-numbers of complex quadratic fields."35203521EXAMPLES::35223523sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks, compute_sequence_of_maps35243525sage: E = EllipticCurve(GF(97), [1,0,1,1,0])3526sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 213527sage: phi = EllipticCurveIsogeny(E, f)3528sage: E2 = phi.codomain()3529sage: (isom1, isom2, E1pr, E2pr, ker_poly) = compute_sequence_of_maps(E, E2, 11)3530sage: compute_isogeny_starks(E1pr, E2pr, 11)3531x^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 + 835323533sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3534sage: R.<x> = GF(37)[]3535sage: f = (x + 14) * (x + 30)3536sage: phi = EllipticCurveIsogeny(E, f)3537sage: E2 = phi.codomain()3538sage: compute_isogeny_starks(E, E2, 5)3539x^4 + 14*x^3 + x^2 + 34*x + 213540sage: f**23541x^4 + 14*x^3 + x^2 + 34*x + 2135423543sage: E = EllipticCurve(QQ, [0,0,0,1,0])3544sage: R.<x> = QQ[]3545sage: f = x3546sage: phi = EllipticCurveIsogeny(E, f)3547sage: E2 = phi.codomain()3548sage: compute_isogeny_starks(E, E2, 2)3549x35503551"""35523553K = E1.base_field()3554R = PolynomialRing(K, 'x')3555x = R.gen()35563557wp1 = E1.weierstrass_p(prec=4*ell+4) #BMSS claim 2*ell is enough, but it is not M093558wp2 = E2.weierstrass_p(prec=4*ell+4)35593560# viewed them as power series in Z = z^23561S = LaurentSeriesRing(K, 'Z')3562Z = S.gen()3563pe1 = 1/Z3564pe2 = 1/Z3565for i in xrange(2*ell+1):3566pe1 += wp1[2*i] * Z**i3567pe2 += wp2[2*i] * Z**i3568pe1 = pe1.add_bigoh(2*ell+2)3569pe2 = pe2.add_bigoh(2*ell+2)35703571#print 'wps = ',pe13572#print 'wps2 = ',pe235733574n = 13575q = [R(1), R(0)]3576#p = [R(0), R(1)]3577T = pe235783579while ( q[n].degree() < (ell-1) ):3580#print 'n=', n35813582n += 13583a_n = 03584r = -T.valuation()3585while ( 0 <= r and T != 0):3586t_r = T[-r]3587#print ' r=',r3588#print ' t_r=',t_r3589#print ' T=',T3590a_n = a_n + t_r * x**r3591T = T - t_r*pe1**r3592r = -T.valuation()359335943595q_n = a_n*q[n-1] + q[n-2]3596q.append(q_n)3597#p_n = a_n*p[n-1] + q[n-2]3598#p.append(p_n)35993600if (n == ell+1 or T==0):3601if T.valuation()<2:3602raise ValueError, "The two curves are not linked by a cyclic normalized isogeny of degree %s"%ell3603#print 'breaks here'3604break36053606T = 1/T3607#print ' a_n=', a_n3608#print ' q_n=', q_n3609#print ' p_n=', p_n3610#print ' T = ', T36113612qn = q[n]3613#pn= p[n]3614#print 'final T = ', T3615#print ' f =', pn/qn36163617qn = (1/qn.leading_coefficient())*qn3618#pn = (1/qn.leading_coefficient())*pn36193620return qn36213622def split_kernel_polynomial(E1, ker_poly, ell):3623r"""3624Internal helper function for ``compute_isogeny_kernel_polynomial``.36253626Given a full kernel polynomial (where two torsion `x`-coordinates3627are roots of multiplicity 1, and all other roots have multiplicity36282.) of degree `\ell-1`, returns the maximum separable divisor.3629(i.e. the kernel polynomial with roots of multiplicity at most 1).36303631EXAMPLES:36323633The following example implicitly exercises this function::36343635sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3636sage: R.<x> = GF(37)[]3637sage: f = (x + 10) * (x + 12) * (x + 16)3638sage: phi = EllipticCurveIsogeny(E, f)3639sage: E2 = phi.codomain()3640sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks3641sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import split_kernel_polynomial3642sage: ker_poly = compute_isogeny_starks(E, E2, 7); ker_poly3643x^6 + 2*x^5 + 20*x^4 + 11*x^3 + 36*x^2 + 35*x + 163644sage: split_kernel_polynomial(E, ker_poly, 7)3645x^3 + x^2 + 28*x + 3336463647"""36483649poly_ring = ker_poly.parent()36503651z = poly_ring.gen(0)36523653ker_poly_2tor = two_torsion_part(E1, poly_ring, ker_poly, ell)3654ker_poly_quo = poly_ring(ker_poly/ker_poly_2tor)3655ker_poly_quo_sqrt = ker_poly_quo.gcd(ker_poly_quo.derivative(z))3656ker_poly = ker_poly_2tor*ker_poly_quo_sqrt3657ker_poly = (1/ker_poly.leading_coefficient())*ker_poly36583659return ker_poly366036613662def compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm="starks"):3663r"""3664Computes the kernel polynomial of the degree ``ell`` isogeny3665between ``E1`` and ``E2``. There must be a degree ``ell``,3666cyclic, separable, normalized isogeny from ``E1`` to ``E2``.36673668INPUT:36693670- ``E1`` - an elliptic curve in short Weierstrass form.36713672- ``E2`` - an elliptic curve in short Weierstrass form.36733674- ``ell`` - the degree of the isogeny from ``E1`` to ``E2``.36753676- ``algorithm`` - currently only ``starks`` (default) is implemented.36773678OUTPUT:36793680polynomial -- over the field of definition of ``E1``, ``E2``, that is the3681kernel polynomial of the isogeny from ``E1`` to ``E2``.36823683EXAMPLES::36843685sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_kernel_polynomial36863687sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3688sage: R.<x> = GF(37)[]3689sage: f = (x + 14) * (x + 30)3690sage: phi = EllipticCurveIsogeny(E, f)3691sage: E2 = phi.codomain()3692sage: compute_isogeny_kernel_polynomial(E, E2, 5)3693x^2 + 7*x + 133694sage: f3695x^2 + 7*x + 1336963697sage: R.<x> = QQ[]3698sage: K.<i> = NumberField(x^2 + 1)3699sage: E = EllipticCurve(K, [0,0,0,1,0])3700sage: E2 = EllipticCurve(K, [0,0,0,16,0])3701sage: compute_isogeny_kernel_polynomial(E, E2, 4)3702x^3 + x37033704"""37053706ker_poly = compute_isogeny_starks(E1, E2, ell)3707ker_poly = split_kernel_polynomial(E1, ker_poly, ell)37083709return ker_poly371037113712def compute_intermediate_curves(E1, E2):3713r"""3714Computes isomorphism from ``E1`` to an intermediate domain and an3715isomorphism from an intermediate codomain to ``E2``.37163717Intermediate domain and intermediate codomain, are in short3718Weierstrass form.37193720This is used so we can compute `\wp` functions from the short3721Weierstrass model more easily.37223723The underlying field must be of characteristic not equal to 2,3.37243725INPUT:37263727- ``E1`` - an elliptic curve3728- ``E2`` - an elliptic curve37293730OUTPUT:37313732tuple -- (``pre_isomorphism``, ``post_isomorphism``, ``intermediate_domain``,3733``intermediate_codomain``):37343735- ``intermediate_domain``: a short Weierstrass model isomorphic to ``E1``3736- ``intermediate_codomain``: a short Weierstrass model isomorphic to ``E2``3737- ``pre_isomorphism``: normalized isomorphism from ``E1`` to intermediate_domain3738- ``post_isomorphism``: normalized isomorphism from intermediate_codomain to ``E2``37393740EXAMPLES::37413742sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_intermediate_curves3743sage: E = EllipticCurve(GF(83), [1,0,1,1,0])3744sage: R.<x> = GF(83)[]; f = x+243745sage: phi = EllipticCurveIsogeny(E, f)3746sage: E2 = phi.codomain()3747sage: compute_intermediate_curves(E, E2)3748(Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83,3749Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83,3750Generic morphism:3751From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 833752To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 833753Via: (u,r,s,t) = (1, 76, 41, 3),3754Generic morphism:3755From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 833756To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 833757Via: (u,r,s,t) = (1, 7, 42, 80))37583759sage: R.<x> = QQ[]3760sage: K.<i> = NumberField(x^2 + 1)3761sage: E = EllipticCurve(K, [0,0,0,1,0])3762sage: E2 = EllipticCurve(K, [0,0,0,16,0])3763sage: compute_intermediate_curves(E, E2)3764(Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,3765Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1,3766Generic morphism:3767From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13768To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13769Via: (u,r,s,t) = (1, 0, 0, 0),3770Generic morphism:3771From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 13772To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 13773Via: (u,r,s,t) = (1, 0, 0, 0))37743775"""37763777if (E1.base_ring().characteristic() in [2,3]):3778raise NotImplemented37793780# compute the r,s,t values that clear the denominator of E13781a1 = E1.a1()3782a2 = E1.a2()3783a3 = E1.a3()37843785s1 = -a1/23786r1 = (s1**2 + s1*a1 - a2)/33787t1 = (-r1*a1 - a3)/237883789# compute the isomorphism from E1 to intermediate_domain3790pre_isom = WeierstrassIsomorphism(E1, (1, r1, s1, t1))37913792intermediate_domain = pre_isom.codomain().codomain()37933794# compute the r,s,t values that clear the denominator of E23795a1pr = E2.a1()3796a2pr = E2.a2()3797a3pr = E2.a3()37983799s2 = -a1pr/23800r2 = (s2**2 + s2*a1pr - a2pr)/33801t2 = (-r2*a1pr - a3pr)/238023803post_isom_inv = WeierstrassIsomorphism(E2, (1, r2, s2, t2))3804intermediate_codomain = post_isom_inv.codomain().codomain()38053806post_isom = WeierstrassIsomorphism(intermediate_codomain, (1, -r2, -s2, -t2))38073808return (intermediate_domain, intermediate_codomain, pre_isom, post_isom)380938103811def compute_sequence_of_maps(E1, E2, ell):3812r"""3813Given domain ``E1`` and codomain ``E2`` such that there is a3814degree ``ell`` separable normalized isogeny from ``E1`` to ``E2``,3815returns pre/post isomorphism, as well as intermediate domain and3816codomain, and kernel polynomial.38173818EXAMPLES::38193820sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_sequence_of_maps3821sage: E = EllipticCurve('11a1')3822sage: R.<x> = QQ[]; f = x^2 - 21*x + 803823sage: phi = EllipticCurveIsogeny(E, f)3824sage: E2 = phi.codomain()3825sage: compute_sequence_of_maps(E, E2, 5)3826(Generic morphism:3827From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field3828To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field3829Via: (u,r,s,t) = (1, 1/3, 0, -1/2),3830Generic morphism:3831From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field3832To: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field3833Via: (u,r,s,t) = (1, -1/3, 0, 1/2),3834Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field,3835Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field,3836x^2 - 61/3*x + 658/9)38373838sage: K.<i> = NumberField(x^2 + 1)3839sage: E = EllipticCurve(K, [0,0,0,1,0])3840sage: E2 = EllipticCurve(K, [0,0,0,16,0])3841sage: compute_sequence_of_maps(E, E2, 4)3842(Generic morphism:3843From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13844To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13845Via: (u,r,s,t) = (1, 0, 0, 0),3846Generic morphism:3847From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 13848To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 13849Via: (u,r,s,t) = (1, 0, 0, 0),3850Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,3851Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1,3852x^3 + x)38533854sage: E = EllipticCurve(GF(97), [1,0,1,1,0])3855sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 213856sage: phi = EllipticCurveIsogeny(E, f)3857sage: E2 = phi.codomain()3858sage: compute_sequence_of_maps(E, E2, 11)3859(Generic morphism:3860From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 973861To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 973862Via: (u,r,s,t) = (1, 8, 48, 44),3863Generic morphism:3864From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 973865To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 9*y = x^3 + 83*x + 6 over Finite Field of size 973866Via: (u,r,s,t) = (1, 89, 49, 53),3867Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97,3868Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97,3869x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69)38703871"""38723873(E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2)38743875ker_poly = compute_isogeny_kernel_polynomial(E1pr, E2pr, ell)38763877return (pre_isom, post_isom, E1pr, E2pr, ker_poly)387838793880##########################################################################3881# The following section is all about computing l-isogenies, where l is3882# a prime. The genus 0 cases `l` = 2, 3, 5, 7 and 13 are3883# implemented over any field of characteristic not 2, 3 or `l`; over3884# `\QQ` the "sporadic" cases `l` = 11, 17, 19, 37, 43, 67 or 163 with3885# only finitely many `j`-invariants each. are also implemented.3886##########################################################################38873888@cached_function3889def Fricke_polynomial(l):3890r"""3891Fricke polynomial for ``l`` =2,3,5,7,13.38923893For these primes (and these only) the modular curve `X_0(l)` has3894genus zero, and its field is generated by a single modular3895function called the Fricke module (or Hauptmodul), `t`. There is3896a classical choice of such a generator `t` in each case, and the3897`j`-function is a rational function of `t` of degree `l+1` of the3898form `P(t)/t` where `P` is a polynomial of degree `l+1`. Up to3899scaling, `t` is determined by the condition that the ramification3900points above `j=\infty` are `t=0` (with ramification degree `1`)3901and `t=\infty` (with degree `l`). The ramification above `j=0`3902and `j=1728` may be seen in the factorizations of `j(t)` and3903`k(t)` where `k=j-1728`.39043905OUTPUT:39063907The polynomial `P(t)` as an element of `\ZZ[t]`.39083909TESTS::39103911sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import Fricke_polynomial3912sage: Fricke_polynomial(2)3913t^3 + 48*t^2 + 768*t + 40963914sage: Fricke_polynomial(3)3915t^4 + 36*t^3 + 270*t^2 + 756*t + 7293916sage: Fricke_polynomial(5)3917t^6 + 30*t^5 + 315*t^4 + 1300*t^3 + 1575*t^2 + 750*t + 1253918sage: Fricke_polynomial(7)3919t^8 + 28*t^7 + 322*t^6 + 1904*t^5 + 5915*t^4 + 8624*t^3 + 4018*t^2 + 748*t + 493920sage: Fricke_polynomial(13)3921t^14 + 26*t^13 + 325*t^12 + 2548*t^11 + 13832*t^10 + 54340*t^9 + 157118*t^8 + 333580*t^7 + 509366*t^6 + 534820*t^5 + 354536*t^4 + 124852*t^3 + 15145*t^2 + 746*t + 133922"""3923Zt = PolynomialRing(ZZ,'t')3924t = Zt.gen()3925if l==2: return (t+16)**33926elif l==3: return (t+3)**3*(t+27)3927elif l==5: return (t**2+10*t+5)**33928elif l==7: return (t**2+5*t+1)**3 * (t**2+13*t+49)3929elif l==13: return (t**2+5*t+13)*(t**4+7*t**3+20*t**2+19*t+1)**33930else:3931raise ValueError, "The only genus zero primes are 2, 3, 5, 7 or 13."39323933@cached_function3934def Fricke_module(l):3935r"""3936Fricke module for ``l`` =2,3,5,7,13.39373938For these primes (and these only) the modular curve `X_0(l)` has3939genus zero, and its field is generated by a single modular3940function called the Fricke module (or Hauptmodul), `t`. There is3941a classical choice of such a generator `t` in each case, and the3942`j`-function is a rational function of `t` of degree `l+1` of the3943form `P(t)/t` where `P` is a polynomial of degree `l+1`. Up to3944scaling, `t` is determined by the condition that the ramification3945points above `j=\infty` are `t=0` (with ramification degree `1`)3946and `t=\infty` (with degree `l`). The ramification above `j=0`3947and `j=1728` may be seen in the factorizations of `j(t)` and3948`k(t)` where `k=j-1728`.39493950OUTPUT:39513952The rational function `P(t)/t`.39533954TESTS::39553956sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import Fricke_module3957sage: Fricke_module(2)3958(t^3 + 48*t^2 + 768*t + 4096)/t3959sage: Fricke_module(3)3960(t^4 + 36*t^3 + 270*t^2 + 756*t + 729)/t3961sage: Fricke_module(5)3962(t^6 + 30*t^5 + 315*t^4 + 1300*t^3 + 1575*t^2 + 750*t + 125)/t3963sage: Fricke_module(7)3964(t^8 + 28*t^7 + 322*t^6 + 1904*t^5 + 5915*t^4 + 8624*t^3 + 4018*t^2 + 748*t + 49)/t3965sage: Fricke_module(13)3966(t^14 + 26*t^13 + 325*t^12 + 2548*t^11 + 13832*t^10 + 54340*t^9 + 157118*t^8 + 333580*t^7 + 509366*t^6 + 534820*t^5 + 354536*t^4 + 124852*t^3 + 15145*t^2 + 746*t + 13)/t3967"""3968try:3969t = PolynomialRing(QQ,'t').gen()3970return Fricke_polynomial(l) / t3971except ValueError:3972raise ValueError, "The only genus zero primes are 2, 3, 5, 7 or 13."39733974@cached_function3975def Psi(l, use_stored=True):3976r"""3977Generic kernel polynomial for genus one primes.39783979For each of the primes `l` for which `X_0(l)` has genus zero3980(namely `l=2,3,5,7,13`), we may define an elliptic curve `E_t`3981over `\QQ(t)`, with coefficients in `\ZZ[t]`, which has good3982reduction except at `t=0` and `t=\infty` (which lie above3983`j=\infty`) and at certain other values of `t` above `j=0` when3984`l=3` (one value) or `l\equiv1\pmod{3}` (two values) and above3985`j=1728` when `l=2` (one value) or `l\equiv1 \pmod{4}` (two3986values). (These exceptional values correspond to endomorphisms of3987`E_t` of degree `l`.) The `l`-division polynomial of `E_t` has a3988unique factor of degree `(l-1)/2` (or 1 when `l=2`), with3989coefficients in `\ZZ[t]`, which we call the Generic Kernel3990Polynomial for `l`. These are used, by specialising `t`, in the3991function :meth:`isogenies_prime_degree_genus_0`, which also has to3992take into account the twisting factor between `E_t` for a specific3993value of `t` and the short Weierstrass form of an elliptic curve3994with `j`-invariant `j(t)`. This enables the computation of the3995kernel polynomials of isogenies without having to compute and3996factor division polynomials.39973998All of this data is quickly computed from the Fricke modules, except3999that for `l=13` the factorization of the Generic Division Polynomial4000takes a long time, so the value have been precomputed and cached; by4001default the cached values are used, but the code here will recompute4002them when ``use_stored`` is ``False``, as in the doctests.40034004INPUT:40054006- ``l`` -- either 2, 3, 5, 7, or 13.40074008- ``use_stored`` (boolean, default True) -- If True, use4009precomputed values, otherwise compute them on the fly.40104011.. note::40124013This computation takes a negligible time for `l=2,3,5,7'4014but more than 100s for `l=13`. The reason4015for allowing dynamic computation here instead of just using4016precomputed values is for testing.40174018TESTS::40194020sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import Fricke_module, Psi4021sage: assert Psi(2, use_stored=True) == Psi(2, use_stored=False)4022sage: assert Psi(3, use_stored=True) == Psi(3, use_stored=False)4023sage: assert Psi(5, use_stored=True) == Psi(5, use_stored=False)4024sage: assert Psi(7, use_stored=True) == Psi(7, use_stored=False)4025sage: assert Psi(13, use_stored=True) == Psi(13, use_stored=False) # not tested (very long time)4026"""4027if not l in [2,3,5,7,13]:4028raise ValueError, "Genus zero primes are 2, 3, 5, 7 or 13."40294030R = PolynomialRing(ZZ,2,'Xt')4031X,t = R.gens()40324033if use_stored:4034if l==2:4035return X + t + 644036if l==3:4037return X + t + 274038if l==5:4039return X**2 + 2*X*(t**2 + 22*t + 125)+ (t**2 + 22*t + 89) * (t**2 + 22*t + 125)4040if l==7:4041return (X**3 + 3*(t**2 + 13*t + 49)*X**24042+ 3*(t**2 + 13*t + 33)*(t**2 + 13*t + 49)*X4043+ (t**2 + 13*t + 49)*(t**4 + 26*t**3 + 219*t**2 + 778*t + 881))4044if l==13:4045return (t**24 + 66*t**23 + 2091*t**22 + 6*X*t**20 + 42582*t**21 + 330*X*t**19 + 627603*t**20 + 8700*X*t**18 + 7134744*t**19 + 15*X**2*t**16 + 146886*X*t**17 + 65042724*t**18 + 660*X**2*t**15 + 1784532*X*t**16 + 487778988*t**17 + 13890*X**2*t**14 + 16594230*X*t**15 + 3061861065*t**16 + 20*X**3*t**12 + 186024*X**2*t**13 + 122552328*X*t**14 + 16280123754*t**15 + 660*X**3*t**11 + 1774887*X**2*t**12 + 735836862*X*t**13 + 73911331425*t**14 + 10380*X**3*t**10 + 12787272*X**2*t**11 + 3646188342*X*t**12 + 287938949178*t**13 + 15*X**4*t**8 + 102576*X**3*t**9 + 71909658*X**2*t**10 + 15047141292*X*t**11 + 964903805434*t**12 + 330*X**4*t**7 + 707604*X**3*t**8 + 321704316*X**2*t**9 + 51955096824*X*t**10 + 2781843718722*t**11 + 3435*X**4*t**6 + 3582876*X**3*t**7 + 1155971196*X**2*t**8 + 150205315932*X*t**9 + 6885805359741*t**10 + 6*X**5*t**4 + 21714*X**4*t**5 + 13632168*X**3*t**6 + 3343499244*X**2*t**7 + 362526695094*X*t**8 + 14569390179114*t**9 + 66*X**5*t**3 + 90660*X**4*t**4 + 39215388*X**3*t**5 + 7747596090*X**2*t**6 + 725403501318*X*t**7 + 26165223178293*t**8 + 336*X**5*t**2 + 255090*X**4*t**3 + 84525732*X**3*t**4 + 14206132008*X**2*t**5 + 1189398495432*X*t**6 + 39474479008356*t**7 + X**6 + 858*X**5*t + 472143*X**4*t**2 + 132886992*X**3*t**3 + 20157510639*X**2*t**4 + 1569568001646*X*t**5 + 49303015587132*t**6 + 1014*X**5 + 525954*X**4*t + 144222780*X**3*t**2 + 21320908440*X**2*t**3 + 1622460290100*X*t**4 + 49941619724976*t**5 + 272259*X**4 + 96482100*X**3*t + 15765293778*X**2*t**2 + 1260038295438*X*t**3 + 39836631701295*t**4 + 29641924*X**3 + 7210949460*X**2*t + 686651250012*X*t**2 + 23947528862166*t**3 + 1506392823*X**2 + 231462513906*X*t + 10114876838391*t**2 + 35655266790*X + 2644809206442*t + 317295487717)4046# The coefficients for l=13 are:4047# X**6: 14048# X**5: (6) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13)4049# X**4: (3) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13) * (5*t**4 + 55*t**3 + 260*t**2 + 583*t + 537)4050# X**3: (4) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13)**2 * (5*t**6 + 80*t**5 + 560*t**4 + 2214*t**3 + 5128*t**2 + 6568*t + 3373)4051# X**2: (3) * (t**2 + 5*t + 13)**2 * (t**2 + 6*t + 13)**2 * (5*t**8 + 110*t**7 + 1045*t**6 + 5798*t**5 + 20508*t**4 + 47134*t**3 + 67685*t**2 + 54406*t + 17581)4052# X**1: (6) * (t**2 + 5*t + 13)**2 * (t**2 + 6*t + 13)**3 * (t**10 + 27*t**9 + 316*t**8 + 2225*t**7 + 10463*t**6 + 34232*t**5 + 78299*t**4 + 122305*t**3 + 122892*t**2 + 69427*t + 16005)4053# X**0: (t**2 + 5*t + 13)**2 * (t**2 + 6*t + 13)**3 * (t**14 + 38*t**13 + 649*t**12 + 6844*t**11 + 50216*t**10 + 271612*t**9 + 1115174*t**8 + 3520132*t**7 + 8549270*t**6 + 15812476*t**5 + 21764840*t**4 + 21384124*t**3 + 13952929*t**2 + 5282630*t + 854569)4054#40554056# Here the generic kernel polynomials are actually calculated:4057j = Fricke_module(l)4058k = j-17284059from sage.misc.all import prod4060f = prod( [p for p,e in j.factor() if e==3]4061+[p for p,e in k.factor() if e==2])4062A4 = -3*t**2*j*k // f**24063A6 = -2*t**3*j*k**2 // f**34064E = EllipticCurve([0,0,0,A4,A6])4065assert E.j_invariant() == j4066return E.division_polynomial(l,X).factor()[0][0]406740684069def isogenies_prime_degree_genus_0(E, l=None):4070"""4071Returns list of ``l`` -isogenies with domain ``E``.40724073INPUT:40744075- ``E`` -- an elliptic curve.40764077- ``l`` -- either None or 2, 3, 5, 7, or 13.40784079OUTPUT:40804081(list) When ``l`` is None a list of all isogenies of degree 2, 3,40825, 7 and 13, otherwise a list of isogenies of the given degree.40834084.. note::40854086This function would normally be invoked indirectly via4087``E.isogenies_prime_degree(l)``, which automatically calls the4088appropriate function.40894090EXAMPLES::40914092sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_prime_degree_genus_04093sage: E = EllipticCurve([0,12])4094sage: isogenies_prime_degree_genus_0(E, 5)4095[]40964097sage: E = EllipticCurve('1450c1')4098sage: isogenies_prime_degree_genus_0(E)4099[Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + 300*x - 1000 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 5950*x - 182250 over Rational Field]41004101sage: E = EllipticCurve('50a1')4102sage: isogenies_prime_degree_genus_0(E)4103[Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 126*x - 552 over Rational Field,4104Isogeny of degree 5 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 76*x + 298 over Rational Field]4105"""4106if not l in [2, 3, 5, 7, 13, None]:4107raise ValueError, "Isogenies must be of degree 2, 3, 5, 7 or 13."4108F = E.base_ring()4109j = E.j_invariant()4110if F.characteristic() in [2, 3, l]:4111raise NotImplementedError, "2, 3, 5, 7 and 13-isogenies are not yet implemented in characteristic 2 and 3, and when the characteristic is the same as the degree of the isogeny."4112if l==2:4113return isogenies_2(E)4114if l==3:4115return isogenies_3(E)4116if j==F(0):4117if l==5:4118return isogenies_5_0(E)4119if l==7:4120return isogenies_7_0(E)4121if l==13:4122return isogenies_13_0(E)4123if j==F(1728):4124if l==5:4125return isogenies_5_1728(E)4126if l==7:4127return isogenies_7_1728(E)4128if l==13:4129return isogenies_13_1728(E)41304131if l != None:4132R = PolynomialRing(F,'t')4133t = R.gen()4134f = R(Fricke_polynomial(l))4135t_list = (f-j*t).roots(multiplicities=False)4136t_list.sort()4137# The generic kernel polynomial applies to a standard curve4138# E_t with the correct j-invariant; we must compute the4139# appropriate twising factor to scale X by:4140c4, c6 = E.c_invariants()4141T = c4/(3*c6)4142jt = Fricke_module(l)4143kt = jt-17284144from sage.misc.all import prod4145psi = Psi(l)4146X = t4147f = R(prod( [p for p,e in jt.factor() if e==3]4148+[p for p,e in kt.factor() if e==2]))4149kernels = [R(psi(X*T*(j-1728)*t0/f(t0),t0)) for t0 in t_list]4150kernels = [ker.monic() for ker in kernels]4151E1 = EllipticCurve([-27*c4,-54*c6])4152w = E.isomorphism_to(E1)4153model = "minimal" if F is QQ else None4154isogs = [E1.isogeny(kernel=ker, model=model) for ker in kernels]4155[isog.set_pre_isomorphism(w) for isog in isogs]4156return isogs41574158if l == None:4159return sum([isogenies_prime_degree_genus_0(E, l) for l in [2,3,5,7,13]],[])416041614162# The following is data to be used in isogenies_sporadic_Q. Over Q4163# there are only finitely many j-invariants of curves with l-isogenies4164# where l is not equal to 2, 3, 5, 7 or 13. In these cases l is equal4165# to 11, 17, 19, 37, 43, 67 or 163. We refer to these l as "sporadic".4166#4167# isog_table is indexed by the possible sporadic (l,j) pairs and lists4168# ((a4,a6),f) where (a4,a6) are the invariants of a short Weierstrass4169# model of one curve with that j-invariant,and f is the factor of4170# degree (l-1)/2 of the l-division polynomial of that curve. Then4171# whenever we have a curve of that j-invariant, we can compute the4172# corresponding l-isogeny by just scaling f by the right twisting4173# factor and using the result as a kernel-polynomial.41744175# Sample code to precompute this data. Note that working over ZZ4176# instead of QQ is a lot faster (in Sage 4.2):4177#4178#sage: j = -297756989/2; l = 174179#sage: E = EllipticCurve(ZZ,EllipticCurve(j=j).short_weierstrass_model().ainvs())4180#sage: E.division_polynomial(l,polygen(ZZ)).factor()[1][0].coefficients()4181#4182#sage: j = -884736000; l = 434183#sage: E = EllipticCurve(ZZ,EllipticCurve(j=j).short_weierstrass_model().ainvs())4184#sage: E.division_polynomial(l,polygen(ZZ)).factor()[1][0].coefficients()418541864187isog_table = dict()41884189isog_table[(11,QQ('-32768'))] = ([-9504, 365904], [1294672896, -92835072, 1463616, 7920, -264, 1])41904191isog_table[(11,QQ('-121'))] = ([-3267, -280962], [1480352841, -56169531, -2829222, 10890, 429, 1])41924193isog_table[(11,QQ('-24729001'))] = ([-38907, -2953962], [-20349931239, -424530315, -134838, 53658, 429, 1])41944195isog_table[(17,QQ('-297756989/2'))] = ([-3940515, 3010787550], [-6458213126940667330314375, 34699336325466068070000, -72461450055340471500, 68342601718080000, -15140380554450, -25802960400, 23981220, -8160, 1])41964197isog_table[(17,QQ('-882216989/131072'))] = ([-856035, -341748450], [103687510635057329105625, 961598491955315190000, 1054634146768300500, -6553122389064000, -14554350284850, -2046589200, 13185540, 8160, 1])41984199isog_table[(19,QQ('-884736'))] = ([-608, 5776], [-34162868224, -8540717056, 6405537792, -1123778560, 84283392, -2033152, -92416, 6992, -152, 1])42004201isog_table[(37,QQ('-9317'))] = ([-10395, 444150],[-38324677699334121599624973029296875, -17868327793500376961572310472656250, 2569568362004197901139023084765625, -95128267987528547588017818750000, -822168183291347061312510937500, 134395594560592096297190625000, -2881389756919344324888937500, -2503855007083401977250000, 922779077075655997443750, -11503912310262102937500, -18237870962450291250, 1457822151548910000, -10087015556047500, -13677678063000, 490243338900, -2461460400, 5198445, -4410, 1])42024203isog_table[(37,QQ('-162677523113838677'))] = ([-269675595, -1704553285050], [-31653754873248632711650187487655160190139073510876609346911928661154296875/37, -1469048260972089939455942042937882262144594798448952781325533511718750, -1171741935131505774747142644126089902595908234671576131857702734375, -574934780393177024547076427530739751753985644656221274606250000, -193516922725803688001809624711400287605136013195315374687500, -47085563820928456130325308223963045033502182349693125000, -8472233937388712980597845725196873697064639957437500, -1124815211213953261752081095348112305023653750000, -105684015609077608033913080859605951322531250, -5911406027236569746089675554748135312500, 22343907270397352965399097794968750, 43602171843758666292581116410000, 5054350766002463251474186500, 350135768194635636171000, 16633063574896677300, 549939627039600, 12182993865, 163170, 1])42044205isog_table[(43,QQ('-884736000'))] = ([-13760, 621264],[-1961864562041980324821547425314935668736, 784270445793223959453256359333693751296, -120528107728500223255333768387027271680, 10335626145581464192664472924270362624, -568426570575654606865505142156820480, 21261993723422650574629752537088000, -544630471727787626557612832587776, 8870521306520473088172555763712, -54993059067301585878494740480, -1434261324709904840432549888, 50978938193065926383894528, -845761855773797582372864, 8627493611216601088000, -48299605284169187328, -32782260293713920, 3415534989828096, -34580115625984, 199359712512, -730488128, 1658080, -2064, 1])42064207isog_table[(67,QQ('-147197952000'))] = ([-117920, 15585808], [426552448394636714720553816389274308035895411389805883034985546818882031845376, -55876556222880738651382959148329502876096075327084935039031884373558741172224, 3393295715290183821010552313572221545212247684503012173117764703828786020352, -125729166452196578653551230178028570067747190427221869867485520072257044480, 3121342502030777257351089270834971957072933779704445667351054593298530304, -52544031605544530265465344472543470442324636919759253720520768014516224, 532110915869155495738137756847596184665209453108323879594125221167104, -399031158106622651277981701966309467713625045637309782055519780864, -101914346170769215732007802723651742508893380955930030421292613632, 2296526155500449624398016447877283594461904009374321659789443072, -31950871094301541469458501953701002806003991982768349794795520, 329792235011603804948028315065667439678526339671142107709440, -2655636715955021784085217734679612378726442691190553837568, 16825164648840434987220620681420687654501026066872664064, -81705027839007003131400500185224450729843244954288128, 273656504606483403474090105104132405333665144373248, -320807702482945680116212224172370503903312084992, -3166683390779345463318656135338172047199043584, 27871349428383710305216046431806697565585408, -132774697798318602604125735604528772808704, 436096215568182871014215818309741314048, -964687143341252402362763535357837312, 942144169187362941776488535425024, 2794850106281773765892648206336, -17236916236678037389276086272, 50979778712911923486851072, -105035658611718440992768, 161833913559276412928, -188675698610077696, 163929317513984, -102098677888, 42387952, -10184, 1])42084209isog_table[(163,QQ('-262537412640768000'))] = ([-34790720, 78984748304], [11937033609701771608400008302859181021419097217821452062564326844817505228663098831008549807845273606080544999996020379100442085010011180910986311230744539492209201267851475053850145465949031314131282944262561686476431332761205504055553653209756637748416809823347727611717499380045401030656, -195130071447306655273524569473852352290010571088570084255929596426827972913675959924834214553822436039185267072655230231264389277855757579340840680919752147359277865429131554516271296434318501723193704667609983954393732283396979741770275596479169906167026623493287956522391758781645062144, 1427502734760154784443139998885173873805698542265553947708985997014264802221336771918193375050938963016560184673026895611200993837000754187703921657388546609660768979949394789838000919808563779734300559653270446650866261801622261730386746625133970663551831816512698564779980290036596736, -5599207432852992026535855102327743354503965526118767584653806869099469434869389394471452436350209911401734358692516268244363981178003440912521398279843764610451103952982463228121628686179444592844803463454880601969041617668281227800515971090274318968755339891485627349912827843313664, 7275289443663173375117187980461451723630939807433676133488193878209459535146604043302393215325736700753114238886326617501903060793779318898498537340122928915051396994852249905774785383484964157718761647679761326405167986820403416875550489904598260809039588027484880575324789669888, 53852767252251176711316610474871670511285949778037067647446607721301053062542360857644949076379793988972999080753585666268471181395581176311086709516236139859119228114940726664020344711163961450649040900179940667704933096423082541578086102752168151408016128448757608609516355584, -441024601763314150109608522830440149169771622404264936395215000306188259683627792348927267455527449622616337194882061278315837263834842622422058957336768392927319786456429412773335490683756389242358011775192147290260088212928183893496023497385031567935590156495818971603271680, 1923729652470036657640234466480856403679261373466564217770510758620007251234737653848912112257887106718711179570266106782165127910894792855741763009046440188368346201617134183692667813264354753020558715833289878752200363206184231817927249353441775148372373391040829093576704, -6174291905252822700639099970860178217904525535465573253756653994759145320917644436646210500761314537511653465341404223911052812759676375813287317189557074876672717009913962857515263325087926781282727274494599622098970326546685474959128901831166082055481492871737587531776, 15963605433939241348215386312076502855685142708851007052060264896693306401589916424547272907372369971200908960298559196028000249867821387055883338894215055448441454208145184664251082508258481820123154014612667230187589409024581605410594578299015578613903351914203971584, -34687777075075826936035422448136670540047824478867437603900549472003349053758981331083701038247602826434094223697740838012005963350495346494192086319952577715870471857062004211165110944749546489357024333327851492892063261902845789001287880518909468079710544890691584, 64935614565701660925102862834870557968917923758048315817978089985628103203452108238400473842703675144415856702414743965076964752315718880263247146806212144113325233966196430978981658754610129252819800656290540439882400228191972297000590950499022332532802841477120, -106450113192928986500166510746460290010686605565802553549898115364953461571938149159855780359758326598170956839310849727549767334328481520722457671184262149140997347199434067316119593873464084542168958564857207310255104210252802288265107074620056433232296542208, 154588468341182819097156049664780175805765082709542906853062319968823210709884467518965950031344875777123989196305422245441384128571495551803479155842444104959551491130118809781140758556182128829570214830557657320822341658937375265326185627024588353675722752, -200559814675071715715147513664537685696543665835231560123119674695431140901874837885144270078673500682009909076723885595600964688749788075855566556738418513204701882392037282897429720984011892144438563658741417367819609826485149957684720592798005782904832, 233913230287794067984901680255098952718268709897211662836962202594844321932231309396660409956864579218254273924904394011519168528453166798219739516110916032144001430976170021740673624911101610999174313953331179592523559209806130064362331035786304028672, -246353703535830799051965068435640665615241585380168769205605419959931340172791084855084136413845436489354260626697043416419953596294256639939636661074827002386688825389366314922889935515780006872313799807871034941783710991661439846743406825846079488, 234982742638283161239147075499923192184558615040750093346909554959954534765162320677404212311317141015056956519607730625264033505832417237335526289717986324622989530401755659861160278474288472483456460761582961131223878005034852988312569782468608, -203278213565303083958289848507904983111914464281937008996800600743049033135780053019308180654889993715847194782810638377233384956677984229396984592095978852141937402724743415866647478390224972086303117541277057454016741537801255285401042550784, 159421011266364165773350759598961923468646295930442671951663830439105229019095602850806206849694626149081055860876320252885592409781300283802068036284087012054926328984117466238728138017296876920468741929209733382315316048593848804000661504, -113020918346823224387675962727710849438448560054728764538889949910907956081636084818673918939857811981198128625134001275445247927733612860826192033364144709296859805908448480126055187856540001252440723696556907592809391568682658983575552, 71945777186858148520189111385851657591994785437936790663752048596268908397761761228530149720647914698227096033298596468433406211022425872184679773706985835273196359946527329295352840585601589987654250252509940697181497393634479177728, -40553506248279853197899380016510447069205875473858373944916667311741237594752103405195544436215283638784303466518029972315361472909380024525230365389883507930702477745185560842399992120410631726800835247081534888734998176190169088, 19639696188973552762819015734509385187497753279018359326954702329472344393424778261565226791972589248949076879073752940457430177635689762236418319921157145929450429275277598105096782299310906043071624518383647513981402864418816, -7557145635717782395604678688732309739123765964398036300935902895029921544449817739871127195837816246027098669576710973724603305169613035210748794125702623638061784934800621663541549758981147547220745886014319375033833619456, 1657074863449131529294393850366914004166071540911557375298352670995793916631379837217699843183161870412953109096989706473414891817476345269315000071815674837414249807862563049048940888990780356828116926372826050377809920, 594537607406738614488647166334439665406200193881374352383582637957395810395355986219181323336507140663007282377906531198753011484726171889166159296232442266402815351908351664480142997422997116094990105400004717838336, -1063381335685557601789471169771716160614658527547206527560235661204306306147122486589145738731952820149525220010993135210540125800587297277176980780550749659568216404307556497848427558893515024809067113577642459136, 866504016710397283549081797838552191017551170056714418172658679484342314216337494688411296133019156758665490378562995489461120013841310945167448587950589192882728019730184100760635093600626150305226434294054912, -544456451437710104677464982275658569122639544706468906698603670935572135268235880234260773620839923609980624261711876187191086008709319550421652238153751371247896403810296918434808016324776218527300472274944, 291391938923983436973777049837536733140215048414562274102609644110225500962890424001140034799254161420207705596799832439286323749581485058440291289292376834767289200150488260103720502388531610043446984704, -137669336373928330264003425607593379960726875901008061728935571651808147336578784033262243606118618305155146994101199276509296485578362621442124562716722538959248783675765430495753630524650420015464448, 58305039769563586190846386880024028458953483779423358562963969531061253550565868881984384427294827940260948562007946246585988242539388915757370599713569828414708265704775708180369817440224330907648, -22263674613297409152475382098514675408629524088165884591926938276387287183647211206514841583522457779552325379611699721363009213935995055122374833256328128159685068070573439567341889102047870976, 7659525572873653643686667682470156611730287715779213959462404612107764289631014622079262434509991525269350939684751076168111178931547830737285816290499346814316593688339716060537705476390912, -2356369509601030092354164626593105564281508081035914666378162646456624099153984023946457193322861690246151591627985138670141283491665875837349056368982626874320059053912723460560567402496, 636306064623878566247238117586667093960745761448319133509756604897082306674457051834692637631208787669480579961449146859307914219525683813169045631019945325543755784485150162136596480, -144354698667964959131302121388611435649331689922451077357726958728526160763985021377919777057073652734054824995380136026354322489788621439866623621032883911971992887755746217820160, 24121955586756417060840806312875152536841537469465641066665477185642959713399102667004561835703554642486033432650174169972215286732914841507194929969333501923213681889898397696, -1062982554332400020436047718307967606435230424325029173087078414691100152298424407470637592479633445244263771003475924500470457802708388802132021409732119617604143984672768, -1289959173517591900879403877417447464323361120695839905879179383576917611515563011791770601288187258710836960962551744314331281738572022125094897455138775637822772609024, 713094034093241133139975542207369737377005379966568397923649557581354608722973890056780743426440880397949894405054289149004564424971813787111450018625163532324306944, -254627379967901645020979419858451704766383325190491161773871149760504423262065255127251316663797380198173202687716259997416292667070368594859769612820620832145408, 73141763506085097918144459824978126154049420184880822723900482544151820781804249152002290712777719695036970656528265835764223704583688284269989955443519127552, -17838537225679516940483486695156689114251551141417084228356667456567223074797422210814066353881812352204911178711536306766419580650031647883778868599848960, 3732949472404613028683276858400771022649020140479952475050562287824228475488013407594597423014344735572239887680502683815016952233794807477380489150464, -658090831088275932021697572468169724648153295038942023393017242911882324988827102897240587742441233130939688197251981440661637431663180512231424000, 91044773494274344573228085560493548892450695165631132364575161840790371925870648417274049055693061297980952723608086693629684733411639066361856, -7206875978668204173369106020317806614830036116031258178074085756310402308591937698714169573782276745187407867676712962154996289706219536384, -819751497058465540849522914081577930969395072622202448379227754265195552229316711754131018363430793506957620878700584807196119659446272, 524492219141524596329431820120551446539246304466694008535436881375050446937946483408452355745347329681867559263476448413099237572608, -144831995016562693238485974645571530330971707229081912571899541756458417275452663670185243929333997861822834344607487043313860608, 29914869637979316056234691641068533246353548074478964560456384907200155525359490145390698951538414992573246875654471802683392, -5051703199007242317980870828294675665554938059871421101373455640671888804716466166733214891733545898164243959713215021056, 704266224450794229753813389400889235502895246267920454892105495898823500254340026026030392861415807391779452916596736, -77090914220067457257437168730743598007998214624866646138957596697882331770536104168830311427039146990575867133952, 5185529715527985800186976473360862373518426289807725150611458977619779754244941008386724289180811582624497664, 253997773097193639890870939442154039645526260966991421810387625142025920490445698037959549218977356972032, -167663051891371188948811201282888303918118872228509878481620659513761819092806840088343319460416847872, 37111139278046773379558801627698801653586358926939257719148812112681156722739468064234356797865984, -6094794232647488071603134809336879629321484740792083961518604911291776122012806633249006682112, 837291566508665017874331015912241564512130987193765470835615200761060354034220082158108672, -100296887606046826616864046733353580911852480578758327196473644505408067503452896362496, 10671531126308719182671886696772003009468978048122050876385337250105289881860177920, -1017660211057522997139542974021461951590281854561469513981031668621068390629376, 87341651749945752980300268787472991750253192293865191008561736741703122944, -6755055811837604655292473395831392832731215030180150346004905802596352, 470435697396489049890276884918878813522261509046808135502735081472, -29431936259973770189795237369002643735145492537132570738950144, 1647955729708147681608319291051493831298410618099083509760, -82151504501901440318090519089275042334656836617109504, 3621394962905672351516373383975280471835697741824, -139946424433346723333934826799658073276284928, 4689146702972667351768128807176661303296, -134326059738838559898371882636836864, 3230090486862617839209120497664, -63628315178835325152092160, 992573003659549935360, -11668560578458368, 95539651616, -472048, 1])4210421142124213def isogenies_sporadic_Q(E, l=None):4214"""4215Returns list of ``l`` -isogenies with domain ``E`` (defined over `\QQ`).42164217Returns a list of sporadic l-isogenies from E (l = 11, 17, 19, 37,421843, 67 or 163). Only for elliptic curves over `\QQ`.42194220INPUT:42214222- ``E`` -- an elliptic curve defined over `\QQ`.42234224- ``l`` -- either None or a prime number.42254226OUTPUT:42274228(list) If ``l`` is None, a list of all isogenies with domain ``E``4229and of degree 11, 17, 19, 37, 43, 67 or 163; otherwise a list of4230isogenies of the given degree.42314232.. note::42334234This function would normally be invoked indirectly via4235``E.isogenies_prime_degree(l)``, which automatically calls the appropriate4236function.42374238EXAMPLES::42394240sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_sporadic_Q4241sage: E = EllipticCurve('121a1')4242sage: isogenies_sporadic_Q(E, 11)4243[Isogeny of degree 11 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 30*x - 76 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 305*x + 7888 over Rational Field]4244sage: isogenies_sporadic_Q(E, 13)4245[]4246sage: isogenies_sporadic_Q(E, 17)4247[]4248sage: isogenies_sporadic_Q(E)4249[Isogeny of degree 11 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 30*x - 76 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 305*x + 7888 over Rational Field]42504251sage: E = EllipticCurve([1, 1, 0, -660, -7600])4252sage: isogenies_sporadic_Q(E, 17)4253[Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 660*x - 7600 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 878710*x + 316677750 over Rational Field]4254sage: isogenies_sporadic_Q(E)4255[Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 660*x - 7600 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 878710*x + 316677750 over Rational Field]4256sage: isogenies_sporadic_Q(E, 11)4257[]42584259sage: E = EllipticCurve([0, 0, 1, -1862, -30956])4260sage: isogenies_sporadic_Q(E, 11)4261[]4262sage: isogenies_sporadic_Q(E, 19)4263[Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field]4264sage: isogenies_sporadic_Q(E)4265[Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field]42664267sage: E = EllipticCurve([0, -1, 0, -6288, 211072])4268sage: E.conductor()4269196004270sage: isogenies_sporadic_Q(E,37)4271[Isogeny of degree 37 from Elliptic Curve defined by y^2 = x^3 - x^2 - 6288*x + 211072 over Rational Field to Elliptic Curve defined by y^2 = x^3 - x^2 - 163137088*x - 801950801728 over Rational Field]42724273sage: E = EllipticCurve([1, 1, 0, -25178045, 48616918750])4274sage: E.conductor()42751482254276sage: isogenies_sporadic_Q(E,37)4277[Isogeny of degree 37 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 25178045*x + 48616918750 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 970*x - 13075 over Rational Field]42784279sage: E = EllipticCurve([-3440, 77658])4280sage: E.conductor()42811183364282sage: isogenies_sporadic_Q(E,43)4283[Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 - 3440*x + 77658 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 6360560*x - 6174354606 over Rational Field]42844285sage: E = EllipticCurve([-29480, -1948226])4286sage: E.conductor()42872872964288sage: isogenies_sporadic_Q(E,67)4289[Isogeny of degree 67 from Elliptic Curve defined by y^2 = x^3 - 29480*x - 1948226 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 132335720*x + 585954296438 over Rational Field]42904291sage: E = EllipticCurve([-34790720, -78984748304])4292sage: E.conductor()42934251044294sage: isogenies_sporadic_Q(E,163)4295[Isogeny of degree 163 from Elliptic Curve defined by y^2 = x^3 - 34790720*x - 78984748304 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 924354639680*x + 342062961763303088 over Rational Field]4296"""4297if E.base_ring() != QQ:4298raise ValueError, "The elliptic curve must be defined over QQ."4299j = E.j_invariant()4300j = QQ(j)4301if l != None:4302if not l.is_prime():4303raise ValueError("%s is not prime."%l)4304if not isog_table.has_key((l,j)):4305return []4306Ew = E.short_weierstrass_model()4307E_to_Ew = E.isomorphism_to(Ew)4308c4, c6 = Ew.c_invariants()4309(a4,a6), f = isog_table[(l,j)]4310d = (c6*a4)/(18*c4*a6) # twisting factor4311R = PolynomialRing(E.base_field(),'X')4312n = len(f)4313ker = R([d**(n-i-1) * f[i] for i in range(n)])4314isog = Ew.isogeny(kernel=ker, degree=l, model="minimal", check=False)4315isog.set_pre_isomorphism(E_to_Ew)4316return [isog]4317if l is None:4318if isog_table.has_key((11,j)):4319return isogenies_sporadic_Q(E, Integer(11))4320if isog_table.has_key((17,j)):4321return isogenies_sporadic_Q(E, Integer(17))4322if isog_table.has_key((19,j)):4323return isogenies_sporadic_Q(E, Integer(19))4324if isog_table.has_key((37,j)):4325return isogenies_sporadic_Q(E, Integer(37))4326if isog_table.has_key((43,j)):4327return isogenies_sporadic_Q(E, Integer(43))4328if isog_table.has_key((67,j)):4329return isogenies_sporadic_Q(E, Integer(67))4330if isog_table.has_key((163,j)):4331return isogenies_sporadic_Q(E, Integer(163))4332else:4333return []43344335def isogenies_2(E):4336"""4337Returns a list of all 2-isogenies with domain ``E``.43384339INPUT:43404341- ``E`` -- an elliptic curve.43424343OUTPUT:43444345(list) 2-isogenies with domain ``E``. In general these are4346normalised, but over `\QQ` the codomain is a minimal model.43474348EXAMPLES::43494350sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_24351sage: E = EllipticCurve('14a1'); E4352Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x - 6 over Rational Field4353sage: [phi.codomain().ainvs() for phi in isogenies_2(E)]4354[(1, 0, 1, -36, -70)]43554356sage: E = EllipticCurve([1,2,3,4,5]); E4357Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field4358sage: [phi.codomain().ainvs() for phi in isogenies_2(E)]4359[]4360sage: E = EllipticCurve(QQbar, [9,8]); E4361Elliptic Curve defined by y^2 = x^3 + 9*x + 8 over Algebraic Field4362sage: isogenies_2(E) # not implemented4363"""4364f2 = E.division_polynomial(2)4365x2 = f2.roots(multiplicities=False)4366x2.sort()4367x = f2.parent().gen()4368ff = [x-x2i for x2i in x2]4369model = "minimal" if E.base_field() is QQ else None4370isogs = [E.isogeny(f, model=model) for f in ff]4371return isogs43724373def isogenies_3(E):4374"""4375Returns a list of all 3-isogenies with domain ``E``.43764377INPUT:43784379- ``E`` -- an elliptic curve.43804381OUTPUT:43824383(list) 3-isogenies with domain ``E``. In general these are4384normalised, but over `\QQ` the codomain is a minimal model.43854386EXAMPLES::43874388sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_34389sage: E = EllipticCurve(GF(17), [1,1])4390sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]4391[(0, 0, 0, 9, 7), (0, 0, 0, 0, 1)]43924393sage: E = EllipticCurve(GF(17^2,'a'), [1,1])4394sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]4395[(0, 0, 0, 9, 7), (0, 0, 0, 0, 1), (0, 0, 0, 5*a + 1, a + 13), (0, 0, 0, 12*a + 6, 16*a + 14)]43964397sage: E = EllipticCurve('19a1')4398sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]4399[(0, 1, 1, 1, 0), (0, 1, 1, -769, -8470)]44004401sage: E = EllipticCurve([1,1])4402sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]4403[]4404"""4405f3 = E.division_polynomial(3)4406x3 = f3.roots(multiplicities=False)4407x3.sort()4408x = f3.parent().gen()4409ff = [x-x3i for x3i in x3]4410model = "minimal" if E.base_field() is QQ else None4411isogs = [E.isogeny(f, model=model) for f in ff]4412return isogs44134414# 6 special cases: `l` = 5, 7, 13 and `j` = 0, 1728.44154416def isogenies_5_0(E):4417"""4418Returns a list of all the 5-isogenies with domain ``E`` when the4419j-invariant is 0.44204421OUTPUT:44224423(list) 5-isogenies with codomain E. In general these are4424normalised, but over `\QQ` the codomain is a minimal model.44254426.. note::44274428This implementation requires that the characteristic is not 2,44293 or 5.44304431.. note::44324433This function would normally be invoked indirectly via ``E.isogenies_prime_degree(5)``.44344435EXAMPLES::44364437sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_5_04438sage: E = EllipticCurve([0,12])4439sage: isogenies_5_0(E)4440[]44414442sage: E = EllipticCurve(GF(13^2,'a'),[0,-3])4443sage: isogenies_5_0(E)4444[Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (4*a+6)*x + (2*a+10) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (12*a+5)*x + (2*a+10) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (10*a+2)*x + (2*a+10) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (3*a+12)*x + (11*a+12) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (a+4)*x + (11*a+12) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (9*a+10)*x + (11*a+12) over Finite Field in a of size 13^2]44454446sage: K.<a> = NumberField(x**6-320*x**3-320)4447sage: E = EllipticCurve(K,[0,0,1,0,0])4448sage: isogenies_5_0(E)4449[Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^6 - 320*x^3 - 320 to Elliptic Curve defined by y^2 = x^3 + (a^5-400*a^2)*x + (280*a^3-3120) over Number Field in a with defining polynomial x^6 - 320*x^3 - 320,4450Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^6 - 320*x^3 - 320 to Elliptic Curve defined by y^2 = x^3 + (23/2*a^5-3700*a^2)*x + (-280*a^3+86480) over Number Field in a with defining polynomial x^6 - 320*x^3 - 320]44514452"""4453F = E.base_field()4454if E.j_invariant() != 0:4455raise ValueError, "j-invariant must be 0."4456if F.characteristic() in [2,3,5]:4457raise NotImplementedError, "Not implemented in characteristic 2, 3 or 5."4458if not F(5).is_square():4459return []4460Ew = E.short_weierstrass_model()4461a = Ew.a6()4462x = polygen(F)4463betas = (x**6-160*a*x**3-80*a**2).roots(multiplicities=False)4464betas.sort()4465if len(betas)==0:4466return []4467gammas = [(beta**2 *(beta**3-140*a))/(120*a) for beta in betas]4468model = "minimal" if F is QQ else None4469isogs = [Ew.isogeny(x**2+beta*x+gamma, model=model) for beta,gamma in zip(betas,gammas)]4470iso = E.isomorphism_to(Ew)4471[isog.set_pre_isomorphism(iso) for isog in isogs]4472return isogs44734474def isogenies_5_1728(E):4475"""4476Returns a list of 5-isogenies with domain ``E`` when the j-invariant is44771728.44784479OUTPUT:44804481(list) 5-isogenies with codomain E. In general these are4482normalised; but if `-1` is a square then there are two4483endomorphisms of degree `5`, for which the codomain is the same as4484the domain curve; and over `\QQ`, the codomain is a minimal model.44854486.. note::44874488This implementation requires that the characteristic is not 2,44893 or 5.44904491.. note::44924493This function would normally be invoked indirectly via ``E.isogenies_prime_degree(5)``.44944495EXAMPLES::44964497sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_5_17284498sage: E = EllipticCurve([7,0])4499sage: isogenies_5_1728(E)4500[]45014502sage: E = EllipticCurve(GF(13),[11,0])4503sage: isogenies_5_1728(E)4504[Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13 to Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13,4505Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13 to Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13]45064507An example of endomorphisms of degree 5::45084509sage: K.<i> = QuadraticField(-1)4510sage: E = EllipticCurve(K,[0,0,0,1,0])4511sage: isogenies_5_1728(E)4512[Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,4513Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1]4514sage: _[0].rational_maps()4515(((-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)),4516((2/125*i - 11/125)*x^6*y + (64/125*i + 23/125)*x^4*y + (162/125*i - 141/125)*x^2*y + (-4/25*i - 3/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125)))45174518An example of 5-isogenies over a number field::45194520sage: K.<a> = NumberField(x**4+20*x**2-80)4521sage: K(5).is_square() #necessary but not sufficient!4522True4523sage: E = EllipticCurve(K,[0,0,0,1,0])4524sage: isogenies_5_1728(E)4525[Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^4 + 20*x^2 - 80 to Elliptic Curve defined by y^2 = x^3 + (-20*a^2-39)*x + (35*a^3+112*a) over Number Field in a with defining polynomial x^4 + 20*x^2 - 80,4526Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^4 + 20*x^2 - 80 to Elliptic Curve defined by y^2 = x^3 + (-20*a^2-39)*x + (-35*a^3-112*a) over Number Field in a with defining polynomial x^4 + 20*x^2 - 80]45274528"""4529F = E.base_field()4530if E.j_invariant() != 1728:4531raise ValueError, "j-invariant must be 1728."4532if F.characteristic() in [2,3,5]:4533raise NotImplementedError, "Not implemented in characteristic 2, 3 or 5."4534model = "minimal" if F is QQ else None4535# quick test for a negative answer (from Fricke module)4536square5 = F(5).is_square()4537square1 = F(-1).is_square()4538if not square5 and not square1:4539return []4540Ew = E.short_weierstrass_model()4541iso = E.isomorphism_to(Ew)4542a = Ew.a4()4543x = polygen(F)4544isogs = []4545# 2 cases4546# Type 1: if -1 is a square we have 2 endomorphisms4547if square1:4548i = F(-1).sqrt()4549isogs = [Ew.isogeny(f) for f in [x**2+a/(1+2*i), x**2+a/(1-2*i)]]4550[isog.set_post_isomorphism(isog.codomain().isomorphism_to(E)) for isog in isogs]4551# Type 2: if 5 is a square we have up to 4 (non-endomorphism) isogenies4552if square5:4553betas = (x**4+20*a*x**2-80*a**2).roots(multiplicities=False)4554betas.sort()4555gammas = [a*(beta**2-2)/6 for beta in betas]4556isogs += [Ew.isogeny(x**2+beta*x+gamma, model=model) for beta,gamma in zip(betas,gammas)]4557[isog.set_pre_isomorphism(iso) for isog in isogs]4558return isogs45594560def isogenies_7_0(E):4561"""4562Returns list of all 7-isogenies from E when the j-invariant is 0.45634564OUTPUT:45654566(list) 7-isogenies with codomain E. In general these are4567normalised; but if `-3` is a square then there are two4568endomorphisms of degree `7`, for which the codomain is the same as4569the domain; and over `\QQ`, the codomain is a minimal model.45704571.. note::45724573This implementation requires that the characteristic is not 2,45743 or 7.45754576.. note::45774578This function would normally be invoked indirectly via ``E.isogenies_prime_degree(7)``.45794580EXAMPLES:45814582First some examples of endomorphisms::45834584sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_7_04585sage: K.<r> = QuadraticField(-3)4586sage: E = EllipticCurve(K, [0,1])4587sage: isogenies_7_0(E)4588[Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3,4589Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3]45904591sage: E = EllipticCurve(GF(13^2,'a'),[0,-3])4592sage: isogenies_7_0(E)4593[Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2, Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2]45944595Now some examples of 7-isogenies which are not endomorphisms::45964597sage: K = GF(101)4598sage: E = EllipticCurve(K, [0,1])4599sage: isogenies_7_0(E)4600[Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 101 to Elliptic Curve defined by y^2 = x^3 + 55*x + 100 over Finite Field of size 101, Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 101 to Elliptic Curve defined by y^2 = x^3 + 83*x + 26 over Finite Field of size 101]46014602Examples over a number field::46034604sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_7_04605sage: E = EllipticCurve('27a1').change_ring(QuadraticField(-3,'r'))4606sage: isogenies_7_0(E)4607[Isogeny of degree 7 from Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3,4608Isogeny of degree 7 from Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3]46094610sage: K.<a> = NumberField(x^6 + 1512*x^3 - 21168)4611sage: E = EllipticCurve(K, [0,1])4612sage: isogs = isogenies_7_0(E)4613sage: [phi.codomain().a_invariants() for phi in isogs]4614[(0, 0, 0, -5/294*a^5 - 300/7*a^2, -55/2*a^3 - 1133),4615(0, 0, 0, -295/1176*a^5 - 5385/14*a^2, 55/2*a^3 + 40447)]4616sage: [phi.codomain().j_invariant() for phi in isogs]4617[158428486656000/7*a^3 - 313976217600000,4618-158428486656000/7*a^3 - 34534529335296000]4619"""4620if E.j_invariant()!=0:4621raise ValueError, "j-invariant must be 0."4622F = E.base_field()4623if F.characteristic() in [2,3,7]:4624raise NotImplementedError, "Not implemented when the characteristic of the base field is 2, 3 or 7."4625x = polygen(F)4626Ew = E.short_weierstrass_model()4627iso = E.isomorphism_to(Ew)4628a = Ew.a6()4629model = "minimal" if F is QQ else None46304631# there will be 2 endomorphisms if -3 is a square:46324633ts = (x**2+3).roots(multiplicities=False)4634ts.sort()4635kers = [7*x-(2+6*t) for t in ts]4636kers = [k(x**3/a).monic() for k in kers]4637isogs = [Ew.isogeny(k,model=model) for k in kers]4638if len(isogs)>0:4639[endo.set_post_isomorphism(endo.codomain().isomorphism_to(E)) for endo in isogs]46404641# we may have up to 6 other isogenies:4642ts = (x**2-21).roots(multiplicities=False)4643for t0 in ts:4644s3 = a/(28+6*t0)4645ss = (x**3-s3).roots(multiplicities=False)4646ss.sort()4647ker = x**3 - 2*t0*x**2 - 4*t0*x + 4*t0 + 284648kers = [ker(x/s).monic() for s in ss]4649isogs += [Ew.isogeny(k, model=model) for k in kers]46504651[isog.set_pre_isomorphism(iso) for isog in isogs]4652return isogs46534654def isogenies_7_1728(E):4655"""4656Returns list of all 7-isogenies from E when the j-invariant is 1728.46574658OUTPUT:46594660(list) 7-isogenies with codomain E. In general these are4661normalised; but over `\QQ` the codomain is a minimal model.46624663.. note::46644665This implementation requires that the characteristic is not 2,46663, or 7.46674668.. note::46694670This function would normally be invoked indirectly via ``E.isogenies_prime_degree(7)``.46714672EXAMPLES::46734674sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_7_17284675sage: E = EllipticCurve(GF(47), [1, 0])4676sage: isogenies_7_1728(E)4677[Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 47 to Elliptic Curve defined by y^2 = x^3 + 26 over Finite Field of size 47,4678Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 47 to Elliptic Curve defined by y^2 = x^3 + 21 over Finite Field of size 47]46794680An example in characteristic 53 (for which an earlier implementation did not work)::46814682sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_7_17284683sage: E = EllipticCurve(GF(53), [1, 0])4684sage: isogenies_7_1728(E)4685[]4686sage: E = EllipticCurve(GF(53^2,'a'), [1, 0])4687sage: [iso.codomain().ainvs() for iso in isogenies_7_1728(E)]4688[(0, 0, 0, 36, 19*a + 15), (0, 0, 0, 36, 34*a + 38), (0, 0, 0, 33, 39*a + 28), (0, 0, 0, 33, 14*a + 25), (0, 0, 0, 19, 45*a + 16), (0, 0, 0, 19, 8*a + 37), (0, 0, 0, 3, 45*a + 16), (0, 0, 0, 3, 8*a + 37)]46894690::46914692sage: K.<a> = NumberField(x^8 + 84*x^6 - 1890*x^4 + 644*x^2 - 567)4693sage: E = EllipticCurve(K, [1, 0])4694sage: isogs = isogenies_7_1728(E)4695sage: [phi.codomain().a_invariants() for phi in isogs]4696[(0,46970,46980,469935/636*a^6 + 55/12*a^4 - 79135/636*a^2 + 1127/212,4700155/636*a^7 + 245/12*a^5 - 313355/636*a^3 - 3577/636*a),4701(0,47020,47030,470435/636*a^6 + 55/12*a^4 - 79135/636*a^2 + 1127/212,4705-155/636*a^7 - 245/12*a^5 + 313355/636*a^3 + 3577/636*a)]4706sage: [phi.codomain().j_invariant() for phi in isogs]4707[-526110256146528/53*a^6 + 183649373229024*a^4 - 3333881559996576/53*a^2 + 2910267397643616/53,4708-526110256146528/53*a^6 + 183649373229024*a^4 - 3333881559996576/53*a^2 + 2910267397643616/53]4709sage: E1 = isogs[0].codomain()4710sage: E2 = isogs[1].codomain()4711sage: E1.is_isomorphic(E2)4712False4713sage: E1.is_quadratic_twist(E2)4714-14715"""4716if E.j_invariant()!=1728:4717raise ValueError, "j_invariant must be 1728 (in base field)."4718F = E.base_field()4719if F.characteristic() in [2,3,7]:4720raise NotImplementedError, "Not implemented when the characteristic of the base field is 2, 3 or 7."4721Ew = E.short_weierstrass_model()4722iso = E.isomorphism_to(Ew)4723a = Ew.a4()47244725ts = (Fricke_module(7)-1728).numerator().roots(F,multiplicities=False)4726if len(ts)==0:4727return []4728ts.sort()4729isogs = []4730model = "minimal" if F is QQ else None4731x = polygen(F)4732for t0 in ts:4733s2 = a/t04734ss = (x**2-s2).roots(multiplicities=False)4735ss.sort()4736ker = 9*x**3 + (-3*t0**3 - 36*t0**2 - 123*t0)*x**2 + (-8*t0**3 - 101*t0**2 - 346*t0 + 35)*x - 7*t0**3 - 88*t0**2 - 296*t0 + 2847374738kers = [ker(x/s) for s in ss]4739isogs += [Ew.isogeny(k.monic(), model=model) for k in kers]4740[isog.set_pre_isomorphism(iso) for isog in isogs]4741return isogs47424743def isogenies_13_0(E):4744"""4745Returns list of all 13-isogenies from E when the j-invariant is 0.47464747OUTPUT:47484749(list) 13-isogenies with codomain E. In general these are4750normalised; but if `-3` is a square then there are two4751endomorphisms of degree `13`, for which the codomain is the same4752as the domain.47534754.. note::47554756This implementation requires that the characteristic is not 2,47573 or 13.47584759.. note::47604761This function would normally be invoked indirectly via ``E.isogenies_prime_degree(13)``.47624763EXAMPLES::47644765sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_13_047664767Endomorphisms of degree 13 will exist when -3 is a square::47684769sage: K.<r> = QuadraticField(-3)4770sage: E = EllipticCurve(K, [0, r]); E4771Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 34772sage: isogenies_13_0(E)4773[Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3,4774Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3]4775sage: isogenies_13_0(E)[0].rational_maps()4776(((-4/169*r - 11/169)*x^13 + (-128/13*r - 456/13)*x^10 + (-1224/13*r - 2664/13)*x^7 + (-2208/13*r + 5472/13)*x^4 + (1152/13*r - 8064/13)*x)/(x^12 + (4*r - 36)*x^9 + (-1080/13*r + 3816/13)*x^6 + (2112/13*r + 5184/13)*x^3 + (17280/169*r - 1152/169)), ((18/2197*r - 35/2197)*x^18*y + (-23142/2197*r + 35478/2197)*x^15*y + (-1127520/2197*r + 1559664/2197)*x^12*y + (87744/2197*r + 5992704/2197)*x^9*y + (-6625152/2197*r + 9085824/2197)*x^6*y + (28919808/2197*r - 2239488/2197)*x^3*y + (-1990656/2197*r + 3870720/2197)*y)/(x^18 + (6*r - 54)*x^15 + (-3024/13*r + 11808/13)*x^12 + (31296/13*r - 51840/13)*x^9 + (-487296/169*r - 2070144/169)*x^6 + (-940032/169*r - 248832/169)*x^3 + (-1990656/2197*r + 3870720/2197)))47774778An example of endomorphisms over a finite field::47794780sage: K = GF(19^2,'a')4781sage: E = EllipticCurve(j=K(0)); E4782Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^24783sage: isogenies_13_0(E)4784[Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2,4785Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2]4786sage: isogenies_13_0(E)[0].rational_maps()4787((6*x^13 - 6*x^10 - 3*x^7 + 6*x^4 + x)/(x^12 - 5*x^9 - 9*x^6 - 7*x^3 + 5), (-8*x^18*y - 9*x^15*y + 9*x^12*y - 5*x^9*y + 5*x^6*y - 7*x^3*y + 7*y)/(x^18 + 2*x^15 + 3*x^12 - x^9 + 8*x^6 - 9*x^3 + 7))47884789A previous implementation did not work in some characteristics::47904791sage: K = GF(29)4792sage: E = EllipticCurve(j=K(0))4793sage: isogenies_13_0(E)4794[Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 26*x + 12 over Finite Field of size 29, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 16*x + 28 over Finite Field of size 29]47954796::47974798sage: K = GF(101)4799sage: E = EllipticCurve(j=K(0)); E.ainvs()4800(0, 0, 0, 0, 1)4801sage: [phi.codomain().ainvs() for phi in isogenies_13_0(E)]4802[(0, 0, 0, 64, 36), (0, 0, 0, 42, 66)]48034804::48054806sage: x = polygen(QQ)4807sage: f = x^12 + 78624*x^9 - 130308048*x^6 + 2270840832*x^3 - 545001799684808sage: K.<a> = NumberField(f)4809sage: E = EllipticCurve(j=K(0)); E.ainvs()4810(0, 0, 0, 0, 1)4811sage: [phi.codomain().ainvs() for phi in isogenies_13_0(E)]4812[(0, 0, 0, -739946459/23857162861049856*a^11 - 2591641747/1062017577504*a^8 + 16583647773233/4248070310016*a^5 - 14310911337/378211388*a^2, 26146225/4248070310016*a^9 + 7327668845/14750244132*a^6 + 174618431365/756422776*a^3 - 378332499709/94552847), (0, 0, 0, 3501275/5964290715262464*a^11 + 24721025/531008788752*a^8 - 47974903745/1062017577504*a^5 - 6773483100/94552847*a^2, 6699581/4248070310016*a^9 + 1826193509/14750244132*a^6 - 182763866047/756422776*a^3 - 321460597/94552847)]4813"""4814if E.j_invariant()!=0:4815raise ValueError, "j-invariant must be 0."4816F = E.base_field()4817if F.characteristic() in [2,3,13]:4818raise NotImplementedError, "Not implemented when the characteristic of the base field is 2, 3 or 13."4819Ew = E.short_weierstrass_model()4820iso = E.isomorphism_to(Ew)4821a = Ew.a6()4822model = "minimal" if F is QQ else None4823x = polygen(F)48244825# there will be 2 endomorphisms if -3 is a square:4826ts = (x**2+3).roots(multiplicities=False)4827ts.sort()4828kers = [13*x**2 + (78*t + 26)*x + 24*t + 40 for t in ts]4829kers = [k(x**3/a).monic() for k in kers]4830isogs = [Ew.isogeny(k,model=model) for k in kers]4831if len(isogs)>0:4832[endo.set_post_isomorphism(endo.codomain().isomorphism_to(E)) for endo in isogs]48334834# we may have up to 12 other isogenies:4835ts = (x**4 + 7*x**3 + 20*x**2 + 19*x + 1).roots(multiplicities=False)4836ts.sort()4837for t0 in ts:4838s3 = a / (6*t0**3 + 32*t0**2 + 68*t0 + 4)4839ss = (x**3-s3).roots(multiplicities=False)4840ss.sort()4841ker = (x**6 + (20*t0**3 + 106*t0**2 + 218*t0 + 4)*x**54842+ (-826*t0**3 - 4424*t0**2 - 9244*t0 - 494)*x**44843+ (13514*t0**3 + 72416*t0**2 + 151416*t0 + 8238)*x**34844+ (-101948*t0**3 - 546304*t0**2 - 1142288*t0 - 62116)*x**24845+ (354472*t0**3 + 1899488*t0**2 + 3971680*t0 + 215960)*x4846- 459424*t0**3 - 2461888*t0**2 - 5147648*t0 - 279904)4847kers = [ker(x/s).monic() for s in ss]4848isogs += [Ew.isogeny(k, model=model) for k in kers]48494850[isog.set_pre_isomorphism(iso) for isog in isogs]48514852return isogs48534854def isogenies_13_1728(E):4855"""4856Returns list of all 13-isogenies from E when the j-invariant is 1728.48574858OUTPUT:48594860(list) 13-isogenies with codomain E. In general these are4861normalised; but if `-1` is a square then there are two4862endomorphisms of degree `13`, for which the codomain is the same4863as the domain; and over `\QQ`, the codomain is a minimal model.48644865.. note::48664867This implementation requires that the characteristic is not48682, 3 or 13.48694870.. note::48714872This function would normally be invoked indirectly via ``E.isogenies_prime_degree(13)``.48734874EXAMPLES::48754876sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogenies_13_172848774878sage: K.<i> = QuadraticField(-1)4879sage: E = EllipticCurve([0,0,0,i,0]); E.ainvs()4880(0, 0, 0, i, 0)4881sage: isogenies_13_1728(E)4882[Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1,4883Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1]48844885::48864887sage: K = GF(83)4888sage: E = EllipticCurve(K, [0,0,0,5,0]); E.ainvs()4889(0, 0, 0, 5, 0)4890sage: isogenies_13_1728(E)4891[]4892sage: K = GF(89)4893sage: E = EllipticCurve(K, [0,0,0,5,0]); E.ainvs()4894(0, 0, 0, 5, 0)4895sage: isogenies_13_1728(E)4896[Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89 to Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89,4897Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89 to Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89]48984899::49004901sage: K = GF(23)4902sage: E = EllipticCurve(K, [1,0])4903sage: isogenies_13_1728(E)4904[Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 23 to Elliptic Curve defined by y^2 = x^3 + 16 over Finite Field of size 23, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 23 to Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 23]49054906::49074908sage: x = polygen(QQ)4909sage: f = x^12 + 1092*x^10 - 432432*x^8 + 6641024*x^6 - 282896640*x^4 - 149879808*x^2 - 3493601284910sage: K.<a> = NumberField(f)4911sage: E = EllipticCurve(K, [1,0])4912sage: [phi.codomain().ainvs() for phi in isogenies_13_1728(E)]4913[(0,49140,49150,491611090413835/20943727039698624*a^10 + 32280103535965/55849938772529664*a^8 - 355655987835845/1551387188125824*a^6 + 19216954517530195/5235931759924656*a^4 - 1079766118721735/5936430566808*a^2 + 156413528482727/8080141604822,4917214217013065/82065216155553792*a^11 + 1217882637605/427423000810176*a^9 - 214645003230565/189965778137856*a^7 + 22973355421236025/1282269002430528*a^5 - 2059145797340695/2544184528632*a^3 - 23198483147321/989405094468*a),4918(0,49190,49200,492111090413835/20943727039698624*a^10 + 32280103535965/55849938772529664*a^8 - 355655987835845/1551387188125824*a^6 + 19216954517530195/5235931759924656*a^4 - 1079766118721735/5936430566808*a^2 + 156413528482727/8080141604822,4922-214217013065/82065216155553792*a^11 - 1217882637605/427423000810176*a^9 + 214645003230565/189965778137856*a^7 - 22973355421236025/1282269002430528*a^5 + 2059145797340695/2544184528632*a^3 + 23198483147321/989405094468*a)]49234924"""4925if E.j_invariant()!=1728:4926raise ValueError, "j-invariant must be 1728."4927F = E.base_field()4928if F.characteristic() in [2, 3, 7, 13, 167, 233, 271, 1117]:4929raise NotImplementedError, "Not implemented when the characteristic of the base field is 2, 3 or 13."4930Ew = E.short_weierstrass_model()4931iso = E.isomorphism_to(Ew)4932a = Ew.a4()4933model = "minimal" if F is QQ else None4934x = polygen(F)49354936# we will have two endomorphisms if -1 is a square:4937ts = (x**2+1).roots(multiplicities=False)4938ts.sort()4939kers = [13*x**3 + (-26*i - 13)*x**2 + (-52*i - 13)*x - 2*i - 3 for i in ts]4940kers = [k(x**2/a).monic() for k in kers]4941isogs = [Ew.isogeny(k,model=model) for k in kers]4942if len(isogs)>0:4943[endo.set_post_isomorphism(endo.codomain().isomorphism_to(E)) for endo in isogs]49444945# we may have up to 12 other isogenies:49464947ts = (x**6 + 10*x**5 + 46*x**4 + 108*x**3 + 122*x**2 + 38*x - 1).roots(multiplicities=False)4948ts.sort()4949for t0 in ts:4950s2 = a/(66*t0**5 + 630*t0**4 + 2750*t0**3 + 5882*t0**2 + 5414*t0 + 162)4951ss = (x**2-s2).roots(multiplicities=False)4952ss.sort()4953ker = (x**6 + (-66*t0**5 - 630*t0**4 - 2750*t0**3 - 5882*t0**24954- 5414*t0 - 162)*x**5 + (-21722*t0**5 - 205718*t0**4 -4955890146*t0**3 - 1873338*t0**2 - 1652478*t0 + 61610)*x**44956+ (-3391376*t0**5 - 32162416*t0**4 - 139397232*t0**3 -4957294310576*t0**2 - 261885968*t0 + 6105552)*x**3 +4958(-241695080*t0**5 - 2291695976*t0**4 - 9930313256*t0**34959- 20956609720*t0**2 - 18625380856*t0 + 469971320)*x**2 +4960(-8085170432*t0**5 - 76663232384*t0**4 -4961332202985024*t0**3 - 701103233152*t0**2 -4962623190845440*t0 + 15598973056)*x - 101980510208*t0**5 -4963966973468160*t0**4 - 4190156868352*t0**3 -49648843158270336*t0**2 - 7860368751232*t0 + 196854655936)49654966kers = [ker(x/s).monic() for s in ss]4967isogs += [Ew.isogeny(k, model=model) for k in kers]49684969[isog.set_pre_isomorphism(iso) for isog in isogs]49704971return isogs49724973# Utility function for manipulating isogeny degree matrices49744975def fill_isogeny_matrix(M):4976"""4977Returns a filled isogeny matrix giving all degrees from one giving only prime degrees.49784979INPUT:49804981- ``M`` -- a square symmetric matrix whose off-diagonal `i`, `j`4982entry is either a prime `l` (if the `i`'th and `j`'th curves4983have an `l`-isogeny between them), otherwise is 0.49844985OUTPUT:49864987(matrix) a square matrix with entries `1` on the diagonal, and in4988general the `i`, `j` entry is `d>0` if `d` is the minimal degree4989of an isogeny from the `i`'th to the `j`'th curve,49904991EXAMPLES::49924993sage: 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]]); M4994[0 2 3 3 0 0]4995[2 0 0 0 3 3]4996[3 0 0 0 2 0]4997[3 0 0 0 0 2]4998[0 3 2 0 0 0]4999[0 3 0 2 0 0]5000sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix5001sage: fill_isogeny_matrix(M)5002[ 1 2 3 3 6 6]5003[ 2 1 6 6 3 3]5004[ 3 6 1 9 2 18]5005[ 3 6 9 1 18 2]5006[ 6 3 2 18 1 9]5007[ 6 3 18 2 9 1]5008"""5009from sage.matrix.all import Matrix5010from sage.rings.infinity import Infinity50115012n = M.nrows()5013M0 = copy(M)5014for i in range(n):5015M0[i,i]=150165017def fix(d):5018if d==0: return Infinity5019return d50205021def fix2(d):5022if d==Infinity: return 05023return d50245025def pr(M1,M2):5026return Matrix([[fix2(min([fix(M1[i,k]*M2[k,j]) for k in range(n)])) for i in range(n)] for j in range(n)])50275028M1 = M05029M2 = pr(M0,M1)5030while M1!=M2:5031M1 = M25032M2 = pr(M0,M1)50335034return M150355036def unfill_isogeny_matrix(M):5037"""5038Reverses the action of ``fill_isogeny_matrix``.50395040INPUT:50415042- ``M`` -- a square symmetric matrix of integers.50435044OUTPUT:50455046(matrix) a square symmetric matrix obtained from ``M`` by5047replacing non-prime entries with `0`.50485049EXAMPLES::50505051sage: 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]]); M5052[0 2 3 3 0 0]5053[2 0 0 0 3 3]5054[3 0 0 0 2 0]5055[3 0 0 0 0 2]5056[0 3 2 0 0 0]5057[0 3 0 2 0 0]5058sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix, unfill_isogeny_matrix5059sage: M1 = fill_isogeny_matrix(M); M15060[ 1 2 3 3 6 6]5061[ 2 1 6 6 3 3]5062[ 3 6 1 9 2 18]5063[ 3 6 9 1 18 2]5064[ 6 3 2 18 1 9]5065[ 6 3 18 2 9 1]5066sage: unfill_isogeny_matrix(M1)5067[0 2 3 3 0 0]5068[2 0 0 0 3 3]5069[3 0 0 0 2 0]5070[3 0 0 0 0 2]5071[0 3 2 0 0 0]5072[0 3 0 2 0 0]5073sage: unfill_isogeny_matrix(M1) == M5074True5075"""5076from sage.matrix.all import Matrix5077from sage.rings.infinity import Infinity50785079n = M.nrows()5080M1 = copy(M)5081zero = Integer(0)5082for i in range(n):5083M1[i,i] = zero5084for j in range(i):5085if not M1[i,j].is_prime():5086M1[i,j] = zero5087M1[j,i] = zero5088return M1508950905091