Path: blob/master/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
8820 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, separable 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"""5354#*****************************************************************************55# Copyright (C) 2009 Daniel Shumow <[email protected]>56#57# Distributed under the terms of the GNU General Public License (GPL)58# http://www.gnu.org/licenses/59#*****************************************************************************6061from copy import deepcopy, copy6263from sage.categories import homset6465from sage.categories.morphism import Morphism6667from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing68from sage.rings.polynomial.polynomial_ring import polygen69from sage.rings.all import Integer, ZZ70from sage.rings.laurent_series_ring import LaurentSeriesRing71from sage.rings.polynomial.all import is_Polynomial72from sage.schemes.elliptic_curves.all import EllipticCurve73from sage.schemes.elliptic_curves.all import is_EllipticCurve7475from sage.rings.number_field.number_field_base import is_NumberField7677from sage.rings.rational_field import is_RationalField, QQ7879from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism8081from sage.sets.set import Set8283from sage.misc.cachefunc import cached_function8485#86# Private function for parsing input to determine the type of87# algorithm88#89def isogeny_determine_algorithm(E, kernel, codomain, degree, model):90r"""91Helper function that allows the various isogeny functions to infer92the algorithm type from the parameters passed in.9394If ``kernel`` is a list of points on the EllipticCurve `E`, then95we assume the algorithm to use is Velu.9697If ``kernel`` is a list of coefficients or a univariate polynomial98we try to use the Kohel's algorithms.99100EXAMPLES:101102This helper function will be implicitly called by the following examples::103104sage: R.<x> = GF(5)[]105sage: E = EllipticCurve(GF(5), [0,0,0,1,0])106sage: phi = EllipticCurveIsogeny(E, x+3)107sage: phi2 = EllipticCurveIsogeny(E, [GF(5)(3),GF(5)(1)])108sage: phi == phi2109True110sage: phi3 = EllipticCurveIsogeny(E, E((2,0)) )111sage: phi3 == phi2112True113sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_determine_algorithm114sage: isogeny_determine_algorithm(E, x+3, None, None, None)115'kohel'116sage: isogeny_determine_algorithm(E, [3, 1], None, None, None)117'kohel'118sage: isogeny_determine_algorithm(E, E((2,0)), None, None, None)119'velu'120121"""122123kernel_is_list = (type(kernel) == list)124125if not kernel_is_list and kernel in E :126kernel = [kernel]127kernel_is_list = True128129if (is_Polynomial(kernel) or ( kernel_is_list) and (kernel[0] in E.base_ring()) ):130algorithm = "kohel"131elif (kernel_is_list) and (kernel[0] in E): # note that if kernel[0] is on an extension of E this condition will be false132algorithm = "velu"133else:134raise ValueError, "Invalid Parameters to EllipticCurveIsogeny constructor."135136return algorithm137138139def isogeny_codomain_from_kernel(E, kernel, degree=None):140r"""141This function computes the isogeny codomain given a kernel.142143INPUT:144145- ``E`` - The domain elliptic curve.146147- ``kernel`` - Either a list of points in the kernel of the isogeny, or a148kernel polynomial (specified as a either a univariate149polynomial or a coefficient list.)150151- ``degree`` - an integer, (default:``None``) optionally specified degree152of the kernel.153154OUTPUT:155156(elliptic curve) the codomain of the separable normalized isogeny157from this kernel158159EXAMPLES::160161sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_codomain_from_kernel162sage: E = EllipticCurve(GF(7), [1,0,1,0,1])163sage: R.<x> = GF(7)[]164sage: isogeny_codomain_from_kernel(E, [4,1], degree=3)165Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7166sage: EllipticCurveIsogeny(E, [4,1]).codomain() == isogeny_codomain_from_kernel(E, [4,1], degree=3)167True168sage: isogeny_codomain_from_kernel(E, x^3 + x^2 + 4*x + 3)169Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7170sage: isogeny_codomain_from_kernel(E, x^3 + 2*x^2 + 4*x + 3)171Elliptic Curve defined by y^2 + x*y + y = x^3 + 5*x + 2 over Finite Field of size 7172173sage: E = EllipticCurve(GF(19), [1,2,3,4,5])174sage: kernel_list = [E((15,10)), E((10,3)),E((6,5))]175sage: isogeny_codomain_from_kernel(E, kernel_list)176Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19177178"""179180algorithm = isogeny_determine_algorithm(E, kernel, None, degree, None);181182if ("velu"==algorithm):183# if we are using Velu's formula, just instantiate the isogeny184# and return the codomain185codomain = EllipticCurveIsogeny(E, kernel).codomain()186elif ("kohel"==algorithm):187codomain = compute_codomain_kohel(E, kernel, degree)188189return codomain190191192def compute_codomain_formula(E, v, w):193r"""194Given parameters `v` and `w` (as in Velu / Kohel / etc formulas)195computes the codomain curve.196197EXAMPLES:198199This formula is used by every Isogeny Instantiation::200201sage: E = EllipticCurve(GF(19), [1,2,3,4,5])202sage: phi = EllipticCurveIsogeny(E, E((1,2)) )203sage: phi.codomain()204Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19205sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_formula206sage: v = phi._EllipticCurveIsogeny__v207sage: w = phi._EllipticCurveIsogeny__w208sage: compute_codomain_formula(E, v, w)209Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19210211"""212213a1,a2,a3,a4,a6 = E.ainvs()214215A4 = a4 - 5*v216A6 = a6 - (a1**2 + 4*a2)*v - 7*w217218return EllipticCurve([a1, a2, a3, A4, A6])219220221def compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4):222r"""223The formula for computing `v` and `w` using Kohel's formulas for224isogenies of degree 2.225226EXAMPLES:227228This function will be implicitly called by the following example::229230sage: E = EllipticCurve(GF(19), [1,2,3,4,5])231sage: phi = EllipticCurveIsogeny(E, [9,1])232sage: phi233Isogeny 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 19234sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg1235sage: a1,a2,a3,a4,a6 = E.ainvs()236sage: x0 = -9237sage: y0 = -(a1*x0 + a3)/2238sage: compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4)239(18, 9)240241"""242243v = (3*x0**2 + 2*a2*x0 + a4 - a1*y0)244w = x0*v245246return (v,w)247248249def compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3):250r"""251The formula for computing `v` and `w` using Kohel's formulas for252isogenies of degree 3.253254EXAMPLES:255256This function will be implicitly called by the following example::257258sage: E = EllipticCurve(GF(19), [1,2,3,4,5])259sage: R.<x> = GF(19)[]260sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12)261sage: phi262Isogeny 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 19263sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg3264sage: (b2,b4) = (E.b2(), E.b4())265sage: (s1, s2, s3) = (-7, 15, -12)266sage: compute_vw_kohel_even_deg3(b2, b4, s1, s2, s3)267(4, 7)268269"""270271temp1 = (s1**2 - 2*s2)272v = 3*temp1 + b2*s1/2 + 3*b4/2273w = 3*(s1**3 - 3*s1*s2 + 3*s3) + b2*temp1/2 + b4*s1/2274275return (v,w)276277278def compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n):279r"""280This function computes the `v` and `w` according to Kohel's formulas.281282EXAMPLES:283284This function will be implicitly called by the following example::285286sage: E = EllipticCurve(GF(19), [18,17,16,15,14])287sage: R.<x> = GF(19)[]288sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11)289sage: phi290Isogeny 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 19291sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_odd292sage: (b2,b4,b6) = (E.b2(), E.b4(), E.b6())293sage: (s1,s2,s3) = (-14,3,-11)294sage: compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,3)295(7, 1)296297"""298299v = 6*(s1**2 - 2*s2) + b2*s1 + n*b4300w = 10*(s1**3 - 3*s1*s2 + 3*s3) + 2*b2*(s1**2 - 2*s2) + 3*b4*s1 + n*b6301302return (v,w)303304305def compute_codomain_kohel(E, kernel, degree):306r"""307This function computes the codomain from the kernel polynomial as308per Kohel's formulas.309310EXAMPLES::311312sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_kohel313sage: E = EllipticCurve(GF(19), [1,2,3,4,5])314sage: phi = EllipticCurveIsogeny(E, [9,1])315sage: phi.codomain() == isogeny_codomain_from_kernel(E, [9,1])316True317sage: compute_codomain_kohel(E, [9,1], 2)318Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19319sage: R.<x> = GF(19)[]320sage: E = EllipticCurve(GF(19), [18,17,16,15,14])321sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11)322sage: phi.codomain() == isogeny_codomain_from_kernel(E, x^3 + 14*x^2 + 3*x + 11)323True324sage: compute_codomain_kohel(E, x^3 + 14*x^2 + 3*x + 11, 7)325Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19326sage: E = EllipticCurve(GF(19), [1,2,3,4,5])327sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12)328sage: isogeny_codomain_from_kernel(E, x^3 + 7*x^2 + 15*x + 12) == phi.codomain()329True330sage: compute_codomain_kohel(E, x^3 + 7*x^2 + 15*x + 12,4)331Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19332333NOTES:334335This function uses the formulas of Section 2.4 of [K96].336337REFERENCES:338339- [K96] Kohel, "Endomorphism Rings of Elliptic Curves over Finite Fields"340341"""342343# First set up the polynomial ring344345base_field = E.base_ring()346347if (is_Polynomial(kernel)):348psi = kernel349kernel_list = psi.list()350poly_ring = psi.parent()351x = psi.variables()[0]352elif (list == type(kernel)) and (kernel[0] in base_field):353kernel_list = kernel354poly_ring = base_field.polynomial_ring()355psi = poly_ring(kernel_list)356x = poly_ring.gen()357else:358raise ValueError, "input not of correct type"359360361# next determine the even / odd part of the isogeny362psi_2tor = two_torsion_part(E, poly_ring, psi, degree)363364if (0 != psi_2tor.degree()): # even degree case365366psi_quo = poly_ring(psi/psi_2tor)367368if (0 != psi_quo.degree()):369raise ArithmeticError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion."370371n = psi_2tor.degree()372373if (1 == n):374375a1,a2,a3,a4,a6 = E.ainvs()376377x0 = -psi_2tor.constant_coefficient()378379# determine y0380if (2 == base_field.characteristic()):381y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt()382else:383y0 = -(a1*x0 + a3)/2384385(v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4)386387elif (3 == n):388389b2 = E.b2()390b4 = E.b4()391392s = psi_2tor.list()393s1 = -s[n-1]394s2 = s[n-2]395s3 = -s[n-3]396397(v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3)398399else:400401n = psi.degree()402403b2 = E.b2()404b4 = E.b4()405b6 = E.b6()406407s1 = 0; s2 = 0; s3 = 0408409if (1 <= n):410s1 = -kernel_list[n-1]411412if (2 <= n):413s2 = kernel_list[n-2]414415if (3 <= n):416s3 = -kernel_list[n-3]417418# initializing these allows us to calculate E2.419(v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n);420421return compute_codomain_formula(E, v, w)422423424def two_torsion_part(E, poly_ring, psi, degree):425r"""426427Returns the greatest common divisor of ``psi`` and the 2 torsion428polynomial of `E`.429430EXAMPLES:431432Every function that computes the kernel polynomial via Kohel's433formulas will call this function::434435sage: E = EllipticCurve(GF(19), [1,2,3,4,5])436sage: R.<x> = GF(19)[]437sage: phi = EllipticCurveIsogeny(E, x + 13)438sage: isogeny_codomain_from_kernel(E, x + 13) == phi.codomain()439True440sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part441sage: two_torsion_part(E, R, x+13, 2)442x + 13443444"""445if (None==degree) or (0 == degree % 2):446447x = poly_ring.gens()[0]448psi_2 = E.two_division_polynomial(x)449psi_G = poly_ring(psi.gcd(psi_2))450451else:452453psi_G = poly_ring(1)454455return psi_G456457458class EllipticCurveIsogeny(Morphism):459r"""460Class Implementing Isogenies of Elliptic Curves461462This class implements cyclic, separable, normalized isogenies of463elliptic curves.464465Several different algorithms for computing isogenies are466available. These include:467468- Velu's Formulas: Velu's original formulas for computing469isogenies. This algorithm is selected by giving as the470``kernel`` parameter a list of points which generate a finite471subgroup.472473- Kohel's Formulas: Kohel's original formulas for computing474isogenies. This algorithm is selected by giving as the475``kernel`` parameter a monic polynomial (or a coefficient list476(little endian)) which will define the kernel of the isogeny.477478INPUT:479480- ``E`` - an elliptic curve, the domain of the isogeny to481initialize.482483- ``kernel`` - a kernel, either a point in ``E``, a list of points484in ``E``, a monic kernel polynomial, or ``None``.485If initializing from a domain/codomain, this must be486set to None.487488- ``codomain`` - an elliptic curve (default:``None``). If ``kernel``489is ``None``, then this must be the codomain of a cyclic,490separable, normalized isogeny, furthermore, ``degree``491must be the degree of the isogeny from ``E`` to492``codomain``. If ``kernel`` is not ``None``, then this493must be isomorphic to the codomain of the cyclic normalized494separable isogeny defined by ``kernel``, in this case, the495isogeny is post composed with an isomorphism so that this496parameter is the codomain.497498- ``degree`` - an integer (default:``None``).499If ``kernel`` is ``None``, then this is the degree of the500isogeny from ``E`` to ``codomain``.501If ``kernel`` is not ``None``, then this is used to determine502whether or not to skip a gcd of the kernel polynomial with the503two torsion polynomial of ``E``.504505- ``model`` - a string (default:``None``). Only supported variable is506``minimal``, in which case if ``E`` is a curve over the507rationals, then the codomain is set to be the unique global508minimum model.509510- ``check`` (default: ``True``) checks if the input is valid to define an isogeny511512EXAMPLES:513514A simple example of creating an isogeny of a field of small515characteristic::516517sage: E = EllipticCurve(GF(7), [0,0,0,1,0])518sage: phi = EllipticCurveIsogeny(E, E((0,0)) ); phi519Isogeny 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 7520sage: phi.degree() == 2521True522sage: phi.kernel_polynomial()523x524sage: phi.rational_maps()525((x^2 + 1)/x, (x^2*y - y)/x^2)526sage: phi == loads(dumps(phi)) # known bug527True528529A more complicated example of a characteristic 2 field::530531sage: E = EllipticCurve(GF(2^4,'alpha'), [0,0,1,0,1])532sage: P = E((1,1))533sage: phi_v = EllipticCurveIsogeny(E, P); phi_v534Isogeny 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^4535sage: phi_ker_poly = phi_v.kernel_polynomial()536sage: phi_ker_poly537x + 1538sage: ker_poly_list = phi_ker_poly.list()539sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list)540sage: phi_k == phi_v541True542sage: phi_k.rational_maps()543((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1))544sage: phi_v.rational_maps()545((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1))546sage: phi_k.degree() == phi_v.degree()547True548sage: phi_k.degree()5493550sage: phi_k.is_separable()551True552sage: phi_v(E(0))553(0 : 1 : 0)554sage: alpha = E.base_field().gen()555sage: Q = E((0, alpha*(alpha + 1)))556sage: phi_v(Q)557(1 : alpha^2 + alpha : 1)558sage: phi_v(P) == phi_k(P)559True560sage: phi_k(P) == phi_v.codomain()(0)561True562563We can create an isogeny that has kernel equal to the full 2564torsion::565566sage: E = EllipticCurve(GF(3), [0,0,0,1,1])567sage: ker_list = E.division_polynomial(2).list()568sage: phi = EllipticCurveIsogeny(E, ker_list); phi569Isogeny 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 3570sage: phi(E(0))571(0 : 1 : 0)572sage: phi(E((0,1)))573(1 : 0 : 1)574sage: phi(E((0,2)))575(1 : 0 : 1)576sage: phi(E((1,0)))577(0 : 1 : 0)578sage: phi.degree()5794580581We can also create trivial isogenies with the trivial kernel::582583sage: E = EllipticCurve(GF(17), [11, 11, 4, 12, 10])584sage: phi_v = EllipticCurveIsogeny(E, E(0))585sage: phi_v.degree()5861587sage: phi_v.rational_maps()588(x, y)589sage: E == phi_v.codomain()590True591sage: P = E.random_point()592sage: phi_v(P) == P593True594595sage: E = EllipticCurve(GF(31), [23, 1, 22, 7, 18])596sage: phi_k = EllipticCurveIsogeny(E, [1])597sage: phi_k598Isogeny 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 31599sage: phi_k.degree()6001601sage: phi_k.rational_maps()602(x, y)603sage: phi_k.codomain() == E604True605sage: phi_k.kernel_polynomial()6061607sage: P = E.random_point(); P == phi_k(P)608True609610Velu and Kohel also work in characteristic 0::611612sage: E = EllipticCurve(QQ, [0,0,0,3,4])613sage: P_list = E.torsion_points()614sage: phi = EllipticCurveIsogeny(E, P_list)615sage: phi616Isogeny 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 Field617sage: P = E((0,2))618sage: phi(P)619(6 : -10 : 1)620sage: phi_ker_poly = phi.kernel_polynomial()621sage: phi_ker_poly622x + 1623sage: ker_poly_list = phi_ker_poly.list()624sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k625Isogeny 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 Field626sage: phi_k(P) == phi(P)627True628sage: phi_k == phi629True630sage: phi_k.degree()6312632sage: phi_k.is_separable()633True634635A more complicated example over the rationals (of odd degree)::636637sage: E = EllipticCurve('11a1')638sage: P_list = E.torsion_points()639sage: phi_v = EllipticCurveIsogeny(E, P_list); phi_v640Isogeny 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 Field641sage: P = E((16,-61))642sage: phi_v(P)643(0 : 1 : 0)644sage: ker_poly = phi_v.kernel_polynomial(); ker_poly645x^2 - 21*x + 80646sage: ker_poly_list = ker_poly.list()647sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k648Isogeny 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 Field649sage: phi_k == phi_v650True651sage: phi_v(P) == phi_k(P)652True653sage: phi_k.is_separable()654True655656We can also do this same example over the number field defined by657the irreducible two torsion polynomial of `E`::658659sage: E = EllipticCurve('11a1')660sage: P_list = E.torsion_points()661sage: K.<alpha> = NumberField(x^3 - 2* x^2 - 40*x - 158)662sage: EK = E.change_ring(K)663sage: P_list = [EK(P) for P in P_list]664sage: phi_v = EllipticCurveIsogeny(EK, P_list); phi_v665Isogeny 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 - 158666sage: P = EK((alpha/2,-1/2))667sage: phi_v(P)668(122/121*alpha^2 + 1633/242*alpha - 3920/121 : -1/2 : 1)669sage: ker_poly = phi_v.kernel_polynomial()670sage: ker_poly671x^2 - 21*x + 80672sage: ker_poly_list = ker_poly.list()673sage: phi_k = EllipticCurveIsogeny(EK, ker_poly_list)674sage: phi_k675Isogeny 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 - 158676sage: phi_v == phi_k677True678sage: phi_k(P) == phi_v(P)679True680sage: phi_k == phi_v681True682sage: phi_k.degree()6835684sage: phi_v.is_separable()685True686687The following example shows how to specify an isogeny from domain688and codomain::689690sage: E = EllipticCurve('11a1')691sage: R.<x> = QQ[]692sage: f = x^2 - 21*x + 80693sage: phi = E.isogeny(f)694sage: E2 = phi.codomain()695sage: phi_s = EllipticCurveIsogeny(E, None, E2, 5)696sage: phi_s697Isogeny 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 Field698sage: phi_s == phi699True700sage: phi_s.rational_maps() == phi.rational_maps()701True702703However only cyclic normalized isogenies can be constructed this704way. So it won't find the isogeny [3]::705706sage: E.isogeny(None, codomain=E,degree=9)707Traceback (most recent call last):708...709ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 9710711Also the presumed isogeny between the domain and codomain must be712normalized::713714sage: E2.isogeny(None,codomain=E,degree=5)715Traceback (most recent call last):716...717ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 5718sage: phi.dual()719Isogeny 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 Field720sage: phi.dual().is_normalized()721False722723Here an example of a construction of a endomorphisms with cyclic724kernel on a CM-curve::725726sage: K.<i> = NumberField(x^2+1)727sage: E = EllipticCurve(K, [1,0])728sage: RK.<X> = K[]729sage: f = X^2 - 2/5*i + 1/5730sage: phi= E.isogeny(f)731sage: isom = phi.codomain().isomorphism_to(E)732sage: phi.set_post_isomorphism(isom)733sage: phi.codomain() == phi.domain()734True735sage: phi.rational_maps()736(((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)),737((11/125*i + 2/125)*x^6*y + (-23/125*i + 64/125)*x^4*y + (141/125*i + 162/125)*x^2*y + (3/25*i - 4/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125)))738"""739740####################741# member variables742####################743744__check = None745#746# variables common to all algorithms747#748__E1 = None # domain curve749__E2 = None # codomain curve750751__degree = None752753__separable = True # This class only implements separable isogenies (for now.)754755__algorithm = None756757__this_hash = None758759__check = None760#761# pre isomorphism762#763__intermediate_domain = None764__pre_isomorphism = None765__prei_x_coord_ratl_map = None766__prei_y_coord_ratl_map = None767768#769# post isomorphism770#771772__intermediate_codomain = None773__post_isomorphism = None774__posti_x_coord_ratl_map = None775__posti_y_coord_ratl_map = None776777#778# algebraic structs779#780__base_field = None781__poly_ring = None782__x_var = None783__y_var = None784785#786# Rational Maps787#788__rational_maps_initialized = False789__X_coord_rational_map = None790__Y_coord_rational_map = None791792#793# The dual794#795__dual = None796797#798# Kernel Data799#800801__kernel_list = None # list of elements in the kernel802803__kernel_polynomial_list = None # polynomial stored as a little endian list of coefficients804805__kernel_polynomial = None # polynomial with roots at x values for x-coordinate of points in the kernel806807__inner_kernel_polynomial = None # the inner kernel polynomial (ignoring preisomorphism)808809__n = None810811812#813# member variables common to Velu's formula814#815816# we keep track of the 2 torsion and non2torsion separately817__kernel_2tor = None818__kernel_non2tor = None819820# variables used in Velu's formula (as well as Kohel's variant)821__v = None822__w = None823824825#826# member variables specific to Kohel's algorithm.827#828829__psi = None # psi polynomial830__phi = None # phi polynomial831__omega = None # omega polynomial832833834#835# Python Special Functions836#837838def __init__(self, E, kernel, codomain=None, degree=None, model=None, check=True):839r"""840Constructor for EllipticCurveIsogeny class.841842EXAMPLES::843844sage: E = EllipticCurve(GF(2), [0,0,1,0,1])845sage: phi = EllipticCurveIsogeny(E, [1,1])846sage: phi847Isogeny 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 2848849sage: E = EllipticCurve(GF(31), [0,0,0,1,0])850sage: P = E((2,17))851sage: phi = EllipticCurveIsogeny(E, P)852sage: phi853Isogeny 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 31854855sage: E = EllipticCurve('17a1')856sage: phi = EllipticCurveIsogeny(E, [41/3, -55, -1, -1, 1])857sage: phi858Isogeny 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 Field859860sage: E = EllipticCurve('37a1')861sage: triv = EllipticCurveIsogeny(E, E(0))862sage: triv863Isogeny 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 Field864sage: triv.rational_maps()865(x, y)866867sage: E = EllipticCurve('49a3')868sage: R.<X> = QQ[]869sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False)870Isogeny 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 Field871872"""873874if not is_EllipticCurve(E):875raise ValueError, "E parameter must be an EllipticCurve."876877if type(kernel) != type([1,1]) and kernel in E :878# a single point was given, we put it in a list879# the first condition assures that [1,1] is treated as x+1880kernel = [kernel]881882# if the kernel is None and the codomain isn't883# calculate the kernel polynomial884pre_isom = None885post_isom = None886887self.__check = check888889if (kernel is None) and (codomain is not None):890891if (degree is None):892raise ValueError, "If specifying isogeny by domain and codomain, degree parameter must be set."893894# save the domain/codomain: really used now (trac #7096)895old_domain = E896old_codomain = codomain897898(pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree)899900self.__init_algebraic_structs(E)901902algorithm = isogeny_determine_algorithm(E, kernel, codomain, degree, model);903904self.__algorithm = algorithm905906if ("velu"==algorithm):907self.__init_from_kernel_list(kernel)908elif ("kohel"==algorithm):909self.__init_from_kernel_polynomial(kernel, degree)910911self.__compute_E2()912913self.__setup_post_isomorphism(codomain, model)914915if (pre_isom is not None):916self.set_pre_isomorphism(pre_isom)917918if (post_isom is not None):919self.__set_post_isomorphism(old_codomain, post_isom) #(trac #7096)920921# Inheritance house keeping922923self.__perform_inheritance_housekeeping()924925return926927928def __call__(self, P, output_base_ring=None):929r"""930Function that implements the call-ability of elliptic curve931isogenies.932933EXAMPLES::934935sage: E = EllipticCurve(GF(17), [1, 9, 5, 4, 3])936sage: phi = EllipticCurveIsogeny(E, [6,13,1])937sage: phi(E((1,0)))938(15 : 13 : 1)939940sage: E = EllipticCurve(GF(23), [0,0,0,1,0])941sage: phi = EllipticCurveIsogeny(E, E((0,0)))942sage: phi(E((1,5)))943(2 : 0 : 1)944sage: phi(E(15,20), output_base_ring=GF(23^2,'alpha'))945(12 : 1 : 1)946947sage: E = EllipticCurve(QQ, [0,0,0,3,0])948sage: P = E((1,2))949sage: phi = EllipticCurveIsogeny(E, [0,1])950sage: phi(P)951(4 : -4 : 1)952sage: phi(-P)953(4 : 4 : 1)954955sage: E = EllipticCurve(GF(17), [0,-1,0,-3,-1])956sage: Q = E((16,0))957sage: tau = E.isogeny([Q],E)958sage: tau(Q)959(0 : 1 : 0)960961TESTS (trac 10888)::962963sage: K.<th> = NumberField(x^2+3)964sage: E = EllipticCurve(K,[7,0])965sage: phi = E.isogeny(E(0,0))966sage: P = E(-3,4*th)967sage: phi(P)968(-16/3 : 8/9*th : 1)969sage: Q = phi(P)970sage: phihat = phi.dual()971sage: phihat(Q)972(-1/48 : 127/576*th : 1)973974"""975E1 = self.__E1976E_P = P.curve()977change_output_ring = False978979# check that the parent curve of the input point is this curve980# or that the point is on the same curve but whose base ring981# is an extension of this ring982if (E1 != E_P):983if (E1.a_invariants() != E_P.a_invariants()) :984raise ValueError, "P must be on a curve with same Weierstrass model as the domain curve of this isogeny."985change_output_ring = True986987988if(P.is_zero()):989return self.__E2(0)990991(xP, yP) = P.xy()992993if not self.__E1.is_on_curve(xP,yP):994raise InputError, "Input point must be on the domain curve of this isogeny."995996# if there is a pre isomorphism, apply it997if (self.__pre_isomorphism is not None):998temp_xP = self.__prei_x_coord_ratl_map(xP, yP)999temp_yP = self.__prei_y_coord_ratl_map(xP, yP)1000(xP, yP) = (temp_xP, temp_yP)10011002if ("velu" == self.__algorithm):1003outP = self.__compute_via_velu_numeric(xP, yP)1004elif ("kohel" == self.__algorithm):1005outP = self.__compute_via_kohel_numeric(xP,yP)10061007# the intermediate functions return the point at infinity1008# if the input point is in the kernel1009if (outP == self.__intermediate_codomain(0)):1010return self.__E2(0)10111012# if there is a post isomorphism, apply it1013if (self.__post_isomorphism is not None):1014tempX = self.__posti_x_coord_ratl_map(outP[0], outP[1])1015tempY = self.__posti_y_coord_ratl_map(outP[0], outP[1])1016outP = [tempX, tempY]10171018if change_output_ring:1019if (output_base_ring is None):1020output_base_ring = E_P.base_ring()1021outE2 = self.__E2.change_ring(output_base_ring)1022else:1023output_base_ring = self.__E2.base_ring()1024outE2 = self.__E21025outP = self.__E2.point(outP,check=False)10261027R = output_base_ring10281029return outE2.point([R(outP[0]), R(outP[1]), R(1)], check=False)103010311032def __getitem__(self, i):1033self.__initialize_rational_maps()1034if (i < 0) or (i > 2):1035raise IndexError10361037if i == 0:1038return self.__X_coord_rational_map1039else:1040return self.__Y_coord_rational_map10411042def __iter__(self):1043self.__initialize_rational_maps()1044return iter((self.__X_coord_rational_map, self.__Y_coord_rational_map))10451046def __hash__(self):1047r"""1048Function that implements the hash ability of Isogeny objects.10491050This hashes the underlying kernel polynomial so that equal1051isogeny objects have the same hash value. Also, this hashes1052the base field, and domain and codomain curves as well, so1053that isogenies with the same kernel polynomial (over different1054base fields / curves) hash to different values.10551056EXAMPLES::10571058sage: E = EllipticCurve(QQ, [0,0,0,1,0])1059sage: phi_v = EllipticCurveIsogeny(E, E((0,0)))1060sage: phi_k = EllipticCurveIsogeny(E, [0,1])1061sage: phi_k.__hash__() == phi_v.__hash__()1062True1063sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,1])1064sage: phi_p = EllipticCurveIsogeny(E_F17, E_F17([0,1]))1065sage: phi_p.__hash__() == phi_v.__hash__()1066False10671068sage: E = EllipticCurve('49a3')1069sage: R.<X> = QQ[]1070sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False)1071Isogeny 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 Field10721073"""10741075if (self.__this_hash is not None):1076return self.__this_hash10771078ker_poly_list = self.__kernel_polynomial_list10791080if (ker_poly_list is None):1081ker_poly_list = self.__init_kernel_polynomial()10821083this_hash = 010841085for a in ker_poly_list:1086this_hash = this_hash.__xor__(hash(a))10871088this_hash = this_hash.__xor__(hash(self.__E1))1089this_hash = this_hash.__xor__(hash(self.__E2))1090this_hash = this_hash.__xor__(hash(self.__base_field))10911092self.__this_hash = this_hash10931094return self.__this_hash109510961097def __cmp__(self, other):1098r"""1099Function that implements comparisons between isogeny objects.11001101This function works by comparing the underlying kernel1102objects.11031104EXAMPLES::11051106sage: E = EllipticCurve(QQ, [0,0,0,1,0])1107sage: phi_v = EllipticCurveIsogeny(E, E((0,0)))1108sage: phi_k = EllipticCurveIsogeny(E, [0,1])1109sage: phi_k == phi_v1110True1111sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,0])1112sage: phi_p = EllipticCurveIsogeny(E_F17, [0,1])1113sage: phi_p == phi_v1114False1115sage: E = EllipticCurve('11a1')1116sage: phi = E.isogeny(E(5,5))1117sage: psi = E.isogeny(phi.kernel_polynomial())1118sage: phi == psi1119True1120sage: phi.dual() == psi.dual()1121True112211231124"""1125if (not isinstance(other, EllipticCurveIsogeny)):1126return -111271128if (self.__kernel_polynomial is None):1129self.__init_kernel_polynomial()11301131return cmp(self.__kernel_polynomial, other.kernel_polynomial())113211331134def __neg__(self):1135r"""1136Function to implement unary negation (-) operator on1137isogenies. Returns a copy of this isogeny that has been1138negated.11391140EXAMPLES:11411142The following examples inherently exercise this function::11431144sage: E = EllipticCurve(j=GF(17)(0))1145sage: phi = EllipticCurveIsogeny(E, E((-1,0)) )1146sage: negphi = -phi1147sage: phi(E((0,1))) + negphi(E((0,1)))1148(0 : 1 : 0)11491150sage: E = EllipticCurve(j=GF(19)(1728))1151sage: R.<x> = GF(19)[]1152sage: phi = EllipticCurveIsogeny(E, x)1153sage: negphi = -phi1154sage: phi(E((3,7))) + negphi(E((3,12))) == phi(2*E((3,7)))1155True1156sage: negphi(E((18,6)))1157(17 : 0 : 1)11581159sage: R.<x> = QQ[]1160sage: E = EllipticCurve('17a1')1161sage: R.<x> = QQ[]1162sage: f = x - 11/41163sage: phi = EllipticCurveIsogeny(E, f)1164sage: negphi = -phi1165sage: phi.rational_maps()[0] == negphi.rational_maps()[0]1166True1167sage: P = E((7,13))1168sage: phi(P) + negphi(P)1169(0 : 1 : 0)11701171"""1172# save off the kernel lists1173kernel_list = self.__kernel_list1174self.__kernel_list = None11751176output = deepcopy(self)11771178# reset the kernel lists1179output.__kernel_list = copy(kernel_list)1180self.__kernel_list = kernel_list11811182output.switch_sign()1183return output1184118511861187#1188# Sage Special Functions1189#11901191def _repr_(self):1192r"""1193Special sage specific function that implement the1194functionality to display the isogeny self as a string.11951196EXAMPLES::11971198sage: E = EllipticCurve(GF(31), [1,0,1,1,0])1199sage: phi = EllipticCurveIsogeny(E, E((0,0)) )1200sage: phi._repr_()1201'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'12021203sage: E = EllipticCurve(QQ, [1,0,0,1,9])1204sage: phi = EllipticCurveIsogeny(E, [2,1])1205sage: phi._repr_()1206'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'12071208"""1209return 'Isogeny of degree ' + self.__degree.__repr__() + ' from ' + \1210self.__E1.__repr__() + ' to ' + self.__E2.__repr__()121112121213def _latex_(self):1214r"""1215Special sage specific function that implements functionality1216to display an isogeny object as a latex string.12171218This function returns a latex string representing the isogeny1219self as the `x` and `y` coordinate rational functions.12201221EXAMPLES::12221223sage: E = EllipticCurve(QQ, [0,0,0,1,-1])1224sage: phi = EllipticCurveIsogeny(E, E(0))1225sage: phi._latex_()1226'\\left( x , y \\right)'12271228sage: E = EllipticCurve(GF(17), [0,0,0,1,-1])1229sage: R.<X> = GF(17)[]1230sage: phi = EllipticCurveIsogeny(E, X+11)1231sage: phi._latex_()1232'\\left( \\frac{x^{2} + 11 x + 7}{x + 11} , \\frac{x^{2} y + 5 x y + 12 y}{x^{2} + 5 x + 2} \\right)'123312341235"""1236ratl_maps = self.rational_maps()1237return '\\left( %s , %s \\right)' % (ratl_maps[0]._latex_(), ratl_maps[1]._latex_())123812391240###########################1241# Private Common Functions1242###########################12431244# delete the hash value1245def __clear_cached_values(self):1246r"""1247A private function to clear the hash if the codomain has been1248modified by a pre or post isomorphism.12491250EXAMPLES::12511252sage: F = GF(7);1253sage: E = EllipticCurve(j=F(0))1254sage: phi = EllipticCurveIsogeny(E, [E((0,-1)), E((0,1))])1255sage: old_hash = hash(phi)1256sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1257sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,2,-3,4)))1258sage: hash(phi) == old_hash1259False12601261sage: R.<x> = QQ[]1262sage: E = EllipticCurve(QQ, [0,0,0,1,0])1263sage: phi = EllipticCurveIsogeny(E, x)1264sage: old_ratl_maps = phi.rational_maps()1265sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1266sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,0,0,0)))1267sage: old_ratl_maps == phi.rational_maps()1268False1269sage: old_ratl_maps[1] == -phi.rational_maps()[1]1270True12711272sage: F = GF(127); R.<x> = F[]1273sage: E = EllipticCurve(j=F(1728))1274sage: f = x^5 + 43*x^4 + 97*x^3 + 81*x^2 + 42*x + 821275sage: phi = EllipticCurveIsogeny(E, f)1276sage: old_hash = hash(phi)1277sage: old_ratl_maps = phi.rational_maps()1278sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1279sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-13,13,-13,13)))1280sage: old_hash == hash(phi)1281False1282sage: old_ratl_maps == phi.rational_maps()1283False1284sage: phi._EllipticCurveIsogeny__clear_cached_values()12851286"""1287self.__this_hash = None1288self.__rational_maps_initialized = False1289self.__X_coord_rational_map = None1290self.__Y_coord_rational_map = None1291self.__dual129212931294# performs the inheritance house keeping1295def __perform_inheritance_housekeeping(self):1296r"""1297Internal helper function, sets values on the super classes of1298this class.12991300EXAMPLES:13011302The following examples will implicitly exercise this1303function::13041305sage: E = EllipticCurve(GF(43), [2,3,5,7,11])1306sage: R.<x> = GF(43)[]; f = x + 421307sage: phi = EllipticCurveIsogeny(E, f)1308sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping()1309sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1310sage: E2 = phi.codomain()1311sage: post_isom = WeierstrassIsomorphism(E2, (41, 37, 31, 29))1312sage: phi.set_post_isomorphism(post_isom)1313sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain()1314sage: pre_isom = E1pr.isomorphism_to(E)1315sage: phi.set_pre_isomorphism(pre_isom)13161317"""13181319# one of the superclasses uses these fields1320self._domain = self.__E11321self._codomain = self.__E213221323# sets up the parent1324parent = homset.Hom(self.__E1(0).parent(), self.__E2(0).parent())1325Morphism.__init__(self, parent)13261327return132813291330# initializes the base field1331def __init_algebraic_structs(self, E):1332r"""1333An internal function for EllipticCurveIsogeny objects that1334sets up the member variables necessary for algebra.13351336EXAMPLES:13371338The following tests inherently exercise this function::13391340sage: E = EllipticCurve(j=GF(17)(0))1341sage: phi = EllipticCurveIsogeny(E, E((-1,0)))1342sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)13431344sage: E = EllipticCurve(QQ, [0,0,0,1,0])1345sage: phi = EllipticCurveIsogeny(E, E((0,0)))1346sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)13471348sage: F = GF(19); R.<x> = F[]1349sage: E = EllipticCurve(j=GF(19)(0))1350sage: phi = EllipticCurveIsogeny(E, x)1351sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)13521353"""1354self.__E1 = E1355self.__base_field = E.base_ring()13561357poly_ring = self.__poly_ring = PolynomialRing(self.__base_field, ['x','y'])13581359self.__x_var = poly_ring('x')1360self.__y_var = poly_ring('y')13611362self.__intermediate_domain = E13631364return136513661367def __compute_E2(self):1368r"""1369Private function that computes and sets the isogeny codomain.13701371EXAMPLES:13721373These examples inherently exercise this function::13741375sage: E = EllipticCurve(j=GF(7)(1728))1376sage: phi = EllipticCurveIsogeny(E, E((0,0)))1377sage: phi.codomain()1378Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 71379sage: phi._EllipticCurveIsogeny__compute_E2()13801381sage: R.<x> = GF(7)[]1382sage: phi = EllipticCurveIsogeny(E, x)1383sage: phi.codomain()1384Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 71385sage: phi._EllipticCurveIsogeny__compute_E2()13861387"""13881389if ("velu" == self.__algorithm):1390E2 = self.__compute_E2_via_velu()1391elif ("kohel" == self.__algorithm):1392E2 = self.__compute_E2_via_kohel()13931394self.__E2 = E21395self.__intermediate_codomain = E213961397return139813991400# initializes the rational maps fields1401def __initialize_rational_maps(self, precomputed_maps=None):1402r"""1403Private function that computes and initializes the rational1404maps.14051406INPUT:14071408- ``14091410EXAMPLES:14111412The following examples inherently exercise this function::14131414sage: E = EllipticCurve(j=GF(7)(1728))1415sage: phi = EllipticCurveIsogeny(E, E((0,0)))1416sage: phi._EllipticCurveIsogeny__initialize_rational_maps()1417sage: phi.rational_maps()1418((x^2 + 1)/x, (x^2*y - y)/x^2)14191420sage: R.<x> = GF(7)[]1421sage: phi = EllipticCurveIsogeny(E, x)1422sage: phi = EllipticCurveIsogeny(E, x)1423sage: phi.rational_maps()1424((x^2 + 1)/x, (x^2*y - y)/x^2)1425sage: phi._EllipticCurveIsogeny__initialize_rational_maps()14261427sage: E = EllipticCurve([1,2,3,4,5])1428sage: Eshort = E.short_weierstrass_model()1429sage: phi = E.isogeny(E(0), Eshort)1430sage: phiX, phiY = phi.rational_maps()1431sage: phiX(1,2), phiY(1,2)1432(63, 864)1433"""1434if self.__rational_maps_initialized:1435return14361437if precomputed_maps is None:1438if ("velu"==self.__algorithm):1439(X_map, Y_map) = self.__initialize_rational_maps_via_velu()1440if ("kohel"==self.__algorithm):1441(X_map, Y_map) = self.__initialize_rational_maps_via_kohel()1442else:1443X_map, Y_map = precomputed_maps14441445if self.__prei_x_coord_ratl_map is not None:1446prei_X_map = self.__prei_x_coord_ratl_map1447prei_Y_map = self.__prei_y_coord_ratl_map1448X_map, Y_map = X_map.subs(x=prei_X_map, y=prei_Y_map), \1449Y_map.subs(x=prei_X_map, y=prei_Y_map)14501451if self.__posti_x_coord_ratl_map is not None:1452X_map, Y_map = \1453self.__posti_x_coord_ratl_map.subs(x=X_map, y=Y_map), \1454self.__posti_y_coord_ratl_map.subs(x=X_map, y=Y_map)14551456self.__X_coord_rational_map = X_map1457self.__Y_coord_rational_map = Y_map1458self.__rational_maps_initialized = True145914601461def __init_kernel_polynomial(self):1462r"""1463Private function that initializes the kernel polynomial (if1464the algorithm does not take it as a parameter.)14651466EXAMPLES:14671468The following examples inherently exercise this function::14691470sage: E = EllipticCurve(j=GF(7)(1728))1471sage: phi = EllipticCurveIsogeny(E, E((0,0)))1472sage: phi.kernel_polynomial()1473x1474sage: phi._EllipticCurveIsogeny__init_kernel_polynomial()1475[0, 1]14761477"""14781479if (self.__kernel_polynomial_list is not None):1480return self.__kernel_polynomial_list14811482if ("velu" == self.__algorithm):1483ker_poly_list = self.__init_kernel_polynomial_velu()1484else:1485raise InputError, "The kernel polynomial should already be defined!"14861487return ker_poly_list148814891490def __set_pre_isomorphism(self, domain, isomorphism):1491r"""1492Private function to set the pre isomorphism and domain (and1493keep track of the domain of the isogeny.)14941495EXAMPLES::14961497sage: E = EllipticCurve(GF(43), [2,3,5,7,11])1498sage: R.<x> = GF(43)[]; f = x + 421499sage: phi = EllipticCurveIsogeny(E, f)1500sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping()1501sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1502sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain()1503sage: pre_isom = E1pr.isomorphism_to(E)1504sage: phi.set_pre_isomorphism(pre_isom)1505sage: phi._EllipticCurveIsogeny__set_pre_isomorphism(E, WeierstrassIsomorphism(E, (-1, 3, -3, 4)))1506sage: E == phi.domain()1507True15081509"""15101511self.__E1 = domain15121513# set the isomorphism1514self.__pre_isomorphism = isomorphism15151516# calculate the isomorphism as a rational map.15171518(u, r, s, t) = isomorphism.tuple()15191520x = self.__x_var;1521y = self.__y_var;15221523self.__prei_x_coord_ratl_map = (x - r)/u**21524self.__prei_y_coord_ratl_map = (y - s*(x-r) - t)/u**315251526if (self.__kernel_polynomial is not None):1527ker_poly = self.__kernel_polynomial1528ker_poly = ker_poly.subs(x=self.__prei_x_coord_ratl_map)1529kp_lc = ker_poly.univariate_polynomial().leading_coefficient()1530ker_poly = (1/kp_lc)*ker_poly1531self.__kernel_polynomial = ker_poly15321533self.__perform_inheritance_housekeeping()15341535return;153615371538def __set_post_isomorphism(self, codomain, isomorphism):1539r"""1540Private function to set the post isomorphism and codomain (and1541keep track of the codomain of the isogeny.)15421543EXAMPLES:15441545The following examples inherently exercise this function::15461547sage: E = EllipticCurve(j=GF(7)(1728))1548sage: phi = EllipticCurveIsogeny(E, E((0,0)))1549sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism1550sage: E2 = phi.codomain()1551sage: isom = WeierstrassIsomorphism(E2, (-1,2,-3,4))1552sage: phi.set_post_isomorphism(isom)1553sage: phi._EllipticCurveIsogeny__set_post_isomorphism(E2, WeierstrassIsomorphism(phi.codomain(), (1,-2,3,-4)))1554sage: E2 == phi.codomain()1555True15561557"""15581559# set the codomains1560self.__E2 = codomain15611562# set the isomorphism1563self.__post_isomorphism = isomorphism15641565# calculate the isomorphism as a rational map.15661567(u, r, s, t) = isomorphism.tuple()15681569x = self.__x_var;1570y = self.__y_var;15711572self.__posti_x_coord_ratl_map = (x - r)/u**21573self.__posti_y_coord_ratl_map = (y - s*(x-r) - t)/u**315741575self.__perform_inheritance_housekeeping()15761577return;157815791580def __setup_post_isomorphism(self, codomain, model):1581r"""1582Private function to set up the post isomorphism given the1583codomain.15841585EXAMPLES:15861587The following examples inherently exercise this function::15881589sage: E = EllipticCurve(j=GF(7)(1728))1590sage: E2 = EllipticCurve(GF(7), [0,0,0,5,0])1591sage: phi = EllipticCurveIsogeny(E, E((0,0)), E2); phi1592Isogeny 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 71593sage: E3 = EllipticCurve(GF(7), [0,0,0,6,0])1594sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(E3, None)1595sage: phi1596Isogeny 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 715971598sage: R.<x> = QQ[]1599sage: E = EllipticCurve(j=1728)1600sage: f = x^3 - x1601sage: phi = EllipticCurveIsogeny(E, f, model='minimal'); phi1602Isogeny 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 Field16031604sage: phi = EllipticCurveIsogeny(E, f, model=None)1605sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(None, 'minimal')1606sage: 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 Field16081609"""16101611# TODO: add checks to make sure that1612# codomain and model parameters are consistent with the1613# algorithm used.16141615post_isom = None1616newE2 = None16171618oldE2 = self.__E216191620if (model is not None):16211622if (codomain is not None):1623raise ValueError, "Cannot specify a codomain and model flag simultaneously."16241625if ('minimal' == model):16261627if (not is_RationalField(oldE2.base_field())):1628raise ValueError, "specifying minimal for model flag only valid with curves over the rational numbers."16291630newE2 = oldE2.minimal_model()1631post_isom = oldE2.isomorphism_to(newE2)16321633else:1634raise ValueError, "Unknown value of model flag."16351636elif (codomain is not None):1637if (not is_EllipticCurve(codomain)):1638raise ValueError, "Codomain parameter must be an elliptic curve."16391640if (not oldE2.is_isomorphic(codomain)):1641raise ValueError, "Codomain parameter must be isomorphic to computed codomain isogeny"16421643newE2 = codomain1644post_isom = oldE2.isomorphism_to(newE2)16451646if (post_isom is not None):1647self.__set_post_isomorphism(newE2, post_isom)16481649return165016511652###########################1653# Velu's Formula Functions1654###########################16551656#1657# Setup function for Velu's formula1658#16591660def __init_from_kernel_list(self, kernel_gens):1661r"""1662Private function that initializes the isogeny from a list of1663points which generate the kernel (For Velu's formulas.)16641665EXAMPLES:16661667The following example inherently exercises this function::16681669sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1670sage: phi = EllipticCurveIsogeny(E, E((0,0))); phi1671Isogeny 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 71672sage: phi._EllipticCurveIsogeny__init_from_kernel_list([E(0), E((0,0))])16731674"""1675if self.__check :1676for P in kernel_gens:1677if not P.has_finite_order():1678raise ValueError, "The points in the kernel must be of finite order."1679# work around the current implementation of torsion points. When they are done better this could be1680# reduced but it won't speed things up too much.1681kernel_list = Set([self.__E1(0)])1682for P in kernel_gens:1683points_to_add = []1684for j in range(P.order()):1685for Q in kernel_list:1686points_to_add.append(j*P+Q)1687kernel_list += Set(points_to_add)16881689self.__kernel_list = kernel_list.list()1690self.__kernel_2tor = {}1691self.__kernel_non2tor = {}16921693self.__degree = len(kernel_list)16941695self.__sort_kernel_list()16961697return169816991700#1701# Precompute the values in Velu's Formula.1702#1703def __sort_kernel_list(self):1704r"""1705Private function that sorts the list of points in the kernel1706(For Velu's formulas). Sorts out the 2 torsion points, and1707puts them in a dictionary.17081709EXAMPLES:17101711The following example inherently exercises this function::17121713sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1714sage: P = E((4,2))1715sage: phi = EllipticCurveIsogeny(E, P); phi1716Isogeny 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 71717sage: phi._EllipticCurveIsogeny__kernel_2tor = {}1718sage: phi._EllipticCurveIsogeny__kernel_non2tor = {}1719sage: phi._EllipticCurveIsogeny__sort_kernel_list()17201721"""17221723a1,a2,a3,a4,a6 = self.__E1.ainvs()17241725v = 01726w = 017271728for Q in self.__kernel_list:17291730if Q.is_zero():1731continue17321733(xQ,yQ) = Q.xy()17341735gxQ = 3*xQ**2 + 2*a2*xQ + a4 - a1*yQ1736gyQ = -2*yQ - a1*xQ - a317371738uQ = gyQ**217391740# sort torsion points:1741if (2*yQ == -a1*xQ - a3): # Q is 2-torsion1742vQ = gxQ1743self.__kernel_2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ)1744v = v + vQ1745w = w + (uQ + xQ*vQ)1746elif (not self.__kernel_non2tor.has_key(xQ)): # Q is not a 2-torsion1747vQ = 2*gxQ - a1*gyQ1748self.__kernel_non2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ)1749v = v + vQ1750w = w + (uQ + xQ*vQ)17511752self.__v = v1753self.__w = w17541755return175617571758#1759# Velu's formula computing the codomain curve1760#1761def __compute_E2_via_velu(self):1762r"""1763Private function that computes the codomain via Velu's1764formulas.17651766EXAMPLES:17671768The following example inherently exercises this function::17691770sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1771sage: P = E((4,2))1772sage: phi = EllipticCurveIsogeny(E, P);1773sage: phi.codomain()1774Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 71775sage: phi._EllipticCurveIsogeny__compute_E2_via_velu()1776Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 717771778"""1779v = self.__v1780w = self.__w17811782return compute_codomain_formula(self.__E1, v,w)178317841785def __velu_sum_helper(self, Qvalues, a1, a3, x, y):1786r"""1787Private function for Velu's formulas, helper function to help1788perform the summation.17891790EXAMPLES:17911792The following example inherently exercises this function::17931794sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1795sage: P = E((4,2))1796sage: phi = EllipticCurveIsogeny(E, P);1797sage: Q = E((0,0)); phi(Q)1798(0 : 0 : 1)1799sage: phi.rational_maps()1800((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1801(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))18021803sage: E = EllipticCurve(GF(7), [0,0,0,1,0])1804sage: phi = EllipticCurveIsogeny(E, E((0,0)) )1805sage: Qvals = phi._EllipticCurveIsogeny__kernel_2tor[0]1806sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, 5, 5)1807(3, 3)1808sage: R.<x,y> = GF(7)[]1809sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, x, y)1810(1/x, y/x^2)18111812"""1813xQ = Qvalues[0]1814yQ = Qvalues[1]1815gxQ = Qvalues[2]1816gyQ = Qvalues[3]1817vQ = Qvalues[4]1818uQ = Qvalues[5]18191820t1 = x - xQ1821inv_t1 = t1**-11822inv_t1_2 = inv_t1**21823inv_t1_3 = inv_t1_2*inv_t118241825tX = vQ*inv_t1 + uQ*(inv_t1_2)18261827tY0 = uQ*(2*y + a1*x + a3)1828tY1 = vQ*(a1*t1 + y - yQ)1829tY2 = a1*uQ - gxQ*gyQ18301831tY = ( tY0*inv_t1_3 + (tY1 + tY2)*inv_t1_2 )18321833return (tX, tY)183418351836def __compute_via_velu_numeric(self, xP, yP):1837r"""1838Private function that sorts the list of points in the kernel1839(for Velu's formulas). Sorts out the 2 torsion points, and1840puts them in a diction18411842EXAMPLES:18431844The following example inherently exercises this function::18451846sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1847sage: P = E((4,2))1848sage: phi = EllipticCurveIsogeny(E, P);1849sage: Q = E((0,0)); phi(Q)1850(0 : 0 : 1)1851sage: Q = E((-1,0)); phi(Q)1852(0 : 0 : 1)1853sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(0, 0)1854(0, 0)1855sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(-1, 0)1856(0, 0)18571858"""1859# first check if the point is in the kernel1860if ( self.__kernel_2tor.has_key(xP) or self.__kernel_non2tor.has_key(xP) ) :1861return self.__intermediate_codomain(0)18621863outP = self.__compute_via_velu(xP,yP)18641865return outP186618671868def __compute_via_velu(self, xP, yP):1869r"""1870Private function for Velu's formulas, to perform the1871summation.18721873EXAMPLES:18741875The following example inherently exercises this function::18761877sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1878sage: P = E((4,2))1879sage: phi = EllipticCurveIsogeny(E, P);1880sage: Q = E((0,0)); phi(Q)1881(0 : 0 : 1)1882sage: phi.rational_maps()1883((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1884(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))1885sage: phi._EllipticCurveIsogeny__compute_via_velu(0, 0)1886(0, 0)1887sage: R.<x,y> = GF(7)[]1888sage: phi._EllipticCurveIsogeny__compute_via_velu(x, y)1889((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1890(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))18911892"""18931894ker_2tor = self.__kernel_2tor1895ker_non2tor = self.__kernel_non2tor18961897X = 01898Y = 018991900a1 = self.__E1.a1()1901a3 = self.__E1.a3()19021903# next iterate over the 2torsion points of the kernel1904for Qvalues in ker_2tor.itervalues():1905(tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP)1906X = X + tX1907Y = Y + tY19081909for Qvalues in ker_non2tor.itervalues():1910(tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP)1911X = X + tX1912Y = Y + tY19131914X = xP + X1915Y = yP - Y19161917return (X,Y)191819191920def __initialize_rational_maps_via_velu(self):1921r"""1922Private function for Velu's formulas, helper function to initialize the rational maps.19231924EXAMPLES:19251926The following example inherently exercises this function::19271928sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1929sage: P = E((4,2))1930sage: phi = EllipticCurveIsogeny(E, P);1931sage: phi.rational_maps()1932((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1933(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))1934sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_velu()1935((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),1936(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))19371938"""19391940x = self.__x_var1941y = self.__y_var19421943return self.__compute_via_velu(x,y)194419451946def __init_kernel_polynomial_velu(self):1947r"""1948Private function for Velu's formulas, helper function to1949initialize the rational maps.19501951EXAMPLES:19521953The following example inherently exercises this function::19541955sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])1956sage: P = E((4,2))1957sage: phi = EllipticCurveIsogeny(E, P);1958sage: phi.kernel_polynomial()1959x^2 + 2*x + 41960sage: phi._EllipticCurveIsogeny__init_kernel_polynomial_velu()1961[4, 2, 1]19621963"""19641965poly_ring = self.__poly_ring1966x = self.__x_var19671968invX = 019691970if (self.__pre_isomorphism is not None):1971pre_isom = self.__pre_isomorphism1972u = pre_isom.u1973r = pre_isom.r1974invX = (u**2)*x + r1975else:1976invX = x19771978psi = poly_ring(1)19791980for Qvalues in self.__kernel_2tor.itervalues():1981xQ = invX(x=Qvalues[0])1982psi = psi*(x - xQ)19831984for Qvalues in self.__kernel_non2tor.itervalues():1985xQ = invX(x=Qvalues[0])1986psi = psi*(x - xQ)19871988ker_poly_list = psi.univariate_polynomial().list()19891990self.__kernel_polynomial_list = ker_poly_list1991self.__kernel_polynomial = psi19921993return ker_poly_list1994199519961997###################################1998# Kohel's Variant of Velu's Formula1999###################################20002001def __init_from_kernel_polynomial(self, kernel_polynomial, degree=None):2002r"""2003Private function that initializes the isogeny from a kernel2004polynomial.20052006EXAMPLES:20072008These examples inherently exercise this private function::20092010sage: R.<x> = GF(7)[]2011sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])2012sage: phi = EllipticCurveIsogeny(E, x);phi2013Isogeny 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 720142015sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x)20162017sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2018sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi2019Isogeny 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 720202021sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x+6, degree=3)20222023"""20242025poly_ring = self.__poly_ring2026x = self.__x_var20272028E = self.__E120292030if(is_Polynomial(kernel_polynomial)):2031kernel_polynomial = kernel_polynomial.list()20322033n = len(kernel_polynomial)-120342035if kernel_polynomial[-1] != 1:2036raise ValueError, "The kernel polynomial must be monic."20372038self.__kernel_polynomial_list = kernel_polynomial20392040psi = 02041for j in xrange(len(kernel_polynomial)):2042psi = psi*x + kernel_polynomial[n-j]204320442045#2046# Determine if kernel polynomial is entirely a two torsion2047#2048psi_G = two_torsion_part(E, poly_ring, psi, degree);20492050# force this polynomial to be monic:2051psi_G = psi_G/psi_G.univariate_polynomial().leading_coefficient()20522053if (0 != psi_G.degree()): # even degree case20542055psi_quo = poly_ring(psi/psi_G)20562057if (0 != psi_quo.degree()):2058raise NotImplementedError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion."20592060(phi, omega, v, w, n, d) = self.__init_even_kernel_polynomial(E, psi_G)20612062else: # odd degree case20632064(phi, omega, v, w, n, d) = self.__init_odd_kernel_polynomial(E, psi)206520662067#2068# Set up the necessary instance variables2069#20702071self.__kernel_polynomial = psi2072self.__inner_kernel_polynomial = psi20732074self.__n = n2075self.__degree = d20762077self.__psi = psi2078self.__phi = phi2079self.__omega = omega20802081self.__v = v2082self.__w = w20832084return208520862087def __init_even_kernel_polynomial(self, E, psi_G):2088r"""2089Private function that initializes the isogeny from a kernel2090polynomial, for Kohel's algorithm in the even degree case.20912092EXAMPLES:20932094These examples inherently exercise this private function::20952096sage: R.<x> = GF(7)[]2097sage: E = EllipticCurve(GF(7), [-1,0])2098sage: phi = EllipticCurveIsogeny(E, x);phi2099Isogeny 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 721002101sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part2102sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var)2103sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)2104(x^3 - x, x^3*y + x*y, 6, 0, 1, 2)21052106sage: F = GF(2^4, 'alpha'); R.<x> = F[]2107sage: E = EllipticCurve(F, [1,1,0,1,0])2108sage: phi = EllipticCurveIsogeny(E, x); phi2109Isogeny 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^421102111sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var)2112sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)2113(x^3 + x, x^3*y + x^2 + x*y, 1, 0, 1, 2)21142115sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2116sage: R.<x> = GF(7)[]2117sage: f = x^3 + 6*x^2 + 12118sage: phi = EllipticCurveIsogeny(E, f); phi2119Isogeny 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 72120sage: psig = two_torsion_part(E,R,f,None)2121sage: psig = two_torsion_part(E,R,f,None)(phi._EllipticCurveIsogeny__x_var)2122sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)2123(x^7 - 2*x^6 + 2*x^5 - x^4 + 3*x^3 - 2*x^2 - x + 3,2124x^9*y - 3*x^8*y + 2*x^7*y - 3*x^3*y + 2*x^2*y + x*y - y,21251,21266,21273,21284)212921302131"""213221332134#check if the polynomial really divides the two_torsion_polynomial2135if self.__check and E.division_polynomial(2, x=self.__x_var) % psi_G != 0 :2136raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve."21372138n = psi_G.degree()2139d = n+121402141base_field = self.__base_field2142char = base_field.characteristic()21432144x = self.__x_var2145y = self.__y_var21462147a1,a2,a3,a4,a6 = E.ainvs()21482149b2 = E.b2()2150b4 = E.b4()21512152if (1 == n):2153x0 = -psi_G.constant_coefficient()21542155# determine y02156if (2 == char):2157y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt()2158else:2159y0 = -(a1*x0 + a3)/221602161(v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4)21622163phi = (x*psi_G + v)*psi_G2164omega = (y*psi_G**2 - v*(a1*psi_G + (y - y0)))*psi_G21652166elif (3 == n):2167s = psi_G.univariate_polynomial().list()2168s1 = -s[n-1]2169s2 = s[n-2]2170s3 = -s[n-3]21712172psi_G_pr = psi_G.derivative(x)2173psi_G_prpr = psi_G_pr.derivative(x)21742175phi = (psi_G_pr**2) + (-2*psi_G_prpr + (4*x - s1))*psi_G21762177phi_pr = phi.derivative(x)21782179psi_2 = 2*y + a1*x + a321802181omega = (psi_2*(phi_pr*psi_G - phi*psi_G_pr) - (a1*phi + a3*psi_G)*psi_G)/221822183phi = phi*psi_G2184omega = omega*psi_G21852186(v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3)21872188else:2189raise ValueError, "input polynomial must be of degree 1 or 3, not %d" % n21902191return (phi, omega, v, w, n, d)219221932194def __init_odd_kernel_polynomial(self, E, psi):2195r"""2196Private function that initializes the isogeny from a kernel2197polynomial.21982199EXAMPLES:22002201These examples inherently exercise this private function::22022203sage: R.<x> = GF(7)[]2204sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2205sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi2206Isogeny 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 722072208sage: R.<x,y> = GF(7)[]2209sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, x+6)2210(x^3 - 2*x^2 + 3*x + 2, x^3*y - 3*x^2*y + x*y, 2, 6, 1, 3)22112212sage: F = GF(2^4, 'alpha'); R.<x> = F[]2213sage: alpha = F.gen()2214sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1])2215sage: f = x + alpha^2 + 12216sage: phi = EllipticCurveIsogeny(E, f); phi2217Isogeny 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^422182219sage: R.<x,y> = F[]2220sage: f = x + alpha^2 + 12221sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, f)2222(x^3 + (alpha^2 + 1)*x + (alpha^3 + alpha^2 + alpha),2223x^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),2224alpha^2 + alpha + 1,2225alpha^3 + alpha^2 + alpha,22261,22273)22282229sage: E = EllipticCurve(j=-262537412640768000)2230sage: f = (E.isogenies_prime_degree()[0]).kernel_polynomial()2231sage: f.degree()2232812233sage: E.isogeny(kernel=f) # long time (25s on sage.math, 2012)2234Isogeny 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 Field22352236"""2237n = psi.degree()2238d = 2*n + 122392240# check if the polynomial really divides the torsion polynomial :2241if self.__check:2242alpha = psi.parent().quotient(psi).gen()2243if not E.division_polynomial(d, x=alpha).is_zero():2244raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve."22452246x = self.__x_var22472248b2 = E.b2()2249b4 = E.b4()2250b6 = E.b6()22512252psi_coeffs = psi.univariate_polynomial().list()22532254s1 = 0; s2 = 0; s3 = 022552256if (1 <= n):2257s1 = -psi_coeffs[n-1]22582259if (2 <= n):2260s2 = psi_coeffs[n-2]22612262if (3 <= n):2263s3 = -psi_coeffs[n-3]22642265# initializing these allows us to calculate E2.2266(v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n);22672268# initialize the polynomial temporary variables22692270psi_pr = psi.derivative(x)2271psi_prpr = psi_pr.derivative(x)22722273phi = (4*x**3 + b2*x**2 + 2*b4*x + b6)*(psi_pr**2 - psi_prpr*psi) - \2274(6*x**2 + b2*x + b4)*psi_pr*psi + (d*x - 2*s1)*psi**222752276phi_pr = phi.derivative(x)22772278omega = 02279if (2 != self.__base_field.characteristic()):2280omega = self.__compute_omega_fast(E, psi, psi_pr, phi, phi_pr)2281else:2282omega = self.__compute_omega_general(E, psi, psi_pr, phi, phi_pr)22832284return (phi, omega, v, w, n, d)228522862287#2288# This is the fast omega computation that works when characteristic is not 22289#2290def __compute_omega_fast(self, E, psi, psi_pr, phi, phi_pr):2291r"""2292Private function that initializes the omega polynomial (from2293Kohel's formulas) in the case that the characteristic of the2294underlying field is not 2.22952296EXAMPLES:22972298These examples inherently exercise this private function::22992300sage: R.<x> = GF(7)[]2301sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2302sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi2303Isogeny 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 723042305sage: R.<x,y> = GF(7)[]2306sage: psi = phi._EllipticCurveIsogeny__psi2307sage: psi_pr = psi.derivative(x)2308sage: fi = phi._EllipticCurveIsogeny__phi2309sage: fi_pr = fi.derivative(x)2310sage: phi._EllipticCurveIsogeny__compute_omega_fast(E, psi, psi_pr, fi, fi_pr)2311x^3*y - 3*x^2*y + x*y23122313"""23142315a1 = E.a1()2316a3 = E.a3()23172318x = self.__x_var; # 'x'2319y = self.__y_var; # 'y'23202321psi_2 = 2*y + a1*x + a323222323# note, the formula below is correct2324# the formula in Kohel's thesis has some typos2325# notably the first plus sign should be a minus2326# as it is here below.23272328omega = phi_pr*psi*psi_2/2 - phi*psi_pr*psi_2 - \2329(a1*phi + a3*psi**2)*psi/223302331return omega233223332334def __compute_omega_general(self, E, psi, psi_pr, phi, phi_pr):2335r"""2336Private function that initializes the omega polynomial (from2337Kohel's formulas) in the case of general characteristic of the2338underlying field.23392340EXAMPLES:23412342These examples inherently exercise this private function::23432344sage: F = GF(2^4, 'alpha'); R.<x> = F[]2345sage: alpha = F.gen()2346sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1])2347sage: f = x + alpha^2 + 12348sage: phi = EllipticCurveIsogeny(E, f); phi2349Isogeny 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^423502351sage: R.<x,y> = F[]2352sage: psi = phi._EllipticCurveIsogeny__psi2353sage: psi_pr = psi.derivative(x)2354sage: fi = phi._EllipticCurveIsogeny__phi2355sage: fi_pr = fi.derivative(x)2356sage: phi._EllipticCurveIsogeny__compute_omega_general(E, psi, psi_pr, fi, fi_pr)2357x^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)23582359A bug fixed in ticket #7907::23602361sage: F = GF(128,'a')2362sage: a = F.gen()2363sage: E = EllipticCurve([1,0,0,0,(a**6+a**4+a**2+a)])2364sage: x = polygen(F)2365sage: 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)2366sage: E.isogeny(ker)2367Isogeny 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^7236823692370"""23712372a1,a2,a3,a4,a6 = E.ainvs()23732374b2 = E.b2()2375b4 = E.b4()23762377n = psi.degree()2378d = 2*n+123792380x = self.__x_var2381y = self.__y_var23822383psi_2 = 2*y + a1*x + a323842385psi_coeffs = psi.univariate_polynomial().list()23862387if (0 < n):2388s1 = -psi_coeffs[n-1]2389else:2390s1 = 023912392psi_prpr = 02393cur_x_pow = 123942395#2396# Note: we now get the "derivatives" of psi2397# these are not actually the derivatives2398# furthermore, the formulas in Kohel's2399# thesis are wrong, the correct formulas2400# are coded below2401#2402from sage.rings.arith import binomial24032404for j in xrange(0,n-1):2405psi_prpr = psi_prpr + \2406binomial(j+2,2)*psi_coeffs[(j+2)]*cur_x_pow2407cur_x_pow = x*cur_x_pow24082409psi_prprpr = 02410cur_x_pow = 124112412for j in xrange(0,n-2):2413psi_prprpr = psi_prprpr + \2414(3*binomial(j+3,3))*psi_coeffs[(j+3)]*cur_x_pow2415cur_x_pow = x*cur_x_pow241624172418omega = phi_pr*psi*y - phi*psi_pr*psi_2 + \2419((a1*x + a3)*(psi_2**2)*(psi_prpr*psi_pr-psi_prprpr*psi) + \2420(a1*psi_2**2 - 3*(a1*x + a3)*(6*x**2 + b2*x + b4))*psi_prpr*psi + \2421(a1*x**3 + 3*a3*x**2 + (2*a2*a3 - a1*a4)*x + (a3*a4 - 2*a1*a6))*psi_pr**2 + \2422(-(3*a1*x**2 + 6*a3*x + (-a1*a4 + 2*a2*a3)) + \2423(a1*x + a3)*(d*x - 2*s1) )*psi_pr*psi + (a1*s1 + a3*n)*psi**2)*psi24242425return omega242624272428def __compute_via_kohel_numeric(self, xP, yP):2429r"""2430Private function that computes a numeric result of this2431isogeny (via Kohel's formulas.)24322433EXAMPLES:24342435These examples inherently exercise this private function::24362437sage: R.<x> = GF(7)[]2438sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2439sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2440sage: P = E((0,1)); phi(P)2441(2 : 0 : 1)2442sage: P = E((1,1)); phi(P)2443(0 : 1 : 0)2444sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(0, 1)2445(2, 0)2446sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(1, 1)2447(0 : 1 : 0)24482449"""24502451# first check if this is a kernel point2452# to avoid a divide by 0 error later2453if(0 == self.__inner_kernel_polynomial(x=xP)):2454return self.__intermediate_codomain(0)24552456(xP_out, yP_out) = self.__compute_via_kohel(xP,yP)24572458# for some dang reason in some cases2459# when the base_field is a number field2460# xP_out and yP_out do not get evaluated to field elements2461# but rather constant polynomials.2462# So in this case, we do some explicit casting to make sure2463# everything comes out right24642465if is_NumberField(self.__base_field) and (1 < self.__base_field.degree()) :2466xP_out = self.__poly_ring(xP_out).constant_coefficient()2467yP_out = self.__poly_ring(yP_out).constant_coefficient()24682469return (xP_out,yP_out)247024712472def __compute_via_kohel(self, xP, yP):2473r"""2474Private function that applies Kohel's formulas.24752476EXAMPLES:24772478These examples inherently exercise this private function::24792480sage: R.<x> = GF(7)[]2481sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2482sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2483sage: P = E((0,1)); phi(P)2484(2 : 0 : 1)2485sage: phi.rational_maps()2486((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2487(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))2488sage: phi._EllipticCurveIsogeny__compute_via_kohel(0,1)2489(2, 0)2490sage: R.<x,y> = GF(7)[]2491sage: phi._EllipticCurveIsogeny__compute_via_kohel(x,y)2492((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2493(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))24942495"""24962497x = self.__x_var2498y = self.__y_var24992500psi_out = self.__psi(xP,yP)2501phi_out = self.__phi(xP,yP)2502omega_out =self.__omega(xP, yP)25032504psi_inv_out = 1/psi_out25052506psi_inv_sq_out = psi_inv_out**225072508X_out = phi_out*(psi_inv_sq_out)2509Y_out = omega_out*(psi_inv_sq_out*psi_inv_out)25102511return (X_out, Y_out)251225132514def __initialize_rational_maps_via_kohel(self):2515r"""2516Private function that computes and initializes the rational2517maps of this isogeny.25182519EXAMPLES:25202521These examples inherently exercise this private function::25222523sage: R.<x> = GF(7)[]2524sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2525sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2526sage: phi.rational_maps()2527((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2528(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))2529sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_kohel()2530((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),2531(x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))253225332534"""2535x = self.__x_var2536y = self.__y_var25372538(X,Y) = self.__compute_via_kohel(x,y)25392540return (X,Y)254125422543#2544# Kohel's formula computing the codomain curve2545#2546def __compute_E2_via_kohel(self):2547r"""2548Private function that computes and initializes the codomain of2549the isogeny (via Kohel's.)25502551EXAMPLES:25522553These examples inherently exercise this private function::25542555sage: R.<x> = GF(7)[]2556sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])2557sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)2558sage: phi.codomain()2559Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 72560sage: phi._EllipticCurveIsogeny__compute_E2_via_kohel()2561Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 725622563"""25642565v = self.__v2566w = self.__w25672568return compute_codomain_formula(self.__E1, v,w)2569257025712572#2573# public isogeny methods2574#25752576def domain(self):2577r"""2578Returns the domain curve of this isogeny.25792580EXAMPLES::25812582sage: E = EllipticCurve(QQ, [0,0,0,1,0])2583sage: phi = EllipticCurveIsogeny(E, E(0,0))2584sage: phi.domain() == E2585True25862587sage: E = EllipticCurve(GF(31), [1,0,0,1,2])2588sage: phi = EllipticCurveIsogeny(E, [17, 1])2589sage: phi.domain()2590Elliptic Curve defined by y^2 + x*y = x^3 + x + 2 over Finite Field of size 3125912592"""2593return self.__E1259425952596def codomain(self):2597r"""2598Returns the codomain (range) curve of this isogeny.25992600EXAMPLES::26012602sage: E = EllipticCurve(QQ, [0,0,0,1,0])2603sage: phi = EllipticCurveIsogeny(E, E((0,0)))2604sage: phi.codomain()2605Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field26062607sage: E = EllipticCurve(GF(31), [1,0,0,1,2])2608sage: phi = EllipticCurveIsogeny(E, [17, 1])2609sage: phi.codomain()2610Elliptic Curve defined by y^2 + x*y = x^3 + 24*x + 6 over Finite Field of size 3126112612"""2613return self.__E2261426152616def degree(self):2617r"""2618Returns the degree of this isogeny.26192620EXAMPLES::26212622sage: E = EllipticCurve(QQ, [0,0,0,1,0])2623sage: phi = EllipticCurveIsogeny(E, E((0,0)))2624sage: phi.degree()262522626sage: phi = EllipticCurveIsogeny(E, [0,1,0,1])2627sage: phi.degree()2628426292630sage: E = EllipticCurve(GF(31), [1,0,0,1,2])2631sage: phi = EllipticCurveIsogeny(E, [17, 1])2632sage: phi.degree()2633326342635"""2636return self.__degree263726382639def rational_maps(self):2640r"""2641This function returns this isogeny as a pair of rational maps.26422643EXAMPLES::26442645sage: E = EllipticCurve(QQ, [0,2,0,1,-1])2646sage: phi = EllipticCurveIsogeny(E, [1])2647sage: phi.rational_maps()2648(x, y)26492650sage: E = EllipticCurve(GF(17), [0,0,0,3,0])2651sage: phi = EllipticCurveIsogeny(E, E((0,0)))2652sage: phi.rational_maps()2653((x^2 + 3)/x, (x^2*y - 3*y)/x^2)265426552656"""2657if (not self.__rational_maps_initialized):2658self.__initialize_rational_maps()2659return (self.__X_coord_rational_map, self.__Y_coord_rational_map)266026612662def is_separable(self):2663r"""2664This function returns a bool indicating whether or not this2665isogeny is separable.26662667This function always returns ``True`` as currently this class2668only implements separable isogenies.26692670EXAMPLES::26712672sage: E = EllipticCurve(GF(17), [0,0,0,3,0])2673sage: phi = EllipticCurveIsogeny(E, E((0,0)))2674sage: phi.is_separable()2675True26762677sage: E = EllipticCurve('11a1')2678sage: phi = EllipticCurveIsogeny(E, E.torsion_points())2679sage: phi.is_separable()2680True268126822683"""2684return self.__separable268526862687def kernel_polynomial(self):2688r"""2689Returns the kernel polynomial of this isogeny.26902691EXAMPLES::26922693sage: E = EllipticCurve(QQ, [0,0,0,2,0])2694sage: phi = EllipticCurveIsogeny(E, E((0,0)))2695sage: phi.kernel_polynomial()2696x26972698sage: E = EllipticCurve('11a1')2699sage: phi = EllipticCurveIsogeny(E, E.torsion_points())2700sage: phi.kernel_polynomial()2701x^2 - 21*x + 8027022703sage: E = EllipticCurve(GF(17), [1,-1,1,-1,1])2704sage: phi = EllipticCurveIsogeny(E, [1])2705sage: phi.kernel_polynomial()2706127072708sage: E = EllipticCurve(GF(31), [0,0,0,3,0])2709sage: phi = EllipticCurveIsogeny(E, [0,3,0,1])2710sage: phi.kernel_polynomial()2711x^3 + 3*x271227132714"""2715if (self.__kernel_polynomial is None):2716self.__init_kernel_polynomial()27172718return self.__kernel_polynomial.univariate_polynomial()271927202721def set_pre_isomorphism(self, preWI):2722r"""2723Modifies this isogeny object to pre compose with the given2724Weierstrass isomorphism.27252726EXAMPLES::27272728sage: E = EllipticCurve(GF(31), [1,1,0,1,-1])2729sage: R.<x> = GF(31)[]2730sage: f = x^3 + 9*x^2 + x + 302731sage: phi = EllipticCurveIsogeny(E, f)2732sage: Epr = E.short_weierstrass_model()2733sage: isom = Epr.isomorphism_to(E)2734sage: phi.set_pre_isomorphism(isom)2735sage: phi.rational_maps()2736((-6*x^4 - 3*x^3 + 12*x^2 + 10*x - 1)/(x^3 + x - 12),2737(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))2738sage: phi(Epr((0,22)))2739(13 : 21 : 1)2740sage: phi(Epr((3,7)))2741(14 : 17 : 1)27422743sage: E = EllipticCurve(GF(29), [0,0,0,1,0])2744sage: R.<x> = GF(29)[]2745sage: f = x^2 + 52746sage: phi = EllipticCurveIsogeny(E, f)2747sage: phi2748Isogeny 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 292749sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2750sage: inv_isom = WeierstrassIsomorphism(E, (1,-2,5,10))2751sage: Epr = inv_isom.codomain().codomain()2752sage: isom = Epr.isomorphism_to(E)2753sage: phi.set_pre_isomorphism(isom); phi2754Isogeny 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 292755sage: phi(Epr((12,1)))2756(26 : 0 : 1)2757sage: phi(Epr((2,9)))2758(0 : 0 : 1)2759sage: phi(Epr((21,12)))2760(3 : 0 : 1)2761sage: phi.rational_maps()[0]2762(x^5 - 10*x^4 - 6*x^3 - 7*x^2 - x + 3)/(x^4 - 8*x^3 + 5*x^2 - 14*x - 6)27632764sage: E = EllipticCurve('11a1')2765sage: R.<x> = QQ[]2766sage: f = x^2 - 21*x + 802767sage: phi = EllipticCurveIsogeny(E, f); phi2768Isogeny 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 Field2769sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2770sage: Epr = E.short_weierstrass_model()2771sage: isom = Epr.isomorphism_to(E)2772sage: phi.set_pre_isomorphism(isom)2773sage: phi2774Isogeny 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 Field2775sage: phi(Epr((168,1188)))2776(0 : 1 : 0)27772778"""27792780WIdom = preWI.domain().codomain()2781WIcod = preWI.codomain().codomain()27822783if (type(preWI) != WeierstrassIsomorphism):2784raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism."27852786if (self.__E1 != WIcod):2787raise ValueError, "Invalid parameter: isomorphism must have codomain curve equal to this isogenies' domain."27882789if (self.__pre_isomorphism is None):2790isom = preWI2791domain = WIdom2792else:2793isom = self.__pre_isomorphism*preWI2794domain = WIdom27952796self.__clear_cached_values()27972798self.__set_pre_isomorphism(domain, isom)27992800return280128022803def set_post_isomorphism(self, postWI):2804r"""2805Modifies this isogeny object to post compose with the given2806Weierstrass isomorphism.28072808EXAMPLES::28092810sage: E = EllipticCurve(j=GF(31)(0))2811sage: R.<x> = GF(31)[]2812sage: phi = EllipticCurveIsogeny(E, x+18)2813sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2814sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (6,8,10,12)))2815sage: phi2816Isogeny 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 3128172818sage: E = EllipticCurve(j=GF(47)(0))2819sage: f = E.torsion_polynomial(3)/32820sage: phi = EllipticCurveIsogeny(E, f)2821sage: E2 = phi.codomain()2822sage: post_isom = E2.isomorphism_to(E)2823sage: phi.set_post_isomorphism(post_isom)2824sage: phi.rational_maps() == E.multiplication_by_m(3)2825False2826sage: phi.switch_sign()2827sage: phi.rational_maps() == E.multiplication_by_m(3)2828True28292830Example over a number field::28312832sage: R.<x> = QQ[]2833sage: K.<a> = NumberField(x^2 + 2)2834sage: E = EllipticCurve(j=K(1728))2835sage: ker_list = E.torsion_points()2836sage: phi = EllipticCurveIsogeny(E, ker_list)2837sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2838sage: post_isom = WeierstrassIsomorphism(phi.codomain(), (a,2,3,5))2839sage: phi2840Isogeny 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 + 228412842"""28432844WIdom = postWI.domain().codomain()2845WIcod = postWI.codomain().codomain()28462847if (type(postWI) != WeierstrassIsomorphism):2848raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism."28492850if (self.__E2 != WIdom):2851raise ValueError, "Invalid parameter: isomorphism must have domain curve equal to this isogenies' codomain."28522853if (self.__post_isomorphism is None):2854isom = postWI2855codomain = WIcod2856else:2857isom = postWI*self.__post_isomorphism2858codomain = WIcod28592860self.__clear_cached_values()28612862self.__set_post_isomorphism(codomain, isom)28632864return286528662867def get_pre_isomorphism(self):2868r"""2869Returns the pre-isomorphism of this isogeny. If there has2870been no pre-isomorphism set, this returns ``None``.28712872EXAMPLES::28732874sage: E = EllipticCurve(GF(31), [1,1,0,1,-1])2875sage: R.<x> = GF(31)[]2876sage: f = x^3 + 9*x^2 + x + 302877sage: phi = EllipticCurveIsogeny(E, f)2878sage: phi.get_post_isomorphism()2879sage: Epr = E.short_weierstrass_model()2880sage: isom = Epr.isomorphism_to(E)2881sage: phi.set_pre_isomorphism(isom)2882sage: isom == phi.get_pre_isomorphism()2883True28842885sage: E = EllipticCurve(GF(83), [1,0,1,1,0])2886sage: R.<x> = GF(83)[]; f = x+242887sage: phi = EllipticCurveIsogeny(E, f)2888sage: E2 = phi.codomain()2889sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2)2890sage: phi2.get_pre_isomorphism()2891Generic morphism:2892From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 832893To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 832894Via: (u,r,s,t) = (1, 76, 41, 3)2895289628972898"""2899return self.__pre_isomorphism290029012902def get_post_isomorphism(self):2903r"""2904Returns the post-isomorphism of this isogeny. If there has2905been no post-isomorphism set, this returns ``None``.29062907EXAMPLES::29082909sage: E = EllipticCurve(j=GF(31)(0))2910sage: R.<x> = GF(31)[]2911sage: phi = EllipticCurveIsogeny(E, x+18)2912sage: phi.get_post_isomorphism()2913sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism2914sage: isom = WeierstrassIsomorphism(phi.codomain(), (6,8,10,12))2915sage: phi.set_post_isomorphism(isom)2916sage: isom == phi.get_post_isomorphism()2917True29182919sage: E = EllipticCurve(GF(83), [1,0,1,1,0])2920sage: R.<x> = GF(83)[]; f = x+242921sage: phi = EllipticCurveIsogeny(E, f)2922sage: E2 = phi.codomain()2923sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2)2924sage: phi2.get_post_isomorphism()2925Generic morphism:2926From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 832927To: 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 832928Via: (u,r,s,t) = (1, 7, 42, 80)29292930"""2931return self.__post_isomorphism293229332934def switch_sign(self):2935r"""2936This function composes the isogeny with `[-1]` (flipping the2937coefficient between +/-1 on the `y` coordinate rational map).29382939EXAMPLES::29402941sage: E = EllipticCurve(GF(23), [0,0,0,1,0])2942sage: f = E.torsion_polynomial(3)/32943sage: phi = EllipticCurveIsogeny(E, f, E)2944sage: phi.rational_maps() == E.multiplication_by_m(3)2945False2946sage: phi.switch_sign()2947sage: phi.rational_maps() == E.multiplication_by_m(3)2948True29492950sage: E = EllipticCurve(GF(17), [-2, 3, -5, 7, -11])2951sage: R.<x> = GF(17)[]2952sage: f = x+62953sage: phi = EllipticCurveIsogeny(E, f)2954sage: phi2955Isogeny 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 172956sage: phi.rational_maps()2957((x^2 + 6*x + 4)/(x + 6), (x^2*y - 5*x*y + 8*x - 2*y)/(x^2 - 5*x + 2))2958sage: phi.switch_sign()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),2963(2*x^3 - x^2*y - 5*x^2 + 5*x*y - 4*x + 2*y + 7)/(x^2 - 5*x + 2))29642965sage: E = EllipticCurve('11a1')2966sage: R.<x> = QQ[]2967sage: f = x^2 - 21*x + 802968sage: phi = EllipticCurveIsogeny(E, f)2969sage: (xmap1, ymap1) = phi.rational_maps()2970sage: phi.switch_sign()2971sage: (xmap2, ymap2) = phi.rational_maps()2972sage: xmap1 == xmap22973True2974sage: ymap1 == -ymap2 - E.a1()*xmap2 - E.a3()2975True29762977sage: K.<a> = NumberField(x^2 + 1)2978sage: E = EllipticCurve(K, [0,0,0,1,0])2979sage: R.<x> = K[]2980sage: phi = EllipticCurveIsogeny(E, x-a)2981sage: phi.rational_maps()2982((x^2 + (-a)*x - 2)/(x + (-a)), (x^2*y + (-2*a)*x*y + y)/(x^2 + (-2*a)*x - 1))2983sage: phi.switch_sign()2984sage: phi.rational_maps()2985((x^2 + (-a)*x - 2)/(x + (-a)), (-x^2*y + (2*a)*x*y - y)/(x^2 + (-2*a)*x - 1))29862987"""2988self.set_post_isomorphism(WeierstrassIsomorphism(self.__E2, (-1,0,-self.__E2.a1(),-self.__E2.a3())))29892990def is_normalized(self, via_formal=True, check_by_pullback=True):2991r"""2992Returns ``True`` if this isogeny is normalized. An isogeny2993`\varphi\colon E\to E_2` between two given Weierstrass2994equations is said to be normalized if the constant `c` is `1`2995in `\varphi*(\omega_2) = c\cdot\omega`, where `\omega` and2996`omega_2` are the invariant differentials on `E` and `E_2`2997corresponding to the given equation.29982999INPUT:30003001- ``via_formal`` - (default: ``True``) If ``True`` it simply checks if3002the leading term of the formal series is 1. Otherwise3003it uses a deprecated algorithm involving the second3004optional argument.30053006- ``check_by_pullback`` - (default:``True``) Deprecated.30073008EXAMPLES::30093010sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism3011sage: E = EllipticCurve(GF(7), [0,0,0,1,0])3012sage: R.<x> = GF(7)[]3013sage: phi = EllipticCurveIsogeny(E, x)3014sage: phi.is_normalized()3015True3016sage: isom = WeierstrassIsomorphism(phi.codomain(), (3, 0, 0, 0))3017sage: phi.set_post_isomorphism(isom)3018sage: phi.is_normalized()3019False3020sage: isom = WeierstrassIsomorphism(phi.codomain(), (5, 0, 0, 0))3021sage: phi.set_post_isomorphism(isom)3022sage: phi.is_normalized()3023True3024sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))3025sage: phi.set_post_isomorphism(isom)3026sage: phi.is_normalized()3027True30283029sage: F = GF(2^5, 'alpha'); alpha = F.gen()3030sage: E = EllipticCurve(F, [1,0,1,1,1])3031sage: R.<x> = F[]3032sage: phi = EllipticCurveIsogeny(E, x+1)3033sage: isom = WeierstrassIsomorphism(phi.codomain(), (alpha, 0, 0, 0))3034sage: phi.is_normalized()3035True3036sage: phi.set_post_isomorphism(isom)3037sage: phi.is_normalized()3038False3039sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/alpha, 0, 0, 0))3040sage: phi.set_post_isomorphism(isom)3041sage: phi.is_normalized()3042True3043sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))3044sage: phi.set_post_isomorphism(isom)3045sage: phi.is_normalized()3046True30473048sage: E = EllipticCurve('11a1')3049sage: R.<x> = QQ[]3050sage: f = x^3 - x^2 - 10*x - 79/43051sage: phi = EllipticCurveIsogeny(E, f)3052sage: isom = WeierstrassIsomorphism(phi.codomain(), (2, 0, 0, 0))3053sage: phi.is_normalized()3054True3055sage: phi.set_post_isomorphism(isom)3056sage: phi.is_normalized()3057False3058sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/2, 0, 0, 0))3059sage: phi.set_post_isomorphism(isom)3060sage: phi.is_normalized()3061True3062sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))3063sage: phi.set_post_isomorphism(isom)3064sage: phi.is_normalized()3065True30663067"""3068# easy algorithm using the formal expansion.3069if via_formal:3070phi_formal = self.formal(prec=5)3071return phi_formal[1] == 130723073# this is the old algorithm. it should be deprecated.3074check_prepost_isomorphism = False30753076f_normalized = True30773078if (check_by_pullback):30793080(Xmap, Ymap) = self.rational_maps()30813082E1 = self.__E13083E2 = self.__E230843085a1 = E1.a1()3086a3 = E1.a3()30873088a1pr = E2.a1()3089a3pr = E2.a3()30903091x = self.__x_var3092y = self.__y_var30933094Xmap_pr = Xmap.derivative(x)30953096domain_inv_diff = 1/(2*y + a1*x + a3)3097codomain_inv_diff = Xmap_pr/(2*Ymap + a1pr*Xmap + a3pr)30983099inv_diff_quo = domain_inv_diff/codomain_inv_diff31003101if (1 == inv_diff_quo):3102f_normalized = True3103else:3104# For some reason, in certain cases, when the isogeny3105# is pre or post composed with a translation the3106# resulting rational functions are too complicated for3107# sage to simplify down to a constant in this case, we3108# do some cheating by checking if the post-composition3109# by isogeny has a non 1 scaling factor3110if ( inv_diff_quo.numerator().is_constant() and (inv_diff_quo.denominator().is_constant) ):3111f_normalized = False3112else:3113check_prepost_isomorphism = True3114else:3115check_prepost_isomorphism = True31163117# If we skip checking by the pullback of the invariant3118# differential OR if that was inconclusive We explicitly check3119# if there is a post isomorphism and if it has a non 1 scaling3120# factor or if it is a just a translation. NOTE: This only3121# works because we are using algorithms for calculating the3122# isogenies that calculate a separable normalized isogeny, if3123# this changes, this check will no longer be correct.3124#3125if (check_prepost_isomorphism):3126post_isom = self.__post_isomorphism3127if (post_isom is not None):3128if (1 == self.__base_field(post_isom.u)):3129f_post_normalized = True3130else:3131f_post_normalized = False3132else:3133f_post_normalized = True31343135pre_isom = self.__pre_isomorphism3136if (pre_isom is not None):3137if (1 == self.__base_field(pre_isom.u)):3138f_pre_normalized = True3139else:3140f_pre_normalized = False3141else:3142f_pre_normalized = True31433144f_normalized = f_pre_normalized and f_post_normalized31453146return f_normalized31473148def dual(self):3149r"""3150Computes and returns the dual isogeny of this isogeny. If3151`\varphi\colon E \to E_2` is the given isogeny, then the dual3152is by definition the unique isogeny `\hat\varphi\colon E_2\to3153E` such that the compositions `\hat\varphi\circ\varphi` and3154`\varphi\circ\hat\varphi` are the multiplication `[n]` by the3155degree of `\varphi` on `E` and `E_2` respectively.31563157EXAMPLES::31583159sage: E = EllipticCurve('11a1')3160sage: R.<x> = QQ[]3161sage: f = x^2 - 21*x + 803162sage: phi = EllipticCurveIsogeny(E, f)3163sage: phi_hat = phi.dual()3164sage: phi_hat.domain() == phi.codomain()3165True3166sage: phi_hat.codomain() == phi.domain()3167True3168sage: (X, Y) = phi.rational_maps()3169sage: (Xhat, Yhat) = phi_hat.rational_maps()3170sage: Xm = Xhat.subs(x=X, y=Y)3171sage: Ym = Yhat.subs(x=X, y=Y)3172sage: (Xm, Ym) == E.multiplication_by_m(5)3173True31743175sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3176sage: R.<x> = GF(37)[]3177sage: f = x^3 + x^2 + 28*x + 333178sage: phi = EllipticCurveIsogeny(E, f)3179sage: phi_hat = phi.dual()3180sage: phi_hat.codomain() == phi.domain()3181True3182sage: phi_hat.domain() == phi.codomain()3183True3184sage: (X, Y) = phi.rational_maps()3185sage: (Xhat, Yhat) = phi_hat.rational_maps()3186sage: Xm = Xhat.subs(x=X, y=Y)3187sage: Ym = Yhat.subs(x=X, y=Y)3188sage: (Xm, Ym) == E.multiplication_by_m(7)3189True31903191sage: E = EllipticCurve(GF(31), [0,0,0,1,8])3192sage: R.<x> = GF(31)[]3193sage: f = x^2 + 17*x + 293194sage: phi = EllipticCurveIsogeny(E, f)3195sage: phi_hat = phi.dual()3196sage: phi_hat.codomain() == phi.domain()3197True3198sage: phi_hat.domain() == phi.codomain()3199True3200sage: (X, Y) = phi.rational_maps()3201sage: (Xhat, Yhat) = phi_hat.rational_maps()3202sage: Xm = Xhat.subs(x=X, y=Y)3203sage: Ym = Yhat.subs(x=X, y=Y)3204sage: (Xm, Ym) == E.multiplication_by_m(5)3205True32063207Test (for trac ticket 7096)::32083209sage: E = EllipticCurve('11a1')3210sage: phi = E.isogeny(E(5,5))3211sage: phi.dual().dual() == phi3212True32133214sage: k = GF(103)3215sage: E = EllipticCurve(k,[11,11])3216sage: phi = E.isogeny(E(4,4))3217sage: phi3218Isogeny 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 1033219sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism3220sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(),(5,0,1,2)))3221sage: phi.dual().dual() == phi3222True32233224sage: E = EllipticCurve(GF(103),[1,0,0,1,-1])3225sage: phi = E.isogeny(E(60,85))3226sage: phi.dual()3227Isogeny 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 10332283229"""32303231if (self.__base_field.characteristic() in [2,3]):3232raise NotImplemented32333234if (self.__dual is not None):3235return self.__dual32363237# trac 70963238(E1, E2pr, pre_isom, post_isom) = compute_intermediate_curves(self.codomain(), self.domain())32393240F = self.__base_field32413242d = self.__degree32433244# trac 70963245if F(d) == 0:3246raise NotImplementedError, "The dual isogeny is not separable, but only separable isogenies are implemented so far"32473248# trac 70963249# this should take care of the case when the isogeny is not normalized.3250u = self.formal(prec=5)[1]3251isom = WeierstrassIsomorphism(E2pr, (u/F(d), 0, 0, 0))32523253E2 = isom.codomain().codomain()32543255pre_isom = self.__E2.isomorphism_to(E1)3256post_isom = E2.isomorphism_to(self.__E1)32573258phi_hat = EllipticCurveIsogeny(E1, None, E2, d)32593260phi_hat.set_pre_isomorphism(pre_isom)3261phi_hat.set_post_isomorphism(post_isom)3262phi_hat.__perform_inheritance_housekeeping()32633264assert phi_hat.codomain() == self.domain()32653266# trac 7096 : this adjust a posteriori the automorphism3267# on the codomain of the dual isogeny.3268# we used _a_ Weierstrass isomorphism to get to the original3269# curve, but we may have to change it my an automorphism.3270# we impose that the composition has the degree3271# as a leading coefficient in the formal expansion.32723273phi_sc = self.formal(prec=5)[1]3274phihat_sc = phi_hat.formal(prec=5)[1]32753276sc = phi_sc * phihat_sc/F(d)32773278if sc != 1:3279auts = phi_hat.codomain().automorphsims()3280aut = [a for a in auts if a.u == sc]3281if len(aut) != 1:3282raise ValueError, "There is a bug in dual()."3283phi_hat.set_post_isomorphism(a[0])32843285self.__dual = phi_hat32863287return phi_hat32883289def formal(self,prec=20):3290r"""3291Computes the formal isogeny as a power series in the variable3292`t=-x/y` on the domain curve.32933294INPUT:32953296- ``prec`` - (default = 20), the precision with which the computations3297in the formal group are carried out.32983299EXAMPLES::33003301sage: E = EllipticCurve(GF(13),[1,7])3302sage: phi = E.isogeny(E(10,4))3303sage: phi.formal()3304t + 12*t^13 + 2*t^17 + 8*t^19 + 2*t^21 + O(t^23)33053306sage: E = EllipticCurve([0,1])3307sage: phi = E.isogeny(E(2,3))3308sage: phi.formal(prec=10)3309t + 54*t^5 + 255*t^7 + 2430*t^9 + 19278*t^11 + O(t^13)33103311sage: E = EllipticCurve('11a2')3312sage: R.<x> = QQ[]3313sage: phi = E.isogeny(x^2 + 101*x + 12751/5)3314sage: phi.formal(prec=7)3315t - 2724/5*t^5 + 209046/5*t^7 - 4767/5*t^8 + 29200946/5*t^9 + O(t^10)331633173318"""3319Eh = self.__E1.formal()3320f, g = self.rational_maps()3321xh = Eh.x(prec=prec)3322yh = Eh.y(prec=prec)3323fh = f(xh,yh)3324gh = g(xh,yh)3325return -fh/gh33263327#3328# Overload Morphism methods that we want to3329#33303331def _composition_(self, right, homset):3332r"""3333Composition operator function inherited from morphism class.33343335EXAMPLES::33363337sage: E = EllipticCurve(j=GF(7)(0))3338sage: phi = EllipticCurveIsogeny(E, [E(0), E((0,1)), E((0,-1))])3339sage: phi._composition_(phi, phi.parent())3340Traceback (most recent call last):3341...3342NotImplementedError33433344The following should test that :meth:`_composition_` is called3345upon a product. However phi is currently improperly3346constructed (see :trac:`12880`), which triggers an assertion3347failure before the actual call ::33483349sage: phi*phi3350Traceback (most recent call last):3351...3352TypeError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 is not in Category of hom sets in Category of Schemes33533354Here would be the desired output::33553356sage: phi*phi # not tested3357Traceback (most recent call last):3358...3359NotImplementedError3360"""3361raise NotImplementedError336233633364def is_injective(self):3365r"""3366Method inherited from the morphism class. Returns ``True`` if3367and only if this isogeny has trivial kernel.33683369EXAMPLES::33703371sage: E = EllipticCurve('11a1')3372sage: R.<x> = QQ[]3373sage: f = x^2 + x - 29/53374sage: phi = EllipticCurveIsogeny(E, f)3375sage: phi.is_injective()3376False3377sage: phi = EllipticCurveIsogeny(E, R(1))3378sage: phi.is_injective()3379True33803381sage: F = GF(7)3382sage: E = EllipticCurve(j=F(0))3383sage: phi = EllipticCurveIsogeny(E, [ E((0,-1)), E((0,1))])3384sage: phi.is_injective()3385False3386sage: phi = EllipticCurveIsogeny(E, E(0))3387sage: phi.is_injective()3388True33893390"""33913392if (1 < self.__degree): return False3393return True339433953396def is_surjective(self):3397r"""3398For elliptic curve isogenies, always returns ``True`` (as a3399non-constant map of algebraic curves must be surjective).34003401EXAMPLES::34023403sage: E = EllipticCurve('11a1')3404sage: R.<x> = QQ[]3405sage: f = x^2 + x - 29/53406sage: phi = EllipticCurveIsogeny(E, f)3407sage: phi.is_surjective()3408True34093410sage: E = EllipticCurve(GF(7), [0,0,0,1,0])3411sage: phi = EllipticCurveIsogeny(E, E((0,0)))3412sage: phi.is_surjective()3413True34143415sage: F = GF(2^5, 'omega')3416sage: E = EllipticCurve(j=F(0))3417sage: R.<x> = F[]3418sage: phi = EllipticCurveIsogeny(E, x)3419sage: phi.is_surjective()3420True34213422"""3423return True34243425def is_zero(self):3426r"""3427Member function inherited from morphism class.34283429EXAMPLES::34303431sage: E = EllipticCurve(j=GF(7)(0))3432sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3433sage: phi.is_zero()3434Traceback (most recent call last):3435...3436NotImplementedError3437"""3438raise NotImplementedError34393440def post_compose(self, left):3441r"""3442Member function inherited from morphism class.34433444EXAMPLES::34453446sage: E = EllipticCurve(j=GF(7)(0))3447sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3448sage: phi.post_compose(phi)3449Traceback (most recent call last):3450...3451NotImplementedError34523453"""3454raise NotImplementedError345534563457def pre_compose(self, right):3458r"""3459Member function inherited from morphism class.34603461EXAMPLES::34623463sage: E = EllipticCurve(j=GF(7)(0))3464sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3465sage: phi.pre_compose(phi)3466Traceback (most recent call last):3467...3468NotImplementedError34693470"""3471raise NotImplementedError347234733474def n(self):3475r"""3476Numerical Approximation inherited from Map (through morphism),3477nonsensical for isogenies.34783479EXAMPLES::34803481sage: E = EllipticCurve(j=GF(7)(0))3482sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])3483sage: phi.n()3484Traceback (most recent call last):3485...3486NotImplementedError: Numerical approximations do not make sense for Elliptic Curve Isogenies34873488"""3489raise NotImplementedError, "Numerical approximations do not make sense for Elliptic Curve Isogenies"34903491# no longer needed (trac 7096)3492# def starks_find_r_and_t(T, Z):34933494def compute_isogeny_starks(E1, E2, ell):3495r"""3496Computes the degree ``ell`` isogeny between ``E1`` and ``E2`` via3497Stark's algorithm. There must be a degree ``ell``, separable,3498normalized cyclic isogeny from ``E1`` to ``E2``.34993500INPUT:35013502- ``E1`` - an elliptic curve in short Weierstrass form.3503- ``E2`` - an elliptic curve in short Weierstrass form.3504- ``ell`` - the degree of the isogeny from E1 to E2.35053506OUTPUT:35073508polynomial -- over the field of definition of ``E1``, ``E2``, that is the3509kernel polynomial of the isogeny from ``E1`` to ``E2``.35103511ALGORITHM:35123513This function uses Starks Algorithm as presented in section 6.2 of3514[BMSS].35153516.. note::35173518As published there, the algorithm is incorrect, and a correct3519version (with slightly different notation) can be found in3520[M09]. The algorithm originates in [S72]35213522REFERENCES:35233524- [BMSS] Boston, Morain, Salvy, Schost, "Fast Algorithms for Isogenies."3525- [M09] Moody, "The Diffie-Hellman Problem and Generalization of Verheul's Theorem"3526- [S72] Stark, "Class-numbers of complex quadratic fields."35273528EXAMPLES::35293530sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks, compute_sequence_of_maps35313532sage: E = EllipticCurve(GF(97), [1,0,1,1,0])3533sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 213534sage: phi = EllipticCurveIsogeny(E, f)3535sage: E2 = phi.codomain()3536sage: (isom1, isom2, E1pr, E2pr, ker_poly) = compute_sequence_of_maps(E, E2, 11)3537sage: compute_isogeny_starks(E1pr, E2pr, 11)3538x^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 + 835393540sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3541sage: R.<x> = GF(37)[]3542sage: f = (x + 14) * (x + 30)3543sage: phi = EllipticCurveIsogeny(E, f)3544sage: E2 = phi.codomain()3545sage: compute_isogeny_starks(E, E2, 5)3546x^4 + 14*x^3 + x^2 + 34*x + 213547sage: f**23548x^4 + 14*x^3 + x^2 + 34*x + 2135493550sage: E = EllipticCurve(QQ, [0,0,0,1,0])3551sage: R.<x> = QQ[]3552sage: f = x3553sage: phi = EllipticCurveIsogeny(E, f)3554sage: E2 = phi.codomain()3555sage: compute_isogeny_starks(E, E2, 2)3556x35573558"""35593560K = E1.base_field()3561R = PolynomialRing(K, 'x')3562x = R.gen()35633564wp1 = E1.weierstrass_p(prec=4*ell+4) #BMSS claim 2*ell is enough, but it is not M093565wp2 = E2.weierstrass_p(prec=4*ell+4)35663567# viewed them as power series in Z = z^23568S = LaurentSeriesRing(K, 'Z')3569Z = S.gen()3570pe1 = 1/Z3571pe2 = 1/Z3572for i in xrange(2*ell+1):3573pe1 += wp1[2*i] * Z**i3574pe2 += wp2[2*i] * Z**i3575pe1 = pe1.add_bigoh(2*ell+2)3576pe2 = pe2.add_bigoh(2*ell+2)35773578#print 'wps = ',pe13579#print 'wps2 = ',pe235803581n = 13582q = [R(1), R(0)]3583#p = [R(0), R(1)]3584T = pe235853586while ( q[n].degree() < (ell-1) ):3587#print 'n=', n35883589n += 13590a_n = 03591r = -T.valuation()3592while (0 <= r):3593t_r = T[-r]3594#print ' r=',r3595#print ' t_r=',t_r3596#print ' T=',T3597a_n = a_n + t_r * x**r3598T = T - t_r*pe1**r3599r = -T.valuation()360036013602q_n = a_n*q[n-1] + q[n-2]3603q.append(q_n)3604#p_n = a_n*p[n-1] + q[n-2]3605#p.append(p_n)36063607if (n == ell+1 or T == 0):3608if (T == 0 or T.valuation()<2):3609raise ValueError("The two curves are not linked by a cyclic normalized isogeny of degree %s" % ell)3610#print 'breaks here'3611break36123613T = 1/T3614#print ' a_n=', a_n3615#print ' q_n=', q_n3616#print ' p_n=', p_n3617#print ' T = ', T36183619qn = q[n]3620#pn= p[n]3621#print 'final T = ', T3622#print ' f =', pn/qn36233624qn = (1/qn.leading_coefficient())*qn3625#pn = (1/qn.leading_coefficient())*pn36263627return qn36283629def split_kernel_polynomial(E1, ker_poly, ell):3630r"""3631Internal helper function for ``compute_isogeny_kernel_polynomial``.36323633Given a full kernel polynomial (where two torsion `x`-coordinates3634are roots of multiplicity 1, and all other roots have multiplicity36352.) of degree `\ell-1`, returns the maximum separable divisor.3636(i.e. the kernel polynomial with roots of multiplicity at most 1).36373638EXAMPLES:36393640The following example implicitly exercises this function::36413642sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3643sage: R.<x> = GF(37)[]3644sage: f = (x + 10) * (x + 12) * (x + 16)3645sage: phi = EllipticCurveIsogeny(E, f)3646sage: E2 = phi.codomain()3647sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks3648sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import split_kernel_polynomial3649sage: ker_poly = compute_isogeny_starks(E, E2, 7); ker_poly3650x^6 + 2*x^5 + 20*x^4 + 11*x^3 + 36*x^2 + 35*x + 163651sage: split_kernel_polynomial(E, ker_poly, 7)3652x^3 + x^2 + 28*x + 3336533654"""36553656poly_ring = ker_poly.parent()36573658z = poly_ring.gen(0)36593660ker_poly_2tor = two_torsion_part(E1, poly_ring, ker_poly, ell)3661ker_poly_quo = poly_ring(ker_poly/ker_poly_2tor)3662ker_poly_quo_sqrt = ker_poly_quo.gcd(ker_poly_quo.derivative(z))3663ker_poly = ker_poly_2tor*ker_poly_quo_sqrt3664ker_poly = (1/ker_poly.leading_coefficient())*ker_poly36653666return ker_poly366736683669def compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm="starks"):3670r"""3671Computes the kernel polynomial of the degree ``ell`` isogeny3672between ``E1`` and ``E2``. There must be a degree ``ell``,3673cyclic, separable, normalized isogeny from ``E1`` to ``E2``.36743675INPUT:36763677- ``E1`` - an elliptic curve in short Weierstrass form.36783679- ``E2`` - an elliptic curve in short Weierstrass form.36803681- ``ell`` - the degree of the isogeny from ``E1`` to ``E2``.36823683- ``algorithm`` - currently only ``starks`` (default) is implemented.36843685OUTPUT:36863687polynomial -- over the field of definition of ``E1``, ``E2``, that is the3688kernel polynomial of the isogeny from ``E1`` to ``E2``.36893690EXAMPLES::36913692sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_kernel_polynomial36933694sage: E = EllipticCurve(GF(37), [0,0,0,1,8])3695sage: R.<x> = GF(37)[]3696sage: f = (x + 14) * (x + 30)3697sage: phi = EllipticCurveIsogeny(E, f)3698sage: E2 = phi.codomain()3699sage: compute_isogeny_kernel_polynomial(E, E2, 5)3700x^2 + 7*x + 133701sage: f3702x^2 + 7*x + 1337033704sage: R.<x> = QQ[]3705sage: K.<i> = NumberField(x^2 + 1)3706sage: E = EllipticCurve(K, [0,0,0,1,0])3707sage: E2 = EllipticCurve(K, [0,0,0,16,0])3708sage: compute_isogeny_kernel_polynomial(E, E2, 4)3709x^3 + x37103711"""37123713ker_poly = compute_isogeny_starks(E1, E2, ell)3714ker_poly = split_kernel_polynomial(E1, ker_poly, ell)37153716return ker_poly371737183719def compute_intermediate_curves(E1, E2):3720r"""3721Computes isomorphism from ``E1`` to an intermediate domain and an3722isomorphism from an intermediate codomain to ``E2``.37233724Intermediate domain and intermediate codomain, are in short3725Weierstrass form.37263727This is used so we can compute `\wp` functions from the short3728Weierstrass model more easily.37293730The underlying field must be of characteristic not equal to 2,3.37313732INPUT:37333734- ``E1`` - an elliptic curve3735- ``E2`` - an elliptic curve37363737OUTPUT:37383739tuple -- (``pre_isomorphism``, ``post_isomorphism``, ``intermediate_domain``,3740``intermediate_codomain``):37413742- ``intermediate_domain``: a short Weierstrass model isomorphic to ``E1``3743- ``intermediate_codomain``: a short Weierstrass model isomorphic to ``E2``3744- ``pre_isomorphism``: normalized isomorphism from ``E1`` to intermediate_domain3745- ``post_isomorphism``: normalized isomorphism from intermediate_codomain to ``E2``37463747EXAMPLES::37483749sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_intermediate_curves3750sage: E = EllipticCurve(GF(83), [1,0,1,1,0])3751sage: R.<x> = GF(83)[]; f = x+243752sage: phi = EllipticCurveIsogeny(E, f)3753sage: E2 = phi.codomain()3754sage: compute_intermediate_curves(E, E2)3755(Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83,3756Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83,3757Generic morphism:3758From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 833759To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 833760Via: (u,r,s,t) = (1, 76, 41, 3),3761Generic morphism:3762From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 833763To: 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 833764Via: (u,r,s,t) = (1, 7, 42, 80))37653766sage: R.<x> = QQ[]3767sage: K.<i> = NumberField(x^2 + 1)3768sage: E = EllipticCurve(K, [0,0,0,1,0])3769sage: E2 = EllipticCurve(K, [0,0,0,16,0])3770sage: compute_intermediate_curves(E, E2)3771(Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,3772Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1,3773Generic morphism:3774From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13775To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13776Via: (u,r,s,t) = (1, 0, 0, 0),3777Generic morphism:3778From: 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 + 13779To: 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 + 13780Via: (u,r,s,t) = (1, 0, 0, 0))37813782"""37833784if (E1.base_ring().characteristic() in [2,3]):3785raise NotImplemented37863787# compute the r,s,t values that clear the denominator of E13788a1 = E1.a1()3789a2 = E1.a2()3790a3 = E1.a3()37913792s1 = -a1/23793r1 = (s1**2 + s1*a1 - a2)/33794t1 = (-r1*a1 - a3)/237953796# compute the isomorphism from E1 to intermediate_domain3797pre_isom = WeierstrassIsomorphism(E1, (1, r1, s1, t1))37983799intermediate_domain = pre_isom.codomain().codomain()38003801# compute the r,s,t values that clear the denominator of E23802a1pr = E2.a1()3803a2pr = E2.a2()3804a3pr = E2.a3()38053806s2 = -a1pr/23807r2 = (s2**2 + s2*a1pr - a2pr)/33808t2 = (-r2*a1pr - a3pr)/238093810post_isom_inv = WeierstrassIsomorphism(E2, (1, r2, s2, t2))3811intermediate_codomain = post_isom_inv.codomain().codomain()38123813post_isom = WeierstrassIsomorphism(intermediate_codomain, (1, -r2, -s2, -t2))38143815return (intermediate_domain, intermediate_codomain, pre_isom, post_isom)381638173818def compute_sequence_of_maps(E1, E2, ell):3819r"""3820Given domain ``E1`` and codomain ``E2`` such that there is a3821degree ``ell`` separable normalized isogeny from ``E1`` to ``E2``,3822returns pre/post isomorphism, as well as intermediate domain and3823codomain, and kernel polynomial.38243825EXAMPLES::38263827sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_sequence_of_maps3828sage: E = EllipticCurve('11a1')3829sage: R.<x> = QQ[]; f = x^2 - 21*x + 803830sage: phi = EllipticCurveIsogeny(E, f)3831sage: E2 = phi.codomain()3832sage: compute_sequence_of_maps(E, E2, 5)3833(Generic morphism:3834From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field3835To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field3836Via: (u,r,s,t) = (1, 1/3, 0, -1/2),3837Generic morphism:3838From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field3839To: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field3840Via: (u,r,s,t) = (1, -1/3, 0, 1/2),3841Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field,3842Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field,3843x^2 - 61/3*x + 658/9)38443845sage: K.<i> = NumberField(x^2 + 1)3846sage: E = EllipticCurve(K, [0,0,0,1,0])3847sage: E2 = EllipticCurve(K, [0,0,0,16,0])3848sage: compute_sequence_of_maps(E, E2, 4)3849(Generic morphism:3850From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13851To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 13852Via: (u,r,s,t) = (1, 0, 0, 0),3853Generic morphism:3854From: 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 + 13855To: 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 + 13856Via: (u,r,s,t) = (1, 0, 0, 0),3857Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,3858Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1,3859x^3 + x)38603861sage: E = EllipticCurve(GF(97), [1,0,1,1,0])3862sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 213863sage: phi = EllipticCurveIsogeny(E, f)3864sage: E2 = phi.codomain()3865sage: compute_sequence_of_maps(E, E2, 11)3866(Generic morphism:3867From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 973868To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 973869Via: (u,r,s,t) = (1, 8, 48, 44),3870Generic morphism:3871From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 973872To: 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 973873Via: (u,r,s,t) = (1, 89, 49, 53),3874Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97,3875Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97,3876x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69)38773878"""38793880(E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2)38813882ker_poly = compute_isogeny_kernel_polynomial(E1pr, E2pr, ell)38833884return (pre_isom, post_isom, E1pr, E2pr, ker_poly)388538863887# Utility function for manipulating isogeny degree matrices38883889def fill_isogeny_matrix(M):3890"""3891Returns a filled isogeny matrix giving all degrees from one giving only prime degrees.38923893INPUT:38943895- ``M`` -- a square symmetric matrix whose off-diagonal `i`, `j`3896entry is either a prime `l` (if the `i`'th and `j`'th curves3897have an `l`-isogeny between them), otherwise is 0.38983899OUTPUT:39003901(matrix) a square matrix with entries `1` on the diagonal, and in3902general the `i`, `j` entry is `d>0` if `d` is the minimal degree3903of an isogeny from the `i`'th to the `j`'th curve,39043905EXAMPLES::39063907sage: 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]]); M3908[0 2 3 3 0 0]3909[2 0 0 0 3 3]3910[3 0 0 0 2 0]3911[3 0 0 0 0 2]3912[0 3 2 0 0 0]3913[0 3 0 2 0 0]3914sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix3915sage: fill_isogeny_matrix(M)3916[ 1 2 3 3 6 6]3917[ 2 1 6 6 3 3]3918[ 3 6 1 9 2 18]3919[ 3 6 9 1 18 2]3920[ 6 3 2 18 1 9]3921[ 6 3 18 2 9 1]3922"""3923from sage.matrix.all import Matrix3924from sage.rings.infinity import Infinity39253926n = M.nrows()3927M0 = copy(M)3928for i in range(n):3929M0[i,i]=139303931def fix(d):3932if d==0: return Infinity3933return d39343935def fix2(d):3936if d==Infinity: return 03937return d39383939def pr(M1,M2):3940return 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)])39413942M1 = M03943M2 = pr(M0,M1)3944while M1!=M2:3945M1 = M23946M2 = pr(M0,M1)39473948return M139493950def unfill_isogeny_matrix(M):3951"""3952Reverses the action of ``fill_isogeny_matrix``.39533954INPUT:39553956- ``M`` -- a square symmetric matrix of integers.39573958OUTPUT:39593960(matrix) a square symmetric matrix obtained from ``M`` by3961replacing non-prime entries with `0`.39623963EXAMPLES::39643965sage: 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]]); M3966[0 2 3 3 0 0]3967[2 0 0 0 3 3]3968[3 0 0 0 2 0]3969[3 0 0 0 0 2]3970[0 3 2 0 0 0]3971[0 3 0 2 0 0]3972sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix, unfill_isogeny_matrix3973sage: M1 = fill_isogeny_matrix(M); M13974[ 1 2 3 3 6 6]3975[ 2 1 6 6 3 3]3976[ 3 6 1 9 2 18]3977[ 3 6 9 1 18 2]3978[ 6 3 2 18 1 9]3979[ 6 3 18 2 9 1]3980sage: unfill_isogeny_matrix(M1)3981[0 2 3 3 0 0]3982[2 0 0 0 3 3]3983[3 0 0 0 2 0]3984[3 0 0 0 0 2]3985[0 3 2 0 0 0]3986[0 3 0 2 0 0]3987sage: unfill_isogeny_matrix(M1) == M3988True3989"""3990from sage.matrix.all import Matrix3991from sage.rings.infinity import Infinity39923993n = M.nrows()3994M1 = copy(M)3995zero = Integer(0)3996for i in range(n):3997M1[i,i] = zero3998for j in range(i):3999if not M1[i,j].is_prime():4000M1[i,j] = zero4001M1[j,i] = zero4002return M1400340044005