Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Isogenies of small prime degree.
Functions for the computation of isogenies of small primes degree. First: `l` = 2, 3, 5, 7, or 13, where the modular curve `X_0(l)` has genus 0. Second: `l` = 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71, where `X_0^+(l)` has genus 0 and `X_0(l)` is elliptic or hyperelliptic. Also: `l` = 11, 17, 19, 37, 43, 67 or 163 over `\QQ` (the sporadic cases with only finitely many `j`-invariants each). All the above only require factorization of a polynomial of degree `l+1`. Finally, a generic function which works for arbitrary odd primes `l` (including the characteristic), but requires factorization of the `l`-division polynomial, of degree `(l^2-1)/2`.
AUTHORS:
- John Cremona and Jenny Cooley: 2009-07..11: the genus 0 cases the sporadic cases over `\QQ`.
- Kimi Tsukazaki and John Cremona: 2013-07: The 10 (hyper)-elliptic cases and the generic algorithm. See [KT2013]_.
REFERENCES:
.. [CW2005] \J. E. Cremona and M. Watkins. Computing isogenies of elliptic curves. preprint, 2005. .. [KT2013] \K. Tsukazaki, Explicit Isogenies of Elliptic Curves, PhD thesis, University of Warwick, 2013.
"""
#***************************************************************************** # Copyright (C) 2012-2013 John Cremona, Jenny Cooley, Kimi Tsukazaki # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
########################################################################## # The following section is all about computing l-isogenies, where l is # a prime. The genus 0 cases `l` = 2, 3, 5, 7 and 13 are # implemented over any field of characteristic not 2, 3 or `l`; over # `\QQ` the "sporadic" cases `l` = 11, 17, 19, 37, 43, 67 or 163 with # only finitely many `j`-invariants each. are also implemented. ##########################################################################
def Fricke_polynomial(l): r""" Fricke polynomial for ``l`` =2,3,5,7,13.
For these primes (and these only) the modular curve `X_0(l)` has genus zero, and its field is generated by a single modular function called the Fricke module (or Hauptmodul), `t`. There is a classical choice of such a generator `t` in each case, and the `j`-function is a rational function of `t` of degree `l+1` of the form `P(t)/t` where `P` is a polynomial of degree `l+1`. Up to scaling, `t` is determined by the condition that the ramification points above `j=\infty` are `t=0` (with ramification degree `1`) and `t=\infty` (with degree `l`). The ramification above `j=0` and `j=1728` may be seen in the factorizations of `j(t)` and `k(t)` where `k=j-1728`.
OUTPUT:
The polynomial `P(t)` as an element of `\ZZ[t]`.
TESTS::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Fricke_polynomial sage: Fricke_polynomial(2) t^3 + 48*t^2 + 768*t + 4096 sage: Fricke_polynomial(3) t^4 + 36*t^3 + 270*t^2 + 756*t + 729 sage: Fricke_polynomial(5) t^6 + 30*t^5 + 315*t^4 + 1300*t^3 + 1575*t^2 + 750*t + 125 sage: Fricke_polynomial(7) t^8 + 28*t^7 + 322*t^6 + 1904*t^5 + 5915*t^4 + 8624*t^3 + 4018*t^2 + 748*t + 49 sage: Fricke_polynomial(13) t^14 + 26*t^13 + 325*t^12 + 2548*t^11 + 13832*t^10 + 54340*t^9 + 157118*t^8 + 333580*t^7 + 509366*t^6 + 534820*t^5 + 354536*t^4 + 124852*t^3 + 15145*t^2 + 746*t + 13 """ else: raise ValueError("The only genus zero primes are 2, 3, 5, 7 or 13.")
def Fricke_module(l): r""" Fricke module for ``l`` =2,3,5,7,13.
For these primes (and these only) the modular curve `X_0(l)` has genus zero, and its field is generated by a single modular function called the Fricke module (or Hauptmodul), `t`. There is a classical choice of such a generator `t` in each case, and the `j`-function is a rational function of `t` of degree `l+1` of the form `P(t)/t` where `P` is a polynomial of degree `l+1`. Up to scaling, `t` is determined by the condition that the ramification points above `j=\infty` are `t=0` (with ramification degree `1`) and `t=\infty` (with degree `l`). The ramification above `j=0` and `j=1728` may be seen in the factorizations of `j(t)` and `k(t)` where `k=j-1728`.
OUTPUT:
The rational function `P(t)/t`.
TESTS::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Fricke_module sage: Fricke_module(2) (t^3 + 48*t^2 + 768*t + 4096)/t sage: Fricke_module(3) (t^4 + 36*t^3 + 270*t^2 + 756*t + 729)/t sage: Fricke_module(5) (t^6 + 30*t^5 + 315*t^4 + 1300*t^3 + 1575*t^2 + 750*t + 125)/t sage: Fricke_module(7) (t^8 + 28*t^7 + 322*t^6 + 1904*t^5 + 5915*t^4 + 8624*t^3 + 4018*t^2 + 748*t + 49)/t sage: Fricke_module(13) (t^14 + 26*t^13 + 325*t^12 + 2548*t^11 + 13832*t^10 + 54340*t^9 + 157118*t^8 + 333580*t^7 + 509366*t^6 + 534820*t^5 + 354536*t^4 + 124852*t^3 + 15145*t^2 + 746*t + 13)/t """ except ValueError: raise ValueError("The only genus zero primes are 2, 3, 5, 7 or 13.")
r""" Generic kernel polynomial for genus zero primes.
For each of the primes `l` for which `X_0(l)` has genus zero (namely `l=2,3,5,7,13`), we may define an elliptic curve `E_t` over `\QQ(t)`, with coefficients in `\ZZ[t]`, which has good reduction except at `t=0` and `t=\infty` (which lie above `j=\infty`) and at certain other values of `t` above `j=0` when `l=3` (one value) or `l\equiv1\pmod{3}` (two values) and above `j=1728` when `l=2` (one value) or `l\equiv1 \pmod{4}` (two values). (These exceptional values correspond to endomorphisms of `E_t` of degree `l`.) The `l`-division polynomial of `E_t` has a unique factor of degree `(l-1)/2` (or 1 when `l=2`), with coefficients in `\ZZ[t]`, which we call the Generic Kernel Polynomial for `l`. These are used, by specialising `t`, in the function :meth:`isogenies_prime_degree_genus_0`, which also has to take into account the twisting factor between `E_t` for a specific value of `t` and the short Weierstrass form of an elliptic curve with `j`-invariant `j(t)`. This enables the computation of the kernel polynomials of isogenies without having to compute and factor division polynomials.
All of this data is quickly computed from the Fricke modules, except that for `l=13` the factorization of the Generic Division Polynomial takes a long time, so the value have been precomputed and cached; by default the cached values are used, but the code here will recompute them when ``use_stored`` is ``False``, as in the doctests.
INPUT:
- ``l`` -- either 2, 3, 5, 7, or 13.
- ``use_stored`` (boolean, default True) -- If True, use precomputed values, otherwise compute them on the fly.
.. note::
This computation takes a negligible time for `l=2,3,5,7` but more than 100s for `l=13`. The reason for allowing dynamic computation here instead of just using precomputed values is for testing.
TESTS::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Fricke_module, Psi sage: assert Psi(2, use_stored=True) == Psi(2, use_stored=False) sage: assert Psi(3, use_stored=True) == Psi(3, use_stored=False) sage: assert Psi(5, use_stored=True) == Psi(5, use_stored=False) sage: assert Psi(7, use_stored=True) == Psi(7, use_stored=False) sage: assert Psi(13, use_stored=True) == Psi(13, use_stored=False) # not tested (very long time) """ raise ValueError("Genus zero primes are 2, 3, 5, 7 or 13.")
+ 3*(t**2 + 13*t + 33)*(t**2 + 13*t + 49)*X + (t**2 + 13*t + 49)*(t**4 + 26*t**3 + 219*t**2 + 778*t + 881)) # The coefficients for l=13 are: # X**6: 1 # X**5: (6) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13) # X**4: (3) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13) * (5*t**4 + 55*t**3 + 260*t**2 + 583*t + 537) # X**3: (4) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13)**2 * (5*t**6 + 80*t**5 + 560*t**4 + 2214*t**3 + 5128*t**2 + 6568*t + 3373) # X**2: (3) * (t**2 + 5*t + 13)**2 * (t**2 + 6*t + 13)**2 * (5*t**8 + 110*t**7 + 1045*t**6 + 5798*t**5 + 20508*t**4 + 47134*t**3 + 67685*t**2 + 54406*t + 17581) # X**1: (6) * (t**2 + 5*t + 13)**2 * (t**2 + 6*t + 13)**3 * (t**10 + 27*t**9 + 316*t**8 + 2225*t**7 + 10463*t**6 + 34232*t**5 + 78299*t**4 + 122305*t**3 + 122892*t**2 + 69427*t + 16005) # X**0: (t**2 + 5*t + 13)**2 * (t**2 + 6*t + 13)**3 * (t**14 + 38*t**13 + 649*t**12 + 6844*t**11 + 50216*t**10 + 271612*t**9 + 1115174*t**8 + 3520132*t**7 + 8549270*t**6 + 15812476*t**5 + 21764840*t**4 + 21384124*t**3 + 13952929*t**2 + 5282630*t + 854569) #
# Here the generic kernel polynomials are actually calculated: +[p for p,e in k.factor() if e==2])
""" Returns list of ``l`` -isogenies with domain ``E``.
INPUT:
- ``E`` -- an elliptic curve.
- ``l`` -- either None or 2, 3, 5, 7, or 13.
OUTPUT:
(list) When ``l`` is None a list of all isogenies of degree 2, 3, 5, 7 and 13, otherwise a list of isogenies of the given degree.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``, which automatically calls the appropriate function.
ALGORITHM:
Cremona and Watkins [CW2005]_. See also [KT2013]_, Chapter 4.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_0 sage: E = EllipticCurve([0,12]) sage: isogenies_prime_degree_genus_0(E, 5) []
sage: E = EllipticCurve('1450c1') sage: isogenies_prime_degree_genus_0(E) [Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + 300*x - 1000 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 5950*x - 182250 over Rational Field]
sage: E = EllipticCurve('50a1') sage: isogenies_prime_degree_genus_0(E) [Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 126*x - 552 over Rational Field, Isogeny of degree 5 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 76*x + 298 over Rational Field] """ raise ValueError("%s is not a genus 0 prime."%l) raise NotImplementedError("2, 3, 5, 7 and 13-isogenies are not yet implemented in characteristic 2 and 3, and when the characteristic is the same as the degree of the isogeny.")
# The generic kernel polynomial applies to a standard curve # E_t with the correct j-invariant; we must compute the # appropriate twisting factor to scale X by: +[p for p,e in kt.factor() if e==2]))
# The following code computes data to be used in # isogenies_sporadic_Q. Over Q there are only finitely many # j-invariants of curves with l-isogenies where l is not equal to 2, # 3, 5, 7 or 13. In these cases l is equal to 11, 17, 19, 37, 43, 67 # or 163. We refer to these l as "sporadic".
# sporadic_j is a dictionary holding for each possible sporadic # j-invariant, the unique l such that an l-isogeny exists. QQ(-121) : 11, QQ(-32768) : 11, QQ(-24729001) : 11, QQ(-297756989)/2 : 17, QQ(-882216989)/131072 : 17, QQ(-884736) : 19, QQ(-9317) : 37, QQ(-162677523113838677) : 37, QQ(-884736000) : 43, QQ(-147197952000) : 67, QQ(-262537412640768000) : 163 }
def _sporadic_Q_data(j): """ Returns technical data used in computing sporadic isogenies over `\QQ`.
INPUT:
- ``j`` -- The `j`-invariant of a sporadic curve, i.e. one of the keys of ``sporadic_j``.
OUTPUT:
``([a4,a6],coeffs)`` where ``[a4,a6]`` are the coefficients of a short Weierstrass equation of an elliptic curve E with j(E)=``j``, and ``coeffs`` is a list of coefficients of a polynomial defining the kernel of an l-isogeny from E. In all but one case this polynomial is monic with integer coefficients. In one case ($\ell=37$, $j=-162677523113838677$) the constant coefficient has denominator $37$.
Whenever we have a curve of j-invariant ``j``, we can compute the corresponding l-isogeny by just scaling ``coeffs`` by the right twisting factor and using the result as a kernel-polynomial.
ALGORITHM:
For small l it works fine to factor the l-division polynomial, but this takes a long time for the larger l and is a very bad idea for l=163; hence we use floating point arithmetic with a precision which is known to work. This idea was suggested by Samir Siksek.
TESTS::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import sporadic_j, _sporadic_Q_data sage: [_sporadic_Q_data(j) for j in sorted(sporadic_j.keys()) if j != -262537412640768000] [([-269675595, -1704553285050], [-31653754873248632711650187487655160190139073510876609346911928661154296875/37, -1469048260972089939455942042937882262144594798448952781325533511718750, -1171741935131505774747142644126089902595908234671576131857702734375, -574934780393177024547076427530739751753985644656221274606250000, -193516922725803688001809624711400287605136013195315374687500, -47085563820928456130325308223963045033502182349693125000, -8472233937388712980597845725196873697064639957437500, -1124815211213953261752081095348112305023653750000, -105684015609077608033913080859605951322531250, -5911406027236569746089675554748135312500, 22343907270397352965399097794968750, 43602171843758666292581116410000, 5054350766002463251474186500, 350135768194635636171000, 16633063574896677300, 549939627039600, 12182993865, 163170, 1]), ([-117920, 15585808], [426552448394636714720553816389274308035895411389805883034985546818882031845376, -55876556222880738651382959148329502876096075327084935039031884373558741172224, 3393295715290183821010552313572221545212247684503012173117764703828786020352, -125729166452196578653551230178028570067747190427221869867485520072257044480, 3121342502030777257351089270834971957072933779704445667351054593298530304, -52544031605544530265465344472543470442324636919759253720520768014516224, 532110915869155495738137756847596184665209453108323879594125221167104, -399031158106622651277981701966309467713625045637309782055519780864, -101914346170769215732007802723651742508893380955930030421292613632, 2296526155500449624398016447877283594461904009374321659789443072, -31950871094301541469458501953701002806003991982768349794795520, 329792235011603804948028315065667439678526339671142107709440, -2655636715955021784085217734679612378726442691190553837568, 16825164648840434987220620681420687654501026066872664064, -81705027839007003131400500185224450729843244954288128, 273656504606483403474090105104132405333665144373248, -320807702482945680116212224172370503903312084992, -3166683390779345463318656135338172047199043584, 27871349428383710305216046431806697565585408, -132774697798318602604125735604528772808704, 436096215568182871014215818309741314048, -964687143341252402362763535357837312, 942144169187362941776488535425024, 2794850106281773765892648206336, -17236916236678037389276086272, 50979778712911923486851072, -105035658611718440992768, 161833913559276412928, -188675698610077696, 163929317513984, -102098677888, 42387952, -10184, 1]), ([-13760, 621264], [-1961864562041980324821547425314935668736, 784270445793223959453256359333693751296, -120528107728500223255333768387027271680, 10335626145581464192664472924270362624, -568426570575654606865505142156820480, 21261993723422650574629752537088000, -544630471727787626557612832587776, 8870521306520473088172555763712, -54993059067301585878494740480, -1434261324709904840432549888, 50978938193065926383894528, -845761855773797582372864, 8627493611216601088000, -48299605284169187328, -32782260293713920, 3415534989828096, -34580115625984, 199359712512, -730488128, 1658080, -2064, 1]), ([-3940515, 3010787550], [-6458213126940667330314375, 34699336325466068070000, -72461450055340471500, 68342601718080000, -15140380554450, -25802960400, 23981220, -8160, 1]), ([-38907, -2953962], [-20349931239, -424530315, -134838, 53658, 429, 1]), ([-608, 5776], [-34162868224, -8540717056, 6405537792, -1123778560, 84283392, -2033152, -92416, 6992, -152, 1]), ([-9504, 365904], [1294672896, -92835072, 1463616, 7920, -264, 1]), ([-10395, 444150], [-38324677699334121599624973029296875, -17868327793500376961572310472656250, 2569568362004197901139023084765625, -95128267987528547588017818750000, -822168183291347061312510937500, 134395594560592096297190625000, -2881389756919344324888937500, -2503855007083401977250000, 922779077075655997443750, -11503912310262102937500, -18237870962450291250, 1457822151548910000, -10087015556047500, -13677678063000, 490243338900, -2461460400, 5198445, -4410, 1]), ([-856035, -341748450], [103687510635057329105625, 961598491955315190000, 1054634146768300500, -6553122389064000, -14554350284850, -2046589200, 13185540, 8160, 1]), ([-3267, -280962], [1480352841, -56169531, -2829222, 10890, 429, 1])]
See :trac:`22328`. This used to fail on l=37, j=-162677523113838677 for which the kernel polynomial is not integral::
sage: R = PolynomialRing(QQ,'x') sage: for j in sporadic_j: ....: ell = sporadic_j[j] ....: if ell==163: continue # takes 40s ....: E = EllipticCurve(j=j).short_weierstrass_model() ....: f = R(_sporadic_Q_data(j)[1]) ....: g = E.division_polynomial(ell) ....: assert g%f==0
""" else:
""" Returns list of ``l`` -isogenies with domain ``E`` (defined over `\QQ`).
Returns a list of sporadic l-isogenies from E (l = 11, 17, 19, 37, 43, 67 or 163). Only for elliptic curves over `\QQ`.
INPUT:
- ``E`` -- an elliptic curve defined over `\QQ`.
- ``l`` -- either None or a prime number.
OUTPUT:
(list) If ``l`` is None, a list of all isogenies with domain ``E`` and of degree 11, 17, 19, 37, 43, 67 or 163; otherwise a list of isogenies of the given degree.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``, which automatically calls the appropriate function.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_sporadic_Q sage: E = EllipticCurve('121a1') sage: isogenies_sporadic_Q(E, 11) [Isogeny of degree 11 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 30*x - 76 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 305*x + 7888 over Rational Field] sage: isogenies_sporadic_Q(E, 13) [] sage: isogenies_sporadic_Q(E, 17) [] sage: isogenies_sporadic_Q(E) [Isogeny of degree 11 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 30*x - 76 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 305*x + 7888 over Rational Field]
sage: E = EllipticCurve([1, 1, 0, -660, -7600]) sage: isogenies_sporadic_Q(E, 17) [Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 660*x - 7600 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 878710*x + 316677750 over Rational Field] sage: isogenies_sporadic_Q(E) [Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 660*x - 7600 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 878710*x + 316677750 over Rational Field] sage: isogenies_sporadic_Q(E, 11) []
sage: E = EllipticCurve([0, 0, 1, -1862, -30956]) sage: isogenies_sporadic_Q(E, 11) [] sage: isogenies_sporadic_Q(E, 19) [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field] sage: isogenies_sporadic_Q(E) [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field]
sage: E = EllipticCurve([0, -1, 0, -6288, 211072]) sage: E.conductor() 19600 sage: isogenies_sporadic_Q(E,37) [Isogeny of degree 37 from Elliptic Curve defined by y^2 = x^3 - x^2 - 6288*x + 211072 over Rational Field to Elliptic Curve defined by y^2 = x^3 - x^2 - 163137088*x - 801950801728 over Rational Field]
sage: E = EllipticCurve([1, 1, 0, -25178045, 48616918750]) sage: E.conductor() 148225 sage: isogenies_sporadic_Q(E,37) [Isogeny of degree 37 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 25178045*x + 48616918750 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 970*x - 13075 over Rational Field]
sage: E = EllipticCurve([-3440, 77658]) sage: E.conductor() 118336 sage: isogenies_sporadic_Q(E,43) [Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 - 3440*x + 77658 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 6360560*x - 6174354606 over Rational Field]
sage: E = EllipticCurve([-29480, -1948226]) sage: E.conductor() 287296 sage: isogenies_sporadic_Q(E,67) [Isogeny of degree 67 from Elliptic Curve defined by y^2 = x^3 - 29480*x - 1948226 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 132335720*x + 585954296438 over Rational Field]
sage: E = EllipticCurve([-34790720, -78984748304]) sage: E.conductor() 425104 sage: isogenies_sporadic_Q(E,163) [Isogeny of degree 163 from Elliptic Curve defined by y^2 = x^3 - 34790720*x - 78984748304 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 924354639680*x + 342062961763303088 over Rational Field] """ or (l is not None and sporadic_j[j] != l)):
"""Returns a list of all 2-isogenies with domain ``E``.
INPUT:
- ``E`` -- an elliptic curve.
OUTPUT:
(list) 2-isogenies with domain ``E``. In general these are normalised, but over `\QQ` and other number fields, the codomain is a minimal model where possible.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_2 sage: E = EllipticCurve('14a1'); E Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x - 6 over Rational Field sage: [phi.codomain().ainvs() for phi in isogenies_2(E)] [(1, 0, 1, -36, -70)]
sage: E = EllipticCurve([1,2,3,4,5]); E Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field sage: [phi.codomain().ainvs() for phi in isogenies_2(E)] [] sage: E = EllipticCurve(QQbar, [9,8]); E Elliptic Curve defined by y^2 = x^3 + 9*x + 8 over Algebraic Field sage: isogenies_2(E) # not implemented
"""
"""Returns a list of all 3-isogenies with domain ``E``.
INPUT:
- ``E`` -- an elliptic curve.
OUTPUT:
(list) 3-isogenies with domain ``E``. In general these are normalised, but over `\QQ` or a number field, the codomain is a global minimal model where possible.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_3 sage: E = EllipticCurve(GF(17), [1,1]) sage: [phi.codomain().ainvs() for phi in isogenies_3(E)] [(0, 0, 0, 9, 7), (0, 0, 0, 0, 1)]
sage: E = EllipticCurve(GF(17^2,'a'), [1,1]) sage: [phi.codomain().ainvs() for phi in isogenies_3(E)] [(0, 0, 0, 9, 7), (0, 0, 0, 0, 1), (0, 0, 0, 5*a + 1, a + 13), (0, 0, 0, 12*a + 6, 16*a + 14)]
sage: E = EllipticCurve('19a1') sage: [phi.codomain().ainvs() for phi in isogenies_3(E)] [(0, 1, 1, 1, 0), (0, 1, 1, -769, -8470)]
sage: E = EllipticCurve([1,1]) sage: [phi.codomain().ainvs() for phi in isogenies_3(E)] []
"""
# 6 special cases: `l` = 5, 7, 13 and `j` = 0, 1728.
"""Returns a list of all the 5-isogenies with domain ``E`` when the j-invariant is 0.
OUTPUT:
(list) 5-isogenies with codomain E. In general these are normalised, but over `\QQ` or a number field, the codomain is a global minimal model where possible.
.. note::
This implementation requires that the characteristic is not 2, 3 or 5.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(5)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_5_0 sage: E = EllipticCurve([0,12]) sage: isogenies_5_0(E) []
sage: E = EllipticCurve(GF(13^2,'a'),[0,-3]) sage: isogenies_5_0(E) [Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (4*a+6)*x + (2*a+10) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (12*a+5)*x + (2*a+10) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (10*a+2)*x + (2*a+10) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (3*a+12)*x + (11*a+12) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (a+4)*x + (11*a+12) over Finite Field in a of size 13^2, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + (9*a+10)*x + (11*a+12) over Finite Field in a of size 13^2]
sage: K.<a> = NumberField(x**6-320*x**3-320) sage: E = EllipticCurve(K,[0,0,1,0,0]) sage: isogenies_5_0(E) [Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^6 - 320*x^3 - 320 to Elliptic Curve defined by y^2 + y = x^3 + (643/8*a^5-15779/48*a^4-32939/24*a^3-71989/2*a^2+214321/6*a-112115/3)*x + (2901961/96*a^5+4045805/48*a^4+12594215/18*a^3-30029635/6*a^2+15341626/3*a-38944312/9) over Number Field in a with defining polynomial x^6 - 320*x^3 - 320, Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^6 - 320*x^3 - 320 to Elliptic Curve defined by y^2 + y = x^3 + (-1109/8*a^5-53873/48*a^4-180281/24*a^3-14491/2*a^2+35899/6*a-43745/3)*x + (-17790679/96*a^5-60439571/48*a^4-77680504/9*a^3+1286245/6*a^2-4961854/3*a-73854632/9) over Number Field in a with defining polynomial x^6 - 320*x^3 - 320] """ raise ValueError("j-invariant must be 0.") raise NotImplementedError("Not implemented in characteristic 2, 3 or 5.") return []
"""Returns a list of 5-isogenies with domain ``E`` when the j-invariant is 1728.
OUTPUT:
(list) 5-isogenies with codomain E. In general these are normalised; but if `-1` is a square then there are two endomorphisms of degree `5`, for which the codomain is the same as the domain curve; and over `\QQ` or a number field, the codomain is a global minimal model where possible.
.. note::
This implementation requires that the characteristic is not 2, 3 or 5.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(5)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_5_1728 sage: E = EllipticCurve([7,0]) sage: isogenies_5_1728(E) []
sage: E = EllipticCurve(GF(13),[11,0]) sage: isogenies_5_1728(E) [Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13 to Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13 to Elliptic Curve defined by y^2 = x^3 + 11*x over Finite Field of size 13]
An example of endomorphisms of degree 5::
sage: K.<i> = QuadraticField(-1) sage: E = EllipticCurve(K,[0,0,0,1,0]) sage: isogenies_5_1728(E) [Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1] sage: _[0].rational_maps() (((4/25*i + 3/25)*x^5 + (4/5*i - 2/5)*x^3 - x)/(x^4 + (-4/5*i + 2/5)*x^2 + (-4/25*i - 3/25)), ((11/125*i + 2/125)*x^6*y + (-23/125*i + 64/125)*x^4*y + (141/125*i + 162/125)*x^2*y + (3/25*i - 4/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125)))
An example of 5-isogenies over a number field::
sage: K.<a> = NumberField(x**4+20*x**2-80) sage: K(5).is_square() #necessary but not sufficient! True sage: E = EllipticCurve(K,[0,0,0,1,0]) sage: isogenies_5_1728(E) [Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^4 + 20*x^2 - 80 to Elliptic Curve defined by y^2 = x^3 + (-753/4*a^2-4399)*x + (2779*a^3+65072*a) over Number Field in a with defining polynomial x^4 + 20*x^2 - 80, Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^4 + 20*x^2 - 80 to Elliptic Curve defined by y^2 = x^3 + (-753/4*a^2-4399)*x + (-2779*a^3-65072*a) over Number Field in a with defining polynomial x^4 + 20*x^2 - 80]
See :trac:`19840`::
sage: K.<a> = NumberField(x^4 - 5*x^2 + 5) sage: E = EllipticCurve([a^2 + a + 1, a^3 + a^2 + a + 1, a^2 + a, 17*a^3 + 34*a^2 - 16*a - 37, 54*a^3 + 105*a^2 - 66*a - 135]) sage: len(E.isogenies_prime_degree(5)) 2 sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_5_1728 sage: [phi.codomain().j_invariant() for phi in isogenies_5_1728(E)] [19691491018752*a^2 - 27212977933632, 19691491018752*a^2 - 27212977933632] """ raise ValueError("j-invariant must be 1728.") raise NotImplementedError("Not implemented in characteristic 2, 3 or 5.") # quick test for a negative answer (from Fricke module) # 2 cases # Type 1: if -1 is a square we have 2 endomorphisms # Type 2: if 5 is a square we have up to 4 (non-endomorphism) isogenies
"""Returns list of all 7-isogenies from E when the j-invariant is 0.
OUTPUT:
(list) 7-isogenies with codomain E. In general these are normalised; but if `-3` is a square then there are two endomorphisms of degree `7`, for which the codomain is the same as the domain; and over `\QQ` or a number field, the codomain is a global minimal model where possible.
.. note::
This implementation requires that the characteristic is not 2, 3 or 7.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(7)``.
EXAMPLES:
First some examples of endomorphisms::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_0 sage: K.<r> = QuadraticField(-3) sage: E = EllipticCurve(K, [0,1]) sage: isogenies_7_0(E) [Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3, Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + 1 over Number Field in r with defining polynomial x^2 + 3]
sage: E = EllipticCurve(GF(13^2,'a'),[0,-3]) sage: isogenies_7_0(E) [Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2, Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2 to Elliptic Curve defined by y^2 = x^3 + 10 over Finite Field in a of size 13^2]
Now some examples of 7-isogenies which are not endomorphisms::
sage: K = GF(101) sage: E = EllipticCurve(K, [0,1]) sage: isogenies_7_0(E) [Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 101 to Elliptic Curve defined by y^2 = x^3 + 55*x + 100 over Finite Field of size 101, Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 101 to Elliptic Curve defined by y^2 = x^3 + 83*x + 26 over Finite Field of size 101]
Examples over a number field::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_0 sage: E = EllipticCurve('27a1').change_ring(QuadraticField(-3,'r')) sage: isogenies_7_0(E) [Isogeny of degree 7 from Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3, Isogeny of degree 7 from Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 + y = x^3 + (-7) over Number Field in r with defining polynomial x^2 + 3]
sage: K.<a> = NumberField(x^6 + 1512*x^3 - 21168) sage: E = EllipticCurve(K, [0,1]) sage: isogs = isogenies_7_0(E) sage: [phi.codomain().a_invariants() for phi in isogs] [(0, 0, 0, -415/98*a^5 - 675/14*a^4 + 2255/7*a^3 - 74700/7*a^2 - 25110*a - 66420, -141163/56*a^5 + 1443453/112*a^4 - 374275/2*a^3 - 3500211/2*a^2 - 17871975/4*a - 7710065), (0, 0, 0, -24485/392*a^5 - 1080/7*a^4 - 2255/7*a^3 - 1340865/14*a^2 - 230040*a - 553500, 1753037/56*a^5 + 8345733/112*a^4 + 374275/2*a^3 + 95377029/2*a^2 + 458385345/4*a + 275241835)] sage: [phi.codomain().j_invariant() for phi in isogs] [158428486656000/7*a^3 - 313976217600000, -158428486656000/7*a^3 - 34534529335296000] """ raise ValueError("j-invariant must be 0.") raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 7.")
# there will be 2 endomorphisms if -3 is a square:
# we may have up to 6 other isogenies:
"""Returns list of all 7-isogenies from E when the j-invariant is 1728.
OUTPUT:
(list) 7-isogenies with codomain E. In general these are normalised; but over `\QQ` or a number field, the codomain is a global minimal model where possible.
.. note::
This implementation requires that the characteristic is not 2, 3, or 7.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(7)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_1728 sage: E = EllipticCurve(GF(47), [1, 0]) sage: isogenies_7_1728(E) [Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 47 to Elliptic Curve defined by y^2 = x^3 + 26 over Finite Field of size 47, Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 47 to Elliptic Curve defined by y^2 = x^3 + 21 over Finite Field of size 47]
An example in characteristic 53 (for which an earlier implementation did not work)::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_1728 sage: E = EllipticCurve(GF(53), [1, 0]) sage: isogenies_7_1728(E) [] sage: E = EllipticCurve(GF(53^2,'a'), [1, 0]) sage: [iso.codomain().ainvs() for iso in isogenies_7_1728(E)] [(0, 0, 0, 36, 19*a + 15), (0, 0, 0, 36, 34*a + 38), (0, 0, 0, 33, 39*a + 28), (0, 0, 0, 33, 14*a + 25), (0, 0, 0, 19, 45*a + 16), (0, 0, 0, 19, 8*a + 37), (0, 0, 0, 3, 45*a + 16), (0, 0, 0, 3, 8*a + 37)]
::
sage: K.<a> = NumberField(x^8 + 84*x^6 - 1890*x^4 + 644*x^2 - 567) sage: E = EllipticCurve(K, [1, 0]) sage: isogs = isogenies_7_1728(E) sage: [phi.codomain().j_invariant() for phi in isogs] [-526110256146528/53*a^6 + 183649373229024*a^4 - 3333881559996576/53*a^2 + 2910267397643616/53, -526110256146528/53*a^6 + 183649373229024*a^4 - 3333881559996576/53*a^2 + 2910267397643616/53] sage: E1 = isogs[0].codomain() sage: E2 = isogs[1].codomain() sage: E1.is_isomorphic(E2) False sage: E1.is_quadratic_twist(E2) -1
""" raise ValueError("j_invariant must be 1728 (in base field).") raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 7.")
""" Returns list of all 13-isogenies from E when the j-invariant is 0.
OUTPUT:
(list) 13-isogenies with codomain E. In general these are normalised; but if `-3` is a square then there are two endomorphisms of degree `13`, for which the codomain is the same as the domain.
.. note::
This implementation requires that the characteristic is not 2, 3 or 13.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(13)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_13_0
Endomorphisms of degree 13 will exist when -3 is a square::
sage: K.<r> = QuadraticField(-3) sage: E = EllipticCurve(K, [0, r]); E Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3 sage: isogenies_13_0(E) [Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3 to Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3] sage: isogenies_13_0(E)[0].rational_maps() (((7/338*r + 23/338)*x^13 + (-164/13*r - 420/13)*x^10 + (720/13*r + 3168/13)*x^7 + (3840/13*r - 576/13)*x^4 + (4608/13*r + 2304/13)*x)/(x^12 + (4*r + 36)*x^9 + (1080/13*r + 3816/13)*x^6 + (2112/13*r - 5184/13)*x^3 + (-17280/169*r - 1152/169)), ((18/2197*r + 35/2197)*x^18*y + (23142/2197*r + 35478/2197)*x^15*y + (-1127520/2197*r - 1559664/2197)*x^12*y + (-87744/2197*r + 5992704/2197)*x^9*y + (-6625152/2197*r - 9085824/2197)*x^6*y + (-28919808/2197*r - 2239488/2197)*x^3*y + (-1990656/2197*r - 3870720/2197)*y)/(x^18 + (6*r + 54)*x^15 + (3024/13*r + 11808/13)*x^12 + (31296/13*r + 51840/13)*x^9 + (487296/169*r - 2070144/169)*x^6 + (-940032/169*r + 248832/169)*x^3 + (1990656/2197*r + 3870720/2197)))
An example of endomorphisms over a finite field::
sage: K = GF(19^2,'a') sage: E = EllipticCurve(j=K(0)); E Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2 sage: isogenies_13_0(E) [Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2] sage: isogenies_13_0(E)[0].rational_maps() ((6*x^13 - 6*x^10 - 3*x^7 + 6*x^4 + x)/(x^12 - 5*x^9 - 9*x^6 - 7*x^3 + 5), (-8*x^18*y - 9*x^15*y + 9*x^12*y - 5*x^9*y + 5*x^6*y - 7*x^3*y + 7*y)/(x^18 + 2*x^15 + 3*x^12 - x^9 + 8*x^6 - 9*x^3 + 7))
A previous implementation did not work in some characteristics::
sage: K = GF(29) sage: E = EllipticCurve(j=K(0)) sage: isogenies_13_0(E) [Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 26*x + 12 over Finite Field of size 29, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 16*x + 28 over Finite Field of size 29]
::
sage: K = GF(101) sage: E = EllipticCurve(j=K(0)); E.ainvs() (0, 0, 0, 0, 1) sage: [phi.codomain().ainvs() for phi in isogenies_13_0(E)] [(0, 0, 0, 64, 36), (0, 0, 0, 42, 66)]
::
sage: x = polygen(QQ) sage: f = x^12 + 78624*x^9 - 130308048*x^6 + 2270840832*x^3 - 54500179968 sage: K.<a> = NumberField(f) sage: E = EllipticCurve(j=K(0)); E.ainvs() (0, 0, 0, 0, 1) sage: [phi.codomain().ainvs() for phi in isogenies_13_0(E)] [(0, 0, 20360599/165164973653422080*a^11 - 3643073/41291243413355520*a^10 - 101/8789110986240*a^9 + 5557619461/573489491852160*a^8 - 82824971/11947697746920*a^7 - 19487/21127670640*a^6 - 475752603733/29409717530880*a^5 + 87205112531/7352429382720*a^4 + 8349/521670880*a^3 + 5858744881/12764634345*a^2 - 1858703809/2836585410*a + 58759402/48906645, -139861295/2650795873449984*a^11 - 3455957/5664093746688*a^10 - 345310571/50976843720192*a^9 - 500530795/118001953056*a^8 - 12860048113/265504394376*a^7 - 25007420461/44250732396*a^6 + 458134176455/1416023436672*a^5 + 16701880631/9077073312*a^4 + 155941666417/9077073312*a^3 + 3499310115/378211388*a^2 - 736774863/94552847*a - 21954102381/94552847, 579363345221/13763747804451840*a^11 + 371192377511/860234237778240*a^10 + 8855090365657/1146978983704320*a^9 + 5367261541663/1633873196160*a^8 + 614883554332193/15930263662560*a^7 + 30485197378483/68078049840*a^6 - 131000897588387/2450809794240*a^5 - 203628705777949/306351224280*a^4 - 1587619388190379/204234149520*a^3 + 14435069706551/11346341640*a^2 + 7537273048614/472764235*a + 89198980034806/472764235), (0, 0, 20360599/165164973653422080*a^11 - 3643073/41291243413355520*a^10 - 101/8789110986240*a^9 + 5557619461/573489491852160*a^8 - 82824971/11947697746920*a^7 - 19487/21127670640*a^6 - 475752603733/29409717530880*a^5 + 87205112531/7352429382720*a^4 + 8349/521670880*a^3 + 5858744881/12764634345*a^2 - 1858703809/2836585410*a + 58759402/48906645, -6465569317/1325397936724992*a^11 - 112132307/1960647835392*a^10 - 17075412917/25488421860096*a^9 - 207832519229/531008788752*a^8 - 1218275067617/265504394376*a^7 - 9513766502551/177002929584*a^6 + 4297077855437/708011718336*a^5 + 354485975837/4538536656*a^4 + 4199379308059/4538536656*a^3 - 30841577919/189105694*a^2 - 181916484042/94552847*a - 2135779171614/94552847, -132601797212627/3440936951112960*a^11 - 6212467020502021/13763747804451840*a^10 - 1515926454902497/286744745926080*a^9 - 15154913741799637/4901619588480*a^8 - 576888119803859263/15930263662560*a^7 - 86626751639648671/204234149520*a^6 + 16436657569218427/306351224280*a^5 + 1540027900265659087/2450809794240*a^4 + 375782662805915809/51058537380*a^3 - 14831920924677883/11346341640*a^2 - 7237947774817724/472764235*a - 84773764066089509/472764235)] """ raise ValueError("j-invariant must be 0.") raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 13.")
# there will be 2 endomorphisms if -3 is a square:
# we may have up to 12 other isogenies: + (-826*t0**3 - 4424*t0**2 - 9244*t0 - 494)*x**4 + (13514*t0**3 + 72416*t0**2 + 151416*t0 + 8238)*x**3 + (-101948*t0**3 - 546304*t0**2 - 1142288*t0 - 62116)*x**2 + (354472*t0**3 + 1899488*t0**2 + 3971680*t0 + 215960)*x - 459424*t0**3 - 2461888*t0**2 - 5147648*t0 - 279904)
"""Returns list of all 13-isogenies from E when the j-invariant is 1728.
OUTPUT:
(list) 13-isogenies with codomain E. In general these are normalised; but if `-1` is a square then there are two endomorphisms of degree `13`, for which the codomain is the same as the domain; and over `\QQ` or a number field, the codomain is a global minimal model where possible.
.. note::
This implementation requires that the characteristic is not 2, 3 or 13.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(13)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_13_1728
sage: K.<i> = QuadraticField(-1) sage: E = EllipticCurve([0,0,0,i,0]); E.ainvs() (0, 0, 0, i, 0) sage: isogenies_13_1728(E) [Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + i*x over Number Field in i with defining polynomial x^2 + 1]
::
sage: K = GF(83) sage: E = EllipticCurve(K, [0,0,0,5,0]); E.ainvs() (0, 0, 0, 5, 0) sage: isogenies_13_1728(E) [] sage: K = GF(89) sage: E = EllipticCurve(K, [0,0,0,5,0]); E.ainvs() (0, 0, 0, 5, 0) sage: isogenies_13_1728(E) [Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89 to Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89 to Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 89]
::
sage: K = GF(23) sage: E = EllipticCurve(K, [1,0]) sage: isogenies_13_1728(E) [Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 23 to Elliptic Curve defined by y^2 = x^3 + 16 over Finite Field of size 23, Isogeny of degree 13 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 23 to Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 23]
::
sage: x = polygen(QQ) sage: f = x^12 + 1092*x^10 - 432432*x^8 + 6641024*x^6 - 282896640*x^4 - 149879808*x^2 - 349360128 sage: K.<a> = NumberField(f) sage: E = EllipticCurve(K, [1,0]) sage: [phi.codomain().ainvs() for phi in isogenies_13_1728(E)] [(0, 0, 0, -4225010072113/3063768069807341568*a^10 - 24841071989413/15957125363579904*a^8 + 11179537789374271/21276167151439872*a^6 - 407474562289492049/47871376090739712*a^4 + 1608052769560747/4522994717568*a^2 + 7786720245212809/36937790193472, -363594277511/574456513088876544*a^11 - 7213386922793/2991961005671232*a^9 - 2810970361185589/1329760446964992*a^7 + 281503836888046601/8975883017013696*a^5 - 1287313166530075/848061509544*a^3 + 9768837984886039/6925835661276*a), (0, 0, 0, -4225010072113/3063768069807341568*a^10 - 24841071989413/15957125363579904*a^8 + 11179537789374271/21276167151439872*a^6 - 407474562289492049/47871376090739712*a^4 + 1608052769560747/4522994717568*a^2 + 7786720245212809/36937790193472, 363594277511/574456513088876544*a^11 + 7213386922793/2991961005671232*a^9 + 2810970361185589/1329760446964992*a^7 - 281503836888046601/8975883017013696*a^5 + 1287313166530075/848061509544*a^3 - 9768837984886039/6925835661276*a)] """ raise ValueError("j-invariant must be 1728.") raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 13.")
# we will have two endomorphisms if -1 is a square:
# we may have up to 12 other isogenies:
- 5414*t0 - 162)*x**5 + (-21722*t0**5 - 205718*t0**4 - 890146*t0**3 - 1873338*t0**2 - 1652478*t0 + 61610)*x**4 + (-3391376*t0**5 - 32162416*t0**4 - 139397232*t0**3 - 294310576*t0**2 - 261885968*t0 + 6105552)*x**3 + (-241695080*t0**5 - 2291695976*t0**4 - 9930313256*t0**3 - 20956609720*t0**2 - 18625380856*t0 + 469971320)*x**2 + (-8085170432*t0**5 - 76663232384*t0**4 - 332202985024*t0**3 - 701103233152*t0**2 - 623190845440*t0 + 15598973056)*x - 101980510208*t0**5 - 966973468160*t0**4 - 4190156868352*t0**3 - 8843158270336*t0**2 - 7860368751232*t0 + 196854655936)
# List of primes l for which X_0(l) is (hyper)elliptic and X_0^+(l) has genus 0
def _hyperelliptic_isogeny_data(l): r""" Helper function for elliptic curve isogenies.
INPUT:
- ``l`` -- a prime in [11, 17, 19, 23, 29, 31, 41, 47, 59, 71]
OUTPUT:
- A dict holding a collection of precomputed data needed for computing `l`-isogenies.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import _hyperelliptic_isogeny_data sage: HID = _hyperelliptic_isogeny_data(11) sage: HID['A2'] 55*u - 33 sage: HID['A4'] -183*u^2 + 738*u - 180*v - 135 sage: HID['A6'] 1330*u^3 - 11466*u^2 + 1332*u*v + 2646*u - 1836*v + 1890 sage: HID['alpha'] u^11 - 55*u^10 + 1188*u^9 - 12716*u^8 + 69630*u^7 - 177408*u^6 + 133056*u^5 + 132066*u^4 - 187407*u^3 + 40095*u^2 + 24300*u - 6750 sage: HID['beta'] u^9 - 47*u^8 + 843*u^7 - 7187*u^6 + 29313*u^5 - 48573*u^4 + 10665*u^3 + 27135*u^2 - 12150*u sage: HID['hyper_poly'] u^4 - 16*u^3 + 2*u^2 + 12*u - 7
sage: _hyperelliptic_isogeny_data(37) Traceback (most recent call last): ... ValueError: 37 must be one of [11, 17, 19, 23, 29, 31, 41, 47, 59, 71].
""" #beta factors as (u - 15) * (u - 6) * (u - 3) * (u - 1) * u * (u**2 - 12*u - 9) * (u**2 - 10*u + 5) #beta factors as (u - 10) * (u - 5) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 10*u + 7) * (u**2 - 6*u - 4) * (u**2 - 4*u + 2) * (u**3 - 9*u**2 + 8*u - 4) #beta factors as (u - 7) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 8*u - 4) * (u**2 - 6*u - 15) * (u**2 - 5*u - 5) * (u**2 - 5*u + 2) * (u**2 - 2*u - 4) * (u**2 + u - 1) #beta factors as (u - 5) * (u - 3) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 8*u + 3) * (u**2 - 6*u - 9) * (u**3 - 7*u**2 + 3*u - 5) * (u**3 - 7*u**2 + 7*u - 3) * (u**4 - 4*u**3 - 1) #beta factors as (u - 3) * (u - 1) * u * (u + 1) * (u + 2) * (u**2 - 6*u + 2) * (u**2 - 5*u - 5) * (u**2 - 5*u + 3) * (u**2 - 3*u - 9) * (u**2 - u - 3) * (u**2 - u - 1) * (u**2 + u - 1) * (u**3 - 4*u**2 - 6*u - 5) * (u**4 - 2*u**3 - 5*u**2 - 4*u - 1) #beta factors as (u - 3) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 8*u + 11) * (u**2 - 7*u + 2) * (u**2 - 5*u - 2) * (u**2 - 5*u + 5) * (u**2 - 4*u - 4) * (u**2 - 4*u - 1) * (u**2 - 2*u - 1) * (u**2 - u - 1) * (u**3 - 9*u**2 + 21*u - 15) * (u**4 - 8*u**3 + 8*u**2 + 12*u - 9) #beta factors as (u - 5) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 5*u + 5) * (u**2 - 3*u - 7) * (u**2 - 2*u - 4) * (u**2 - 2*u - 1) * (u**2 - u - 1) * (u**2 - 2) * (u**2 + u - 1) * (u**3 - 3*u**2 - 5*u - 2) * (u**3 - 2*u**2 - 2*u - 1) * (u**4 - 6*u**3 + 5*u**2 + 2*u - 1) * (u**4 - 5*u**3 + u**2 + 4) * (u**4 - 4*u**3 + 2) #beta factors as (u - 4) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 5*u + 2) * (u**2 - 2*u - 1) * (u**3 - 5*u**2 + 5*u - 7) * (u**3 - 4*u**2 + 3*u - 4) * (u**3 - 4*u**2 + 3*u - 1) * (u**3 - 3*u**2 + 2*u - 4) * (u**3 - 2*u**2 + 2*u - 2) * (u**3 + u + 1) * (u**4 - 4*u**3 - 2*u**2 - 4) * (u**5 - 5*u**4 + 5*u**3 - 11*u**2 + 6*u - 4) * (u**6 - 4*u**5 + 2*u**4 - 4*u**3 - u**2 + 4*u - 2) #beta factors as (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 4*u - 1) * (u**2 - 3*u - 5) * (u**2 - 3*u - 2) * (u**2 - 3*u + 1) * (u**2 - u - 1) * (u**3 - 6*u**2 + 10*u - 7) * (u**3 - 5*u**2 + 7*u - 5) * (u**3 - 3*u**2 + 2*u - 1) * (u**3 - u**2 + 1) * (u**4 - 5*u**3 + 4*u**2 - 1) * (u**4 - 4*u**3 + 3*u**2 + 2*u - 4) * (u**4 - 3*u**3 - u - 1) * (u**4 - u**3 + 2*u - 1) * (u**5 - 6*u**4 + 10*u**3 - 11*u**2 + 8*u - 4) * (u**6 - 5*u**5 + 5*u**4 - 5*u**2 + 5*u - 5) #beta factors as (u - 3) * (u - 2) * (u - 1) * u * (u + 1) * (u**2 - 5*u + 5) * (u**2 - 3*u + 1) * (u**2 - 2*u - 1) * (u**2 - u - 1) * (u**3 - 5*u**2 + 5*u - 3) * (u**3 - 4*u**2 - 1) * (u**3 - 2*u**2 - 1) * (u**4 - 6*u**3 + 7*u**2 + 6*u - 9) * (u**4 - 5*u**3 + 4*u**2 + u + 3) * (u**4 - 5*u**3 + 6*u**2 - 3*u + 5) * (u**4 - 4*u**3 + u**2 - 4*u + 1) * (u**4 - 4*u**3 + 2*u**2 - u + 1) * (u**4 - 2*u**3 - 3*u**2 - 2*u - 1) * (u**4 - 2*u**3 + u - 1) * (u**6 - 5*u**5 + 8*u**4 - 7*u**3 + 6*u**2 - 3*u + 1) * (u**8 - 6*u**7 + 9*u**6 - 2*u**5 + 2*u**3 - 9*u**2 + 2*u - 1)
def Psi2(l): """ Returns the generic kernel polynomial for hyperelliptic `l`-isogenies.
INPUT:
- ``l`` -- either 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
OUTPUT:
The generic `l`-kernel polynomial.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2 sage: Psi2(11) x^5 - 55*x^4*u + 994*x^3*u^2 - 8774*x^2*u^3 + 41453*x*u^4 - 928945/11*u^5 + 33*x^4 + 276*x^3*u - 7794*x^2*u^2 + 4452*x*u^3 + 1319331/11*u^4 + 216*x^3*v - 4536*x^2*u*v + 31752*x*u^2*v - 842616/11*u^3*v + 162*x^3 + 38718*x^2*u - 610578*x*u^2 + 33434694/11*u^3 - 4536*x^2*v + 73872*x*u*v - 2745576/11*u^2*v - 16470*x^2 + 580068*x*u - 67821354/11*u^2 - 185976*x*v + 14143896/11*u*v + 7533*x - 20437029/11*u - 12389112/11*v + 19964151/11 sage: Psi2(71) # long time (1 second) -2209380711722505179506258739515288584116147237393815266468076436521/71*u^210 + ... - 14790739586438315394567393301990769678157425619440464678252277649/71
TESTS::
sage: Psi2(13) Traceback (most recent call last): ... ValueError: 13 must be one of [11, 17, 19, 23, 29, 31, 41, 47, 59, 71]. """
""" Returns list of ``l`` -isogenies with domain ``E``.
INPUT:
- ``E`` -- an elliptic curve.
- ``l`` -- either None or 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
OUTPUT:
(list) When ``l`` is None a list of all isogenies of degree 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71, otherwise a list of isogenies of the given degree.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``, which automatically calls the appropriate function.
ALGORITHM:
See [KT2013]_, Chapter 5.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_plus_0
sage: E = EllipticCurve('121a1') sage: isogenies_prime_degree_genus_plus_0(E, 11) [Isogeny of degree 11 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 30*x - 76 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 305*x + 7888 over Rational Field]
sage: E = EllipticCurve([1, 1, 0, -660, -7600]) sage: isogenies_prime_degree_genus_plus_0(E, 17) [Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 660*x - 7600 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 - 878710*x + 316677750 over Rational Field]
sage: E = EllipticCurve([0, 0, 1, -1862, -30956]) sage: isogenies_prime_degree_genus_plus_0(E, 19) [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field]
sage: K = QuadraticField(-295,'a') sage: a = K.gen() sage: E = EllipticCurve_from_j(-484650135/16777216*a + 4549855725/16777216) sage: isogenies_prime_degree_genus_plus_0(E, 23) [Isogeny of degree 23 from Elliptic Curve defined by y^2 = x^3 + (-14460494784192904095/140737488355328*a+270742665778826768325/140737488355328)*x + (37035998788154488846811217135/590295810358705651712*a-1447451882571839266752561148725/590295810358705651712) over Number Field in a with defining polynomial x^2 + 295 to Elliptic Curve defined by y^2 = x^3 + (-5130542435555445498495/140737488355328*a+173233955029127361005925/140737488355328)*x + (-1104699335561165691575396879260545/590295810358705651712*a+3169785826904210171629535101419675/590295810358705651712) over Number Field in a with defining polynomial x^2 + 295]
sage: K = QuadraticField(-199,'a') sage: a = K.gen() sage: E = EllipticCurve_from_j(94743000*a + 269989875) sage: isogenies_prime_degree_genus_plus_0(E, 29) [Isogeny of degree 29 from Elliptic Curve defined by y^2 = x^3 + (-153477413215038000*a+5140130723072965125)*x + (297036215130547008455526000*a+2854277047164317800973582250) over Number Field in a with defining polynomial x^2 + 199 to Elliptic Curve defined by y^2 = x^3 + (251336161378040805000*a-3071093219933084341875)*x + (-8411064283162168580187643221000*a+34804337770798389546017184785250) over Number Field in a with defining polynomial x^2 + 199]
sage: K = QuadraticField(253,'a') sage: a = K.gen() sage: E = EllipticCurve_from_j(208438034112000*a - 3315409892960000) sage: isogenies_prime_degree_genus_plus_0(E, 31) [Isogeny of degree 31 from Elliptic Curve defined by y^2 = x^3 + (4146345122185433034677956608000*a-65951656549965037259634800640000)*x + (-18329111516954473474583425393698245080252416000*a+291542366110383928366510368064204147260129280000) over Number Field in a with defining polynomial x^2 - 253 to Elliptic Curve defined by y^2 = x^3 + (200339763852548615776123686912000*a-3186599019027216904280948275200000)*x + (7443671791411479629112717260182286294850207744000*a-118398847898864757209685951728838895495168655360000) over Number Field in a with defining polynomial x^2 - 253]
sage: E = EllipticCurve_from_j(GF(5)(1)) sage: isogenies_prime_degree_genus_plus_0(E, 41) [Isogeny of degree 41 from Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 5 to Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field of size 5, Isogeny of degree 41 from Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 5 to Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field of size 5]
sage: K = QuadraticField(5,'a') sage: a = K.gen() sage: E = EllipticCurve_from_j(184068066743177379840*a - 411588709724712960000) sage: isogenies_prime_degree_genus_plus_0(E, 47) # long time (4.3s) [Isogeny of degree 47 from Elliptic Curve defined by y^2 = x^3 + (454562028554080355857852049849975895490560*a-1016431595837124114668689286176511361024000)*x + (-249456798429896080881440540950393713303830363999480904280965120*a+557802358738710443451273320227578156598454035482869042774016000) over Number Field in a with defining polynomial x^2 - 5 to Elliptic Curve defined by y^2 = x^3 + (39533118442361013730577638493616965245992960*a-88398740199669828340617478832005245173760000)*x + (214030321479466610282320528611562368963830105830555363061803253760*a-478586348074220699687616322532666163722004497458452316582576128000) over Number Field in a with defining polynomial x^2 - 5]
sage: K = QuadraticField(-66827,'a') sage: a = K.gen() sage: E = EllipticCurve_from_j(-98669236224000*a + 4401720074240000) sage: isogenies_prime_degree_genus_plus_0(E, 59) # long time (25s, 2012) [Isogeny of degree 59 from Elliptic Curve defined by y^2 = x^3 + (2605886146782144762297974784000*a+1893681048912773634944634716160000)*x + (-116918454256410782232296183198067568744071168000*a+17012043538294664027185882358514011304812871680000) over Number Field in a with defining polynomial x^2 + 66827 to Elliptic Curve defined by y^2 = x^3 + (-19387084027159786821400775098368000*a-4882059104868154225052787156713472000)*x + (-25659862010101415428713331477227179429538847260672000*a-2596038148441293485938798119003462972840818381946880000) over Number Field in a with defining polynomial x^2 + 66827]
sage: E = EllipticCurve_from_j(GF(13)(5)) sage: isogenies_prime_degree_genus_plus_0(E, 71) # long time [Isogeny of degree 71 from Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 13 to Elliptic Curve defined by y^2 = x^3 + 10*x + 7 over Finite Field of size 13, Isogeny of degree 71 from Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 13 to Elliptic Curve defined by y^2 = x^3 + 10*x + 7 over Finite Field of size 13]
sage: E = EllipticCurve(GF(13),[0,1,1,1,0]) sage: isogenies_prime_degree_genus_plus_0(E) [Isogeny of degree 17 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 1 over Finite Field of size 13, Isogeny of degree 17 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 4 over Finite Field of size 13, Isogeny of degree 29 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 6 over Finite Field of size 13, Isogeny of degree 29 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 5*x + 6 over Finite Field of size 13, Isogeny of degree 41 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 4 over Finite Field of size 13, Isogeny of degree 41 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 5*x + 6 over Finite Field of size 13]
"""
raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
raise NotImplementedError("11, 17, 19, 23, 29, 31, 41, 47, 59, and 71-isogenies are not yet implemented in characteristic 2 and 3, and when the characteristic is the same as the degree of the isogeny.")
return isogenies_prime_degree_genus_plus_0_j0(E, l) return isogenies_prime_degree_genus_plus_0_j1728(E, l)
else:
""" Returns a list of hyperelliptic ``l`` -isogenies with domain ``E`` when `j(E)=0`.
INPUT:
- ``E`` -- an elliptic curve with j-invariant 0.
- ``l`` -- 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
OUTPUT:
(list) a list of all isogenies of degree 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
.. note::
This implementation requires that the characteristic is not 2, 3 or ``l``.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_plus_0_j0
sage: u = polygen(QQ) sage: K.<a> = NumberField(u^4+228*u^3+486*u^2-540*u+225) sage: E = EllipticCurve(K,[0,-121/5*a^3-20691/5*a^2-29403/5*a+3267]) sage: isogenies_prime_degree_genus_plus_0_j0(E,11) [Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + (-121/5*a^3-20691/5*a^2-29403/5*a+3267) over Number Field in a with defining polynomial x^4 + 228*x^3 + 486*x^2 - 540*x + 225 to Elliptic Curve defined by y^2 = x^3 + (-44286*a^2+178596*a-32670)*x + (-17863351/5*a^3+125072739/5*a^2-74353653/5*a-682803) over Number Field in a with defining polynomial x^4 + 228*x^3 + 486*x^2 - 540*x + 225, Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + (-121/5*a^3-20691/5*a^2-29403/5*a+3267) over Number Field in a with defining polynomial x^4 + 228*x^3 + 486*x^2 - 540*x + 225 to Elliptic Curve defined by y^2 = x^3 + (-3267*a^3-740157*a^2+600039*a-277695)*x + (-17863351/5*a^3-4171554981/5*a^2+3769467867/5*a-272366523) over Number Field in a with defining polynomial x^4 + 228*x^3 + 486*x^2 - 540*x + 225]
sage: E = EllipticCurve(GF(5^6,'a'),[0,1]) sage: isogenies_prime_degree_genus_plus_0_j0(E,17) [Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 5^6 to Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field in a of size 5^6] """ raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes)) raise ValueError(("j-invariant must be 0.")) raise NotImplementedError("Not implemented in characteristic 2, 3 or l.")
p = F(-3).sqrt() endo = Fxuv(data['endo']) kernels += [endo(36*X+3*b2,p,-54*c6).monic(), endo(36*X+3*b2,-p,-54*c6).monic()]
continue else: return []
""" Returns a list of ``l`` -isogenies with domain ``E`` when `j(E)=1728`.
INPUT:
- ``E`` -- an elliptic curve with j-invariant 1728.
- ``l`` -- 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
OUTPUT:
(list) a list of all isogenies of degree 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
.. note::
This implementation requires that the characteristic is not 2, 3 or ``l``.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_plus_0_j1728
sage: u = polygen(QQ) sage: K.<a> = NumberField(u^6 - 522*u^5 - 10017*u^4 + 2484*u^3 - 5265*u^2 + 12150*u - 5103) sage: E = EllipticCurve(K,[-75295/1335852*a^5+13066735/445284*a^4+44903485/74214*a^3+17086861/24738*a^2+11373021/16492*a-1246245/2356,0]) sage: isogenies_prime_degree_genus_plus_0_j1728(E,11) [Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + (-75295/1335852*a^5+13066735/445284*a^4+44903485/74214*a^3+17086861/24738*a^2+11373021/16492*a-1246245/2356)*x over Number Field in a with defining polynomial x^6 - 522*x^5 - 10017*x^4 + 2484*x^3 - 5265*x^2 + 12150*x - 5103 to Elliptic Curve defined by y^2 = x^3 + (9110695/1335852*a^5-1581074935/445284*a^4-5433321685/74214*a^3-3163057249/24738*a^2+1569269691/16492*a+73825125/2356)*x + (-3540460*a^3+30522492*a^2-7043652*a-5031180) over Number Field in a with defining polynomial x^6 - 522*x^5 - 10017*x^4 + 2484*x^3 - 5265*x^2 + 12150*x - 5103, Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + (-75295/1335852*a^5+13066735/445284*a^4+44903485/74214*a^3+17086861/24738*a^2+11373021/16492*a-1246245/2356)*x over Number Field in a with defining polynomial x^6 - 522*x^5 - 10017*x^4 + 2484*x^3 - 5265*x^2 + 12150*x - 5103 to Elliptic Curve defined by y^2 = x^3 + (9110695/1335852*a^5-1581074935/445284*a^4-5433321685/74214*a^3-3163057249/24738*a^2+1569269691/16492*a+73825125/2356)*x + (3540460*a^3-30522492*a^2+7043652*a+5031180) over Number Field in a with defining polynomial x^6 - 522*x^5 - 10017*x^4 + 2484*x^3 - 5265*x^2 + 12150*x - 5103] sage: i = QuadraticField(-1,'i').gen() sage: E = EllipticCurve([-1-2*i,0]) sage: isogenies_prime_degree_genus_plus_0_j1728(E,17) [Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + (-2*i-1)*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + (-82*i-641)*x over Number Field in i with defining polynomial x^2 + 1, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + (-2*i-1)*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + (-562*i+319)*x over Number Field in i with defining polynomial x^2 + 1] sage: Emin = E.global_minimal_model() sage: [(p,len(isogenies_prime_degree_genus_plus_0_j1728(Emin,p))) for p in [17, 29, 41]] [(17, 2), (29, 2), (41, 2)] """ raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes)) raise ValueError("j-invariant must be 1728.") raise NotImplementedError("Not implemented in characteristic 2, 3 or l.")
S += [[u0,v0] for v0 in (X**2-f(u0)).roots(multiplicities=False)] else: return []
def _least_semi_primitive(p): """ Returns the smallest semi-primitive root modulo `p`, i.e., generator of the group `(\ZZ/p\ZZ)^*/\{1,-1\}`.
INPUT:
- ``p`` -- an odd prime.
OUTPUT:
the smallest semi-primitive root modulo `p`.
.. note::
This function would normally be invoked indirectly via ``E.isogenies_prime_degree_general(l)``.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import _least_semi_primitive sage: _least_semi_primitive(5) 2 sage: _least_semi_primitive(13) 2 sage: _least_semi_primitive(17) 3 sage: _least_semi_primitive(73) 5 sage: _least_semi_primitive(997) 7 """ raise ValueError("%s is not an odd prime"%p)
else: return d >= (p-1)/2
""" Returns a list of ``l`` -isogenies with domain ``E``.
INPUT:
- ``E`` -- an elliptic curve.
- ``l`` -- a prime.
OUTPUT:
(list) a list of all isogenies of degree l.
ALGORITHM:
This algorithm factors the ``l``-division polynomial, then combines its factors to obtain kernels. See [KT2013]_, Chapter 3.
.. note::
This function works for any prime `l`. Normally one should use the function :meth:`isogenies_prime_degree` which uses special functions for certain small primes.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general sage: E = EllipticCurve_from_j(GF(2^6,'a')(1)) sage: isogenies_prime_degree_general(E, 7) [Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 1 over Finite Field in a of size 2^6 to Elliptic Curve defined by y^2 + x*y = x^3 + x over Finite Field in a of size 2^6] sage: E = EllipticCurve_from_j(GF(3^12,'a')(2)) sage: isogenies_prime_degree_general(E, 17) [Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2 over Finite Field in a of size 3^12 to Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2*x over Finite Field in a of size 3^12, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2 over Finite Field in a of size 3^12 to Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 2 over Finite Field in a of size 3^12] sage: E = EllipticCurve('50a1') sage: isogenies_prime_degree_general(E, 3) [Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 126*x - 552 over Rational Field] sage: isogenies_prime_degree_general(E, 5) [Isogeny of degree 5 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 76*x + 298 over Rational Field] sage: E = EllipticCurve([0, 0, 1, -1862, -30956]) sage: isogenies_prime_degree_general(E, 19) [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field] sage: E = EllipticCurve([0, -1, 0, -6288, 211072]) sage: isogenies_prime_degree_general(E, 37) # long time (10s) [Isogeny of degree 37 from Elliptic Curve defined by y^2 = x^3 - x^2 - 6288*x + 211072 over Rational Field to Elliptic Curve defined by y^2 = x^3 - x^2 - 163137088*x - 801950801728 over Rational Field]
sage: E = EllipticCurve([-3440, 77658]) sage: isogenies_prime_degree_general(E, 43) # long time (16s) [Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 - 3440*x + 77658 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 6360560*x - 6174354606 over Rational Field]
Isogenies of degree equal to the characteristic are computed (but only the separable isogeny). In the following example we consider an elliptic curve which is supersingular in characteristic 2 only::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general sage: ainvs = (0,1,1,-1,-1) sage: for l in prime_range(50): ....: E = EllipticCurve(GF(l),ainvs) ....: isogenies_prime_degree_general(E,l) [] [Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 2*x + 2 over Finite Field of size 3 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 3] [Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 4*x + 4 over Finite Field of size 5 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 4*x + 4 over Finite Field of size 5] [Isogeny of degree 7 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 6*x + 6 over Finite Field of size 7 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 4 over Finite Field of size 7] [Isogeny of degree 11 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 10 over Finite Field of size 11 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + x + 1 over Finite Field of size 11] [Isogeny of degree 13 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 12 over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 12 over Finite Field of size 13] [Isogeny of degree 17 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 16*x + 16 over Finite Field of size 17 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 15 over Finite Field of size 17] [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 18*x + 18 over Finite Field of size 19 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 3*x + 12 over Finite Field of size 19] [Isogeny of degree 23 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 22*x + 22 over Finite Field of size 23 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 22*x + 22 over Finite Field of size 23] [Isogeny of degree 29 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 28*x + 28 over Finite Field of size 29 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 7*x + 27 over Finite Field of size 29] [Isogeny of degree 31 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 30*x + 30 over Finite Field of size 31 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 15*x + 16 over Finite Field of size 31] [Isogeny of degree 37 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 36*x + 36 over Finite Field of size 37 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 16*x + 17 over Finite Field of size 37] [Isogeny of degree 41 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 40*x + 40 over Finite Field of size 41 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 33*x + 16 over Finite Field of size 41] [Isogeny of degree 43 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 42*x + 42 over Finite Field of size 43 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 36 over Finite Field of size 43] [Isogeny of degree 47 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 46*x + 46 over Finite Field of size 47 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 42*x + 34 over Finite Field of size 47]
Note that not all factors of degree (l-1)/2 of the l-division polynomial are kernel polynomials. In this example, the 13-division polynomial factors as a product of 14 irreducible factors of degree 6 each, but only two those are kernel polynomials::
sage: F3 = GF(3) sage: E = EllipticCurve(F3,[0,0,0,-1,0]) sage: Psi13 = E.division_polynomial(13) sage: len([f for f,e in Psi13.factor() if f.degree()==6]) 14 sage: len(E.isogenies_prime_degree(13)) 2
Over GF(9) the other factors of degree 6 split into pairs of cubics which can be rearranged to give the remaining 12 kernel polynomials::
sage: len(E.change_ring(GF(3^2,'a')).isogenies_prime_degree(13)) 14
See :trac:`18589`: the following example took 20s before, now only 4s::
sage: K.<i> = QuadraticField(-1) sage: E = EllipticCurve(K,[0,0,0,1,0]) sage: [phi.codomain().ainvs() for phi in E.isogenies_prime_degree(37)] # long time [(0, 0, 0, -840*i + 1081, 0), (0, 0, 0, 840*i + 1081, 0)] """ raise ValueError("%s is not prime."%l)
# Every kernel polynomial is a product of irreducible factors of # the division polynomial of the same degree, where this degree is # a divisor of (l-1)/2, so we keep only such factors:
for d in l2.divisors()])
# If for some d dividing (l-1)/2 there are exactly (l-1)/2d # divisors of degree d, then their product is a kernel poly, which # we add to the list and remove the factors used.
# Exit now if all factors have been used already:
# In general we look for products of factors of the same degree d # which can be kernel polynomials
# This function permutes the factors of a given degree, replacing # the factor with roots alpha with the one whose roots are # m(alpha), where m(x) is the rational function giving the # multiplication-by-a map on the X-coordinates. Here, a is a # generator for (Z/lZ)^* / <-1> (a so-called semi-primitive root). # Find f such that f(m) = 0 mod g
# kernel polynomials are the products of factors of degree d in # one orbit under mult, provided that the orbit has length # (l-1)/2d. Otherwise the orbit will be longer. # Compute an orbit under mult: # Check orbit length:
""" Returns a list of ``l`` -isogenies with domain ``E``.
INPUT:
- ``E`` -- an elliptic curve.
- ``l`` -- a prime.
OUTPUT:
(list) a list of all isogenies of degree `l`. If the characteristic is `l` then only separable isogenies are constructed.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree sage: E = EllipticCurve_from_j(GF(2^6,'a')(1)) sage: isogenies_prime_degree(E, 7) [Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 1 over Finite Field in a of size 2^6 to Elliptic Curve defined by y^2 + x*y = x^3 + x over Finite Field in a of size 2^6] sage: E = EllipticCurve_from_j(GF(3^12,'a')(2)) sage: isogenies_prime_degree(E, 17) [Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2 over Finite Field in a of size 3^12 to Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2*x over Finite Field in a of size 3^12, Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2 over Finite Field in a of size 3^12 to Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 2 over Finite Field in a of size 3^12] sage: E = EllipticCurve('50a1') sage: isogenies_prime_degree(E, 3) [Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 126*x - 552 over Rational Field] sage: isogenies_prime_degree(E, 5) [Isogeny of degree 5 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x - 2 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - 76*x + 298 over Rational Field] sage: E = EllipticCurve([0, 0, 1, -1862, -30956]) sage: isogenies_prime_degree(E, 19) [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 - 1862*x - 30956 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 672182*x + 212325489 over Rational Field] sage: E = EllipticCurve([0, -1, 0, -6288, 211072]) sage: isogenies_prime_degree(E, 37) [Isogeny of degree 37 from Elliptic Curve defined by y^2 = x^3 - x^2 - 6288*x + 211072 over Rational Field to Elliptic Curve defined by y^2 = x^3 - x^2 - 163137088*x - 801950801728 over Rational Field]
Isogenies of degree equal to the characteristic are computed (but only the separable isogeny). In the following example we consider an elliptic curve which is supersingular in characteristic 2 only::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree sage: ainvs = (0,1,1,-1,-1) sage: for l in prime_range(50): ....: E = EllipticCurve(GF(l),ainvs) ....: isogenies_prime_degree(E,l) [] [Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 2*x + 2 over Finite Field of size 3 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + x over Finite Field of size 3] [Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 4*x + 4 over Finite Field of size 5 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 4*x + 4 over Finite Field of size 5] [Isogeny of degree 7 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 6*x + 6 over Finite Field of size 7 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 4 over Finite Field of size 7] [Isogeny of degree 11 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 10 over Finite Field of size 11 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + x + 1 over Finite Field of size 11] [Isogeny of degree 13 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 12 over Finite Field of size 13 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 12*x + 12 over Finite Field of size 13] [Isogeny of degree 17 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 16*x + 16 over Finite Field of size 17 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 15 over Finite Field of size 17] [Isogeny of degree 19 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 18*x + 18 over Finite Field of size 19 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 3*x + 12 over Finite Field of size 19] [Isogeny of degree 23 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 22*x + 22 over Finite Field of size 23 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 22*x + 22 over Finite Field of size 23] [Isogeny of degree 29 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 28*x + 28 over Finite Field of size 29 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 7*x + 27 over Finite Field of size 29] [Isogeny of degree 31 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 30*x + 30 over Finite Field of size 31 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 15*x + 16 over Finite Field of size 31] [Isogeny of degree 37 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 36*x + 36 over Finite Field of size 37 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 16*x + 17 over Finite Field of size 37] [Isogeny of degree 41 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 40*x + 40 over Finite Field of size 41 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 33*x + 16 over Finite Field of size 41] [Isogeny of degree 43 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 42*x + 42 over Finite Field of size 43 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 36 over Finite Field of size 43] [Isogeny of degree 47 from Elliptic Curve defined by y^2 + y = x^3 + x^2 + 46*x + 46 over Finite Field of size 47 to Elliptic Curve defined by y^2 + y = x^3 + x^2 + 42*x + 34 over Finite Field of size 47]
Note that the computation is faster for degrees equal to one of the genus 0 primes (2, 3, 5, 7, 13) or one of the hyperelliptic primes (11, 17, 19, 23, 29, 31, 41, 47, 59, 71) than when the generic code must be used::
sage: E = EllipticCurve(GF(101), [-3440, 77658]) sage: E.isogenies_prime_degree(71) # fast [] sage: E.isogenies_prime_degree(73) # not tested (very long time: 32s) [] """
|