CoCalc -- isogeny_small

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
⁸⁸²⁰ views
1
r"""
2
Isogenies of small prime degree.
3

4
Functions for the computation of isogenies of small primes
5
degree. First: `l` = 2, 3, 5, 7, or 13, where the modular curve
6
`X_0(l)` has genus 0.  Second: `l` = 11, 17, 19, 23, 29, 31, 41, 47,
7
59, or 71, where `X_0^+(l)` has genus 0 and `X_0(l)` is elliptic or
8
hyperelliptic.  Also: `l` = 11, 17, 19, 37, 43, 67 or 163 over `\QQ`
9
(the sporadic cases with only finitely many `j`-invariants each).  All
10
the above only require factorization of a polynomial of degree `l+1`.
11
Finally, a generic function which works for arbitrary odd primes `l`
12
(including the characteristic), but requires factorization of the
13
`l`-division polynomial, of degree `(l^2-1)/2`.
14

15

16
AUTHORS:
17

18
- John Cremona and Jenny Cooley: 2009-07..11: the genus 0 cases the sporadic cases over `\QQ`.
19

20
- Kimi Tsukazaki and John Cremona: 2013-07: The 10 (hyper)-elliptic
21
  cases and the generic algorithm.  See [KT2013]_.
22

23
REFERENCES:
24

25
.. [CW2005] J. E. Cremona and M. Watkins. Computing isogenies of elliptic curves. preprint, 2005.
26
.. [KT2013] K. Tsukazaki, Explicit Isogenies of Elliptic Curves,
27
   PhD thesis, University of Warwick, 2013.
28

29

30
"""
31

32
#*****************************************************************************
33
#       Copyright (C) 2012-2013 John Cremona, Jenny Cooley, Kimi Tsukazaki
34
#
35
#  Distributed under the terms of the GNU General Public License (GPL)
36
#  as published by the Free Software Foundation; either version 2 of
37
#  the License, or (at your option) any later version.
38
#                  http://www.gnu.org/licenses/
39
#*****************************************************************************
40

41
from sage.categories import homset
42

43
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
44
from sage.rings.polynomial.polynomial_ring import polygen
45
from sage.rings.all import Integer, ZZ, QQ
46
from sage.schemes.elliptic_curves.all import EllipticCurve
47

48
from sage.misc.cachefunc import cached_function
49

50
##########################################################################
51
# The following section is all about computing l-isogenies, where l is
52
# a prime.  The genus 0 cases `l` = 2, 3, 5, 7 and 13 are
53
# implemented over any field of characteristic not 2, 3 or `l`; over
54
# `\QQ` the "sporadic" cases `l` = 11, 17, 19, 37, 43, 67 or 163 with
55
# only finitely many `j`-invariants each. are also implemented.
56
##########################################################################
57

58
@cached_function
59
def Fricke_polynomial(l):
60
    r"""
61
    Fricke polynomial for ``l`` =2,3,5,7,13.
62

63
    For these primes (and these only) the modular curve `X_0(l)` has
64
    genus zero, and its field is generated by a single modular
65
    function called the Fricke module (or Hauptmodul), `t`.  There is
66
    a classical choice of such a generator `t` in each case, and the
67
    `j`-function is a rational function of `t` of degree `l+1` of the
68
    form `P(t)/t` where `P` is a polynomial of degree `l+1`.  Up to
69
    scaling, `t` is determined by the condition that the ramification
70
    points above `j=\infty` are `t=0` (with ramification degree `1`)
71
    and `t=\infty` (with degree `l`).  The ramification above `j=0`
72
    and `j=1728` may be seen in the factorizations of `j(t)` and
73
    `k(t)` where `k=j-1728`.
74

75
    OUTPUT:
76

77
    The polynomial `P(t)` as an element of `\ZZ[t]`.
78

79
    TESTS::
80

81
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Fricke_polynomial
82
        sage: Fricke_polynomial(2)
83
        t^3 + 48*t^2 + 768*t + 4096
84
        sage: Fricke_polynomial(3)
85
        t^4 + 36*t^3 + 270*t^2 + 756*t + 729
86
        sage: Fricke_polynomial(5)
87
        t^6 + 30*t^5 + 315*t^4 + 1300*t^3 + 1575*t^2 + 750*t + 125
88
        sage: Fricke_polynomial(7)
89
        t^8 + 28*t^7 + 322*t^6 + 1904*t^5 + 5915*t^4 + 8624*t^3 + 4018*t^2 + 748*t + 49
90
        sage: Fricke_polynomial(13)
91
        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
92
    """
93
    Zt = PolynomialRing(ZZ,'t')
94
    t = Zt.gen()
95
    if l==2: return (t+16)**3
96
    elif l==3: return (t+3)**3*(t+27)
97
    elif l==5: return (t**2+10*t+5)**3
98
    elif l==7: return (t**2+5*t+1)**3 * (t**2+13*t+49)
99
    elif l==13: return (t**2+5*t+13)*(t**4+7*t**3+20*t**2+19*t+1)**3
100
    else:
101
        raise ValueError("The only genus zero primes are 2, 3, 5, 7 or 13.")
102

103
@cached_function
104
def Fricke_module(l):
105
    r"""
106
    Fricke module for ``l`` =2,3,5,7,13.
107

108
    For these primes (and these only) the modular curve `X_0(l)` has
109
    genus zero, and its field is generated by a single modular
110
    function called the Fricke module (or Hauptmodul), `t`.  There is
111
    a classical choice of such a generator `t` in each case, and the
112
    `j`-function is a rational function of `t` of degree `l+1` of the
113
    form `P(t)/t` where `P` is a polynomial of degree `l+1`.  Up to
114
    scaling, `t` is determined by the condition that the ramification
115
    points above `j=\infty` are `t=0` (with ramification degree `1`)
116
    and `t=\infty` (with degree `l`).  The ramification above `j=0`
117
    and `j=1728` may be seen in the factorizations of `j(t)` and
118
    `k(t)` where `k=j-1728`.
119

120
    OUTPUT:
121

122
    The rational function `P(t)/t`.
123

124
    TESTS::
125

126
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Fricke_module
127
        sage: Fricke_module(2)
128
        (t^3 + 48*t^2 + 768*t + 4096)/t
129
        sage: Fricke_module(3)
130
        (t^4 + 36*t^3 + 270*t^2 + 756*t + 729)/t
131
        sage: Fricke_module(5)
132
        (t^6 + 30*t^5 + 315*t^4 + 1300*t^3 + 1575*t^2 + 750*t + 125)/t
133
        sage: Fricke_module(7)
134
        (t^8 + 28*t^7 + 322*t^6 + 1904*t^5 + 5915*t^4 + 8624*t^3 + 4018*t^2 + 748*t + 49)/t
135
        sage: Fricke_module(13)
136
        (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
137
    """
138
    try:
139
        t = PolynomialRing(QQ,'t').gen()
140
        return Fricke_polynomial(l) / t
141
    except ValueError:
142
        raise ValueError("The only genus zero primes are 2, 3, 5, 7 or 13.")
143

144
@cached_function
145
def Psi(l, use_stored=True):
146
    r"""
147
    Generic kernel polynomial for genus zero primes.
148

149
    For each of the primes `l` for which `X_0(l)` has genus zero
150
    (namely `l=2,3,5,7,13`), we may define an elliptic curve `E_t`
151
    over `\QQ(t)`, with coefficients in `\ZZ[t]`, which has good
152
    reduction except at `t=0` and `t=\infty` (which lie above
153
    `j=\infty`) and at certain other values of `t` above `j=0` when
154
    `l=3` (one value) or `l\equiv1\pmod{3}` (two values) and above
155
    `j=1728` when `l=2` (one value) or `l\equiv1 \pmod{4}` (two
156
    values).  (These exceptional values correspond to endomorphisms of
157
    `E_t` of degree `l`.)  The `l`-division polynomial of `E_t` has a
158
    unique factor of degree `(l-1)/2` (or 1 when `l=2`), with
159
    coefficients in `\ZZ[t]`, which we call the Generic Kernel
160
    Polynomial for `l`.  These are used, by specialising `t`, in the
161
    function :meth:`isogenies_prime_degree_genus_0`, which also has to
162
    take into account the twisting factor between `E_t` for a specific
163
    value of `t` and the short Weierstrass form of an elliptic curve
164
    with `j`-invariant `j(t)`.  This enables the computation of the
165
    kernel polynomials of isogenies without having to compute and
166
    factor division polynomials.
167

168
    All of this data is quickly computed from the Fricke modules, except
169
    that for `l=13` the factorization of the Generic Division Polynomial
170
    takes a long time, so the value have been precomputed and cached; by
171
    default the cached values are used, but the code here will recompute
172
    them when ``use_stored`` is ``False``, as in the doctests.
173

174
    INPUT:
175

176
    - ``l`` -- either 2, 3, 5, 7, or 13.
177

178
    - ``use_stored`` (boolean, default True) -- If True, use
179
      precomputed values, otherwise compute them on the fly.
180

181
    .. note:
182

183
       This computation takes a negligible time for `l=2,3,5,7`
184
       but more than 100s for `l=13`.  The reason
185
       for allowing dynamic computation here instead of just using
186
       precomputed values is for testing.
187

188
    TESTS::
189

190
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Fricke_module, Psi
191
        sage: assert Psi(2, use_stored=True) == Psi(2, use_stored=False)
192
        sage: assert Psi(3, use_stored=True) == Psi(3, use_stored=False)
193
        sage: assert Psi(5, use_stored=True) == Psi(5, use_stored=False)
194
        sage: assert Psi(7, use_stored=True) == Psi(7, use_stored=False)
195
        sage: assert Psi(13, use_stored=True) == Psi(13, use_stored=False) # not tested (very long time)
196
    """
197
    if not l in [2,3,5,7,13]:
198
        raise ValueError("Genus zero primes are 2, 3, 5, 7 or 13.")
199

200
    R = PolynomialRing(ZZ,2,'Xt')
201
    X,t = R.gens()
202

203
    if use_stored:
204
        if l==2:
205
            return X + t + 64
206
        if l==3:
207
            return X + t + 27
208
        if l==5:
209
            return X**2 + 2*X*(t**2 + 22*t + 125)+ (t**2 + 22*t + 89) * (t**2 + 22*t + 125)
210
        if l==7:
211
            return (X**3 + 3*(t**2 + 13*t + 49)*X**2
212
                    + 3*(t**2 + 13*t + 33)*(t**2 + 13*t + 49)*X
213
                    + (t**2 + 13*t + 49)*(t**4 + 26*t**3 + 219*t**2 + 778*t + 881))
214
        if l==13:
215
            return (t**24 + 66*t**23 + 2091*t**22 + 6*X*t**20 + 42582*t**21 + 330*X*t**19 + 627603*t**20 + 8700*X*t**18 + 7134744*t**19 + 15*X**2*t**16 + 146886*X*t**17 + 65042724*t**18 + 660*X**2*t**15 + 1784532*X*t**16 + 487778988*t**17 + 13890*X**2*t**14 + 16594230*X*t**15 + 3061861065*t**16 + 20*X**3*t**12 + 186024*X**2*t**13 + 122552328*X*t**14 + 16280123754*t**15 + 660*X**3*t**11 + 1774887*X**2*t**12 + 735836862*X*t**13 + 73911331425*t**14 + 10380*X**3*t**10 + 12787272*X**2*t**11 + 3646188342*X*t**12 + 287938949178*t**13 + 15*X**4*t**8 + 102576*X**3*t**9 + 71909658*X**2*t**10 + 15047141292*X*t**11 + 964903805434*t**12 + 330*X**4*t**7 + 707604*X**3*t**8 + 321704316*X**2*t**9 + 51955096824*X*t**10 + 2781843718722*t**11 + 3435*X**4*t**6 + 3582876*X**3*t**7 + 1155971196*X**2*t**8 + 150205315932*X*t**9 + 6885805359741*t**10 + 6*X**5*t**4 + 21714*X**4*t**5 + 13632168*X**3*t**6 + 3343499244*X**2*t**7 + 362526695094*X*t**8 + 14569390179114*t**9 + 66*X**5*t**3 + 90660*X**4*t**4 + 39215388*X**3*t**5 + 7747596090*X**2*t**6 + 725403501318*X*t**7 + 26165223178293*t**8 + 336*X**5*t**2 + 255090*X**4*t**3 + 84525732*X**3*t**4 + 14206132008*X**2*t**5 + 1189398495432*X*t**6 + 39474479008356*t**7 + X**6 + 858*X**5*t + 472143*X**4*t**2 + 132886992*X**3*t**3 + 20157510639*X**2*t**4 + 1569568001646*X*t**5 + 49303015587132*t**6 + 1014*X**5 + 525954*X**4*t + 144222780*X**3*t**2 + 21320908440*X**2*t**3 + 1622460290100*X*t**4 + 49941619724976*t**5 + 272259*X**4 + 96482100*X**3*t + 15765293778*X**2*t**2 + 1260038295438*X*t**3 + 39836631701295*t**4 + 29641924*X**3 + 7210949460*X**2*t + 686651250012*X*t**2 + 23947528862166*t**3 + 1506392823*X**2 + 231462513906*X*t + 10114876838391*t**2 + 35655266790*X + 2644809206442*t + 317295487717)
216
# The coefficients for l=13 are:
217
# X**6: 1
218
# X**5: (6) * (t**2 + 5*t + 13) * (t**2 + 6*t + 13)
219
# 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)
220
# 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)
221
# 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)
222
# 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)
223
# 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)
224
#
225

226
    # Here the generic kernel polynomials are actually calculated:
227
    j = Fricke_module(l)
228
    k = j-1728
229
    from sage.misc.all import prod
230
    f = prod( [p for p,e in j.factor() if e==3]
231
             +[p for p,e in k.factor() if e==2])
232
    A4 = -3*t**2*j*k // f**2
233
    A6 = -2*t**3*j*k**2 // f**3
234
    E = EllipticCurve([0,0,0,A4,A6])
235
    assert E.j_invariant() == j
236
    return E.division_polynomial(l,X).factor()[0][0]
237

238

239
def isogenies_prime_degree_genus_0(E, l=None):
240
    """
241
    Returns list of ``l`` -isogenies with domain ``E``.
242

243
    INPUT:
244

245
    - ``E`` -- an elliptic curve.
246

247
    - ``l`` -- either None or 2, 3, 5, 7, or 13.
248

249
    OUTPUT:
250

251
    (list) When ``l`` is None a list of all isogenies of degree 2, 3,
252
    5, 7 and 13, otherwise a list of isogenies of the given degree.
253

254
    .. note::
255

256
       This function would normally be invoked indirectly via
257
       ``E.isogenies_prime_degree(l)``, which automatically calls the
258
       appropriate function.
259

260
    ALGORITHM:
261

262
    Cremona and Watkins [CW2005]_. See also [KT2013]_, Chapter 4.
263

264
    EXAMPLES::
265

266
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_0
267
        sage: E = EllipticCurve([0,12])
268
        sage: isogenies_prime_degree_genus_0(E, 5)
269
        []
270

271
        sage: E = EllipticCurve('1450c1')
272
        sage: isogenies_prime_degree_genus_0(E)
273
        [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]
274

275
        sage: E = EllipticCurve('50a1')
276
        sage: isogenies_prime_degree_genus_0(E)
277
        [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,
278
        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]
279
    """
280
    if not l in [2, 3, 5, 7, 13, None]:
281
        raise ValueError("%s is not a genus 0 prime."%l)
282
    F = E.base_ring()
283
    j = E.j_invariant()
284
    if F.characteristic() in [2, 3, l]:
285
        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.")
286
    if l==2:
287
        return isogenies_2(E)
288
    if l==3:
289
        return isogenies_3(E)
290
    if j==F(0):
291
        if l==5:
292
            return isogenies_5_0(E)
293
        if l==7:
294
            return isogenies_7_0(E)
295
        if l==13:
296
            return isogenies_13_0(E)
297
    if j==F(1728):
298
        if l==5:
299
            return isogenies_5_1728(E)
300
        if l==7:
301
            return isogenies_7_1728(E)
302
        if l==13:
303
            return isogenies_13_1728(E)
304

305
    if l != None:
306
        R = PolynomialRing(F,'t')
307
        t = R.gen()
308
        f = R(Fricke_polynomial(l))
309
        t_list = (f-j*t).roots(multiplicities=False)
310
        t_list.sort()
311
        # The generic kernel polynomial applies to a standard curve
312
        # E_t with the correct j-invariant; we must compute the
313
        # appropriate twising factor to scale X by:
314
        c4, c6 = E.c_invariants()
315
        T = c4/(3*c6)
316
        jt = Fricke_module(l)
317
        kt = jt-1728
318
        from sage.misc.all import prod
319
        psi = Psi(l)
320
        X = t
321
        f = R(prod( [p for p,e in jt.factor() if e==3]
322
                 +[p for p,e in kt.factor() if e==2]))
323
        kernels = [R(psi(X*T*(j-1728)*t0/f(t0),t0)) for t0 in t_list]
324
        kernels = [ker.monic() for ker in kernels]
325
        E1 = EllipticCurve([-27*c4,-54*c6])
326
        w = E.isomorphism_to(E1)
327
        model = "minimal" if F is QQ else None
328
        isogs = [E1.isogeny(kernel=ker, model=model) for ker in kernels]
329
        [isog.set_pre_isomorphism(w) for isog in isogs]
330
        return isogs
331

332
    if l == None:
333
        return sum([isogenies_prime_degree_genus_0(E, l) for l in [2,3,5,7,13]],[])
334

335

336
# The following code computes data to be used in
337
# isogenies_sporadic_Q. Over Q there are only finitely many
338
# j-invariants of curves with l-isogenies where l is not equal to 2,
339
# 3, 5, 7 or 13. In these cases l is equal to 11, 17, 19, 37, 43, 67
340
# or 163. We refer to these l as "sporadic".
341

342
# sporadic_j is a dictionary holding for each possible sporadic
343
# j-invariant, the unique l such that an l-isogeny exists.
344
sporadic_j = {
345
    QQ(-121)                : 11,
346
    QQ(-32768)              : 11,
347
    QQ(-24729001)           : 11,
348
    QQ(-297756989)/2        : 17,
349
    QQ(-882216989)/131072   : 17,
350
    QQ(-884736)             : 19,
351
    QQ(-9317)               : 37,
352
    QQ(-162677523113838677) : 37,
353
    QQ(-884736000)          : 43,
354
    QQ(-147197952000)       : 67,
355
    QQ(-262537412640768000) : 163
356
    }
357

358
@cached_function
359
def _sporadic_Q_data(j):
360
    """
361
    Returns technical data used in computing sporadic isogenies over `\QQ`.
362

363
    INPUT:
364

365
    - ``j`` -- The `j`-invariant of a sporadic curve, i.e. one of the
366
      keys of ``sporadic_j``.
367

368
    OUTPUT:
369

370
    ``([a4,a6],coeffs)`` where ``[a4,a6]`` are the coefficients of a
371
    short Weierstrass equation of an elliptic curve E with j(E)=``j``,
372
    and ``coeffs`` is a list of coefficients of a polynomial defining
373
    the kernel of an l-isogeny from E.
374

375
    Whenever we have a curve of j-invariant ``j``, we can compute the
376
    corresponding l-isogeny by just scaling ``coeffs`` by the right
377
    twisting factor and using the result as a kernel-polynomial.
378

379
    ALGORITHM:
380

381
    For small l it works fine to factor the l-division polynomial, but
382
    this takes a long time for the larger l and is a very bad idea for
383
    l=163; hence we use floating point arithmetic with a precision
384
    which is known to work.  This idea was suggested by Samir Siksek.
385

386
    TESTS::
387

388
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import sporadic_j, _sporadic_Q_data
389
        sage: [_sporadic_Q_data(j) for j in sorted(sporadic_j.keys()) if j != -262537412640768000]
390
        [([-269675595, -1704553285050],
391
          [-855506888466179262477032094260950275409164148942611063430052125977143159,
392
           -1469048260972089939455942042937882262144594798448952781325533511718750,
393
           -1171741935131505774747142644126089902595908234671576131857702734375,
394
           -574934780393177024547076427530739751753985644656221274606250000,
395
           -193516922725803688001809624711400287605136013195315374687500,
396
           -47085563820928456130325308223963045033502182349693125000,
397
           -8472233937388712980597845725196873697064639957437500,
398
           -1124815211213953261752081095348112305023653750000,
399
           -105684015609077608033913080859605951322531250,
400
           -5911406027236569746089675554748135312500,
401
           22343907270397352965399097794968750,
402
           43602171843758666292581116410000,
403
           5054350766002463251474186500,
404
           350135768194635636171000,
405
           16633063574896677300,
406
           549939627039600,
407
           12182993865,
408
           163170,
409
           1]),
410
         ([-117920, 15585808],
411
          [426552448394636714720553816389274308035895411389805883034985546818882031845376,
412
           -55876556222880738651382959148329502876096075327084935039031884373558741172224,
413
           3393295715290183821010552313572221545212247684503012173117764703828786020352,
414
           -125729166452196578653551230178028570067747190427221869867485520072257044480,
415
           3121342502030777257351089270834971957072933779704445667351054593298530304,
416
           -52544031605544530265465344472543470442324636919759253720520768014516224,
417
           532110915869155495738137756847596184665209453108323879594125221167104,
418
           -399031158106622651277981701966309467713625045637309782055519780864,
419
           -101914346170769215732007802723651742508893380955930030421292613632,
420
           2296526155500449624398016447877283594461904009374321659789443072,
421
           -31950871094301541469458501953701002806003991982768349794795520,
422
           329792235011603804948028315065667439678526339671142107709440,
423
           -2655636715955021784085217734679612378726442691190553837568,
424
           16825164648840434987220620681420687654501026066872664064,
425
           -81705027839007003131400500185224450729843244954288128,
426
           273656504606483403474090105104132405333665144373248,
427
           -320807702482945680116212224172370503903312084992,
428
           -3166683390779345463318656135338172047199043584,
429
           27871349428383710305216046431806697565585408,
430
           -132774697798318602604125735604528772808704,
431
           436096215568182871014215818309741314048,
432
           -964687143341252402362763535357837312,
433
           942144169187362941776488535425024,
434
           2794850106281773765892648206336,
435
           -17236916236678037389276086272,
436
           50979778712911923486851072,
437
           -105035658611718440992768,
438
           161833913559276412928,
439
           -188675698610077696,
440
           163929317513984,
441
           -102098677888,
442
           42387952,
443
           -10184,
444
           1]),
445
         ([-13760, 621264],
446
          [-1961864562041980324821547425314935668736,
447
           784270445793223959453256359333693751296,
448
           -120528107728500223255333768387027271680,
449
           10335626145581464192664472924270362624,
450
           -568426570575654606865505142156820480,
451
           21261993723422650574629752537088000,
452
           -544630471727787626557612832587776,
453
           8870521306520473088172555763712,
454
           -54993059067301585878494740480,
455
           -1434261324709904840432549888,
456
           50978938193065926383894528,
457
           -845761855773797582372864,
458
           8627493611216601088000,
459
           -48299605284169187328,
460
           -32782260293713920,
461
           3415534989828096,
462
           -34580115625984,
463
           199359712512,
464
           -730488128,
465
           1658080,
466
           -2064,
467
           1]),
468
         ([-3940515, 3010787550],
469
          [-6458213126940667330314375,
470
           34699336325466068070000,
471
           -72461450055340471500,
472
           68342601718080000,
473
           -15140380554450,
474
           -25802960400,
475
           23981220,
476
           -8160,
477
           1]),
478
         ([-38907, -2953962], [-20349931239, -424530315, -134838, 53658, 429, 1]),
479
         ([-608, 5776],
480
          [-34162868224,
481
           -8540717056,
482
           6405537792,
483
           -1123778560,
484
           84283392,
485
           -2033152,
486
           -92416,
487
           6992,
488
           -152,
489
           1]),
490
         ([-9504, 365904], [1294672896, -92835072, 1463616, 7920, -264, 1]),
491
         ([-10395, 444150],
492
          [-38324677699334121599624973029296875,
493
           -17868327793500376961572310472656250,
494
           2569568362004197901139023084765625,
495
           -95128267987528547588017818750000,
496
           -822168183291347061312510937500,
497
           134395594560592096297190625000,
498
           -2881389756919344324888937500,
499
           -2503855007083401977250000,
500
           922779077075655997443750,
501
           -11503912310262102937500,
502
           -18237870962450291250,
503
           1457822151548910000,
504
           -10087015556047500,
505
           -13677678063000,
506
           490243338900,
507
           -2461460400,
508
           5198445,
509
           -4410,
510
           1]),
511
         ([-856035, -341748450],
512
          [103687510635057329105625,
513
           961598491955315190000,
514
           1054634146768300500,
515
           -6553122389064000,
516
           -14554350284850,
517
           -2046589200,
518
           13185540,
519
           8160,
520
           1]),
521
         ([-3267, -280962], [1480352841, -56169531, -2829222, 10890, 429, 1])]
522
    """
523
    from sage.rings.all import RealField
524
    from sage.misc.all import prod
525
    ell = sporadic_j[j]
526
    E = EllipticCurve(j=j).short_weierstrass_model()
527
    a4a6 = list(E.ainvs())[3:]
528
    L = E.period_lattice()
529
    pr = 100
530
    if ell==163:
531
        pr=1000
532
    elif ell>30:
533
        pr=300
534
    w1, w2 = L.basis(prec=pr)
535
    X = polygen(RealField(pr),'X')
536
    w = w1 # real period
537
    if j in [-121, -24729001, -162677523113838677, QQ(-882216989)/131072]:
538
        w = 2*w2-w1 # imaginary period
539
    kerpol = prod(([X-L.elliptic_exponential(n*w/ell)[0] for n in range(1,(ell+1)//2)]))
540
    kerpolcoeffs = [c.real().round() for c in list(kerpol)]
541
    return (a4a6,kerpolcoeffs)
542

543
def isogenies_sporadic_Q(E, l=None):
544
    """
545
    Returns list of ``l`` -isogenies with domain ``E`` (defined over `\QQ`).
546

547
    Returns a list of sporadic l-isogenies from E (l = 11, 17, 19, 37,
548
    43, 67 or 163). Only for elliptic curves over `\QQ`.
549

550
    INPUT:
551

552
    - ``E`` -- an elliptic curve defined over `\QQ`.
553

554
    - ``l`` -- either None or a prime number.
555

556
    OUTPUT:
557

558
    (list) If ``l`` is None, a list of all isogenies with domain ``E``
559
    and of degree 11, 17, 19, 37, 43, 67 or 163; otherwise a list of
560
    isogenies of the given degree.
561

562
    .. note::
563

564
       This function would normally be invoked indirectly via
565
       ``E.isogenies_prime_degree(l)``, which automatically calls the appropriate
566
       function.
567

568
    EXAMPLES::
569

570
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_sporadic_Q
571
        sage: E = EllipticCurve('121a1')
572
        sage: isogenies_sporadic_Q(E, 11)
573
        [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]
574
        sage: isogenies_sporadic_Q(E, 13)
575
        []
576
        sage: isogenies_sporadic_Q(E, 17)
577
        []
578
        sage: isogenies_sporadic_Q(E)
579
        [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]
580

581
        sage: E = EllipticCurve([1, 1, 0, -660, -7600])
582
        sage: isogenies_sporadic_Q(E, 17)
583
        [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]
584
        sage: isogenies_sporadic_Q(E)
585
        [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]
586
        sage: isogenies_sporadic_Q(E, 11)
587
        []
588

589
        sage: E = EllipticCurve([0, 0, 1, -1862, -30956])
590
        sage: isogenies_sporadic_Q(E, 11)
591
        []
592
        sage: isogenies_sporadic_Q(E, 19)
593
        [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]
594
        sage: isogenies_sporadic_Q(E)
595
        [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]
596

597
        sage: E = EllipticCurve([0, -1, 0, -6288, 211072])
598
        sage: E.conductor()
599
        19600
600
        sage: isogenies_sporadic_Q(E,37)
601
        [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]
602

603
        sage: E = EllipticCurve([1, 1, 0, -25178045, 48616918750])
604
        sage: E.conductor()
605
        148225
606
        sage: isogenies_sporadic_Q(E,37)
607
        [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]
608

609
        sage: E = EllipticCurve([-3440, 77658])
610
        sage: E.conductor()
611
        118336
612
        sage: isogenies_sporadic_Q(E,43)
613
        [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]
614

615
        sage: E = EllipticCurve([-29480, -1948226])
616
        sage: E.conductor()
617
        287296
618
        sage: isogenies_sporadic_Q(E,67)
619
        [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]
620

621
        sage: E = EllipticCurve([-34790720, -78984748304])
622
        sage: E.conductor()
623
        425104
624
        sage: isogenies_sporadic_Q(E,163)
625
        [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]
626
    """
627
    if E.base_ring() != QQ:
628
        raise ValueError("The elliptic curve must be defined over QQ.")
629
    j = E.j_invariant()
630
    j = QQ(j)
631
    if (j not in sporadic_j
632
        or (l is not None and sporadic_j[j] != l)):
633
        return []
634

635
    data = _sporadic_Q_data(j)
636
    Ew = E.short_weierstrass_model()
637
    E_to_Ew = E.isomorphism_to(Ew)
638
    c4, c6 = Ew.c_invariants()
639
    (a4,a6), f = data
640
    d = (c6*a4)/(18*c4*a6) # twisting factor
641
    R = PolynomialRing(E.base_field(),'X')
642
    n = len(f)
643
    ker = R([d**(n-i-1) * f[i] for i in range(n)])
644
    isog = Ew.isogeny(kernel=ker, degree=l, model="minimal", check=False)
645
    isog.set_pre_isomorphism(E_to_Ew)
646
    return [isog]
647

648

649
def isogenies_2(E):
650
    """
651
    Returns a list of all 2-isogenies with domain ``E``.
652

653
    INPUT:
654

655
    - ``E`` -- an elliptic curve.
656

657
    OUTPUT:
658

659
    (list) 2-isogenies with domain ``E``.  In general these are
660
    normalised, but over `\QQ` the codomain is a minimal model.
661

662
    EXAMPLES::
663

664
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_2
665
        sage: E = EllipticCurve('14a1'); E
666
        Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x - 6 over Rational Field
667
        sage: [phi.codomain().ainvs() for phi in isogenies_2(E)]
668
        [(1, 0, 1, -36, -70)]
669

670
        sage: E = EllipticCurve([1,2,3,4,5]); E
671
        Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field
672
        sage: [phi.codomain().ainvs() for phi in isogenies_2(E)]
673
        []
674
        sage: E = EllipticCurve(QQbar, [9,8]); E
675
        Elliptic Curve defined by y^2 = x^3 + 9*x + 8 over Algebraic Field
676
        sage: isogenies_2(E) # not implemented
677
    """
678
    f2 = E.division_polynomial(2)
679
    x2 = f2.roots(multiplicities=False)
680
    x2.sort()
681
    x = f2.parent().gen()
682
    ff = [x-x2i for x2i in x2]
683
    model = "minimal" if E.base_field() is QQ else None
684
    isogs = [E.isogeny(f, model=model) for f in ff]
685
    return isogs
686

687
def isogenies_3(E):
688
    """
689
    Returns a list of all 3-isogenies with domain ``E``.
690

691
    INPUT:
692

693
    - ``E`` -- an elliptic curve.
694

695
    OUTPUT:
696

697
    (list) 3-isogenies with domain ``E``.  In general these are
698
    normalised, but over `\QQ` the codomain is a minimal model.
699

700
    EXAMPLES::
701

702
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_3
703
        sage: E = EllipticCurve(GF(17), [1,1])
704
        sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]
705
        [(0, 0, 0, 9, 7), (0, 0, 0, 0, 1)]
706

707
        sage: E = EllipticCurve(GF(17^2,'a'), [1,1])
708
        sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]
709
        [(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)]
710

711
        sage: E = EllipticCurve('19a1')
712
        sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]
713
        [(0, 1, 1, 1, 0), (0, 1, 1, -769, -8470)]
714

715
        sage: E = EllipticCurve([1,1])
716
        sage: [phi.codomain().ainvs() for phi in isogenies_3(E)]
717
        []
718
    """
719
    f3 = E.division_polynomial(3)
720
    x3 = f3.roots(multiplicities=False)
721
    x3.sort()
722
    x = f3.parent().gen()
723
    ff = [x-x3i for x3i in x3]
724
    model = "minimal" if E.base_field() is QQ else None
725
    isogs = [E.isogeny(f, model=model) for f in ff]
726
    return isogs
727

728
# 6 special cases: `l` = 5, 7, 13 and `j` = 0, 1728.
729

730
def isogenies_5_0(E):
731
    """
732
    Returns a list of all the 5-isogenies  with domain ``E`` when the
733
    j-invariant is 0.
734

735
    OUTPUT:
736

737
    (list) 5-isogenies with codomain E.  In general these are
738
    normalised, but over `\QQ` the codomain is a minimal model.
739

740
    .. note::
741

742
       This implementation requires that the characteristic is not 2,
743
       3 or 5.
744

745
    .. note::
746

747
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(5)``.
748

749
    EXAMPLES::
750

751
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_5_0
752
        sage: E = EllipticCurve([0,12])
753
        sage: isogenies_5_0(E)
754
        []
755

756
        sage: E = EllipticCurve(GF(13^2,'a'),[0,-3])
757
        sage: isogenies_5_0(E)
758
        [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]
759

760
        sage: K.<a> = NumberField(x**6-320*x**3-320)
761
        sage: E = EllipticCurve(K,[0,0,1,0,0])
762
        sage: isogenies_5_0(E)
763
        [Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^6 - 320*x^3 - 320 to Elliptic Curve defined by y^2 = x^3 + (a^5-400*a^2)*x + (280*a^3-3120) over Number Field in a with defining polynomial x^6 - 320*x^3 - 320,
764
        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^6 - 320*x^3 - 320 to Elliptic Curve defined by y^2 = x^3 + (23/2*a^5-3700*a^2)*x + (-280*a^3+86480) over Number Field in a with defining polynomial x^6 - 320*x^3 - 320]
765

766
    """
767
    F = E.base_field()
768
    if E.j_invariant() != 0:
769
        raise ValueError("j-invariant must be 0.")
770
    if F.characteristic() in [2,3,5]:
771
        raise NotImplementedError("Not implemented in characteristic 2, 3 or 5.")
772
    if not F(5).is_square():
773
        return []
774
    Ew = E.short_weierstrass_model()
775
    a = Ew.a6()
776
    x = polygen(F)
777
    betas = (x**6-160*a*x**3-80*a**2).roots(multiplicities=False)
778
    betas.sort()
779
    if len(betas)==0:
780
        return []
781
    gammas = [(beta**2 *(beta**3-140*a))/(120*a) for beta in betas]
782
    model = "minimal" if F is QQ else None
783
    isogs = [Ew.isogeny(x**2+beta*x+gamma, model=model) for beta,gamma in zip(betas,gammas)]
784
    iso = E.isomorphism_to(Ew)
785
    [isog.set_pre_isomorphism(iso) for isog in isogs]
786
    return isogs
787

788
def isogenies_5_1728(E):
789
    """
790
    Returns a list of 5-isogenies with domain ``E`` when the j-invariant is
791
    1728.
792

793
    OUTPUT:
794

795
    (list) 5-isogenies with codomain E.  In general these are
796
    normalised; but if `-1` is a square then there are two
797
    endomorphisms of degree `5`, for which the codomain is the same as
798
    the domain curve; and over `\QQ`, the codomain is a minimal model.
799

800
    .. note::
801

802
       This implementation requires that the characteristic is not 2,
803
       3 or 5.
804

805
    .. note::
806

807
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(5)``.
808

809
    EXAMPLES::
810

811
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_5_1728
812
        sage: E = EllipticCurve([7,0])
813
        sage: isogenies_5_1728(E)
814
        []
815

816
        sage: E = EllipticCurve(GF(13),[11,0])
817
        sage: isogenies_5_1728(E)
818
        [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,
819
        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]
820

821
    An example of endomorphisms of degree 5::
822

823
        sage: K.<i> = QuadraticField(-1)
824
        sage: E = EllipticCurve(K,[0,0,0,1,0])
825
        sage: isogenies_5_1728(E)
826
        [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,
827
        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]
828
        sage: _[0].rational_maps()
829
        (((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)),
830
         ((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)))
831

832
    An example of 5-isogenies over a number field::
833

834
        sage: K.<a> = NumberField(x**4+20*x**2-80)
835
        sage: K(5).is_square() #necessary but not sufficient!
836
        True
837
        sage: E = EllipticCurve(K,[0,0,0,1,0])
838
        sage: isogenies_5_1728(E)
839
        [Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^4 + 20*x^2 - 80 to Elliptic Curve defined by y^2 = x^3 + (-20*a^2-39)*x + (35*a^3+112*a) over Number Field in a with defining polynomial x^4 + 20*x^2 - 80,
840
        Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^4 + 20*x^2 - 80 to Elliptic Curve defined by y^2 = x^3 + (-20*a^2-39)*x + (-35*a^3-112*a) over Number Field in a with defining polynomial x^4 + 20*x^2 - 80]
841
    """
842
    F = E.base_field()
843
    if E.j_invariant() != 1728:
844
        raise ValueError("j-invariant must be 1728.")
845
    if F.characteristic() in [2,3,5]:
846
        raise NotImplementedError("Not implemented in characteristic 2, 3 or 5.")
847
    model = "minimal" if F is QQ else None
848
    # quick test for a negative answer (from Fricke module)
849
    square5 = F(5).is_square()
850
    square1 = F(-1).is_square()
851
    if not square5 and not square1:
852
        return []
853
    Ew = E.short_weierstrass_model()
854
    iso = E.isomorphism_to(Ew)
855
    a = Ew.a4()
856
    x = polygen(F)
857
    isogs = []
858
    # 2 cases
859
    # Type 1: if -1 is a square we have 2 endomorphisms
860
    if square1:
861
        i = F(-1).sqrt()
862
        isogs = [Ew.isogeny(f) for f in [x**2+a/(1+2*i), x**2+a/(1-2*i)]]
863
        [isog.set_post_isomorphism(isog.codomain().isomorphism_to(E)) for isog in isogs]
864
    # Type 2: if 5 is a square we have up to 4 (non-endomorphism) isogenies
865
    if square5:
866
        betas = (x**4+20*a*x**2-80*a**2).roots(multiplicities=False)
867
        betas.sort()
868
        gammas = [a*(beta**2-2)/6 for beta in betas]
869
        isogs += [Ew.isogeny(x**2+beta*x+gamma, model=model) for beta,gamma in zip(betas,gammas)]
870
    [isog.set_pre_isomorphism(iso) for isog in isogs]
871
    return isogs
872

873
def isogenies_7_0(E):
874
    """
875
    Returns list of all 7-isogenies from E when the j-invariant is 0.
876

877
    OUTPUT:
878

879
    (list) 7-isogenies with codomain E.  In general these are
880
    normalised; but if `-3` is a square then there are two
881
    endomorphisms of degree `7`, for which the codomain is the same as
882
    the domain; and over `\QQ`, the codomain is a minimal model.
883

884
    .. note::
885

886
       This implementation requires that the characteristic is not 2,
887
       3 or 7.
888

889
    .. note::
890

891
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(7)``.
892

893
    EXAMPLES:
894

895
    First some examples of endomorphisms::
896

897
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_0
898
        sage: K.<r> = QuadraticField(-3)
899
        sage: E = EllipticCurve(K, [0,1])
900
        sage: isogenies_7_0(E)
901
        [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,
902
        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]
903

904
        sage: E = EllipticCurve(GF(13^2,'a'),[0,-3])
905
        sage: isogenies_7_0(E)
906
        [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]
907

908
    Now some examples of 7-isogenies which are not endomorphisms::
909

910
        sage: K = GF(101)
911
        sage: E = EllipticCurve(K, [0,1])
912
        sage: isogenies_7_0(E)
913
        [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]
914

915
    Examples over a number field::
916

917
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_0
918
        sage: E = EllipticCurve('27a1').change_ring(QuadraticField(-3,'r'))
919
        sage: isogenies_7_0(E)
920
        [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,
921
        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]
922

923
        sage: K.<a> = NumberField(x^6 + 1512*x^3 - 21168)
924
        sage: E = EllipticCurve(K, [0,1])
925
        sage: isogs = isogenies_7_0(E)
926
        sage: [phi.codomain().a_invariants() for phi in isogs]
927
        [(0, 0, 0, -5/294*a^5 - 300/7*a^2, -55/2*a^3 - 1133),
928
        (0, 0, 0, -295/1176*a^5 - 5385/14*a^2, 55/2*a^3 + 40447)]
929
        sage: [phi.codomain().j_invariant() for phi in isogs]
930
        [158428486656000/7*a^3 - 313976217600000,
931
        -158428486656000/7*a^3 - 34534529335296000]
932
    """
933
    if E.j_invariant()!=0:
934
        raise ValueError("j-invariant must be 0.")
935
    F = E.base_field()
936
    if F.characteristic() in [2,3,7]:
937
        raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 7.")
938
    x = polygen(F)
939
    Ew = E.short_weierstrass_model()
940
    iso = E.isomorphism_to(Ew)
941
    a = Ew.a6()
942
    model = "minimal" if F is QQ else None
943

944
    # there will be 2 endomorphisms if -3 is a square:
945

946
    ts = (x**2+3).roots(multiplicities=False)
947
    ts.sort()
948
    kers = [7*x-(2+6*t) for t in ts]
949
    kers = [k(x**3/a).monic() for k in kers]
950
    isogs = [Ew.isogeny(k,model=model) for k in kers]
951
    if len(isogs)>0:
952
        [endo.set_post_isomorphism(endo.codomain().isomorphism_to(E)) for endo in isogs]
953

954
    # we may have up to 6 other isogenies:
955
    ts = (x**2-21).roots(multiplicities=False)
956
    for t0 in ts:
957
        s3 = a/(28+6*t0)
958
        ss = (x**3-s3).roots(multiplicities=False)
959
        ss.sort()
960
        ker = x**3 - 2*t0*x**2 - 4*t0*x + 4*t0 + 28
961
        kers = [ker(x/s).monic() for s in ss]
962
        isogs += [Ew.isogeny(k, model=model) for k in kers]
963

964
    [isog.set_pre_isomorphism(iso) for isog in isogs]
965
    return isogs
966

967
def isogenies_7_1728(E):
968
    """
969
    Returns list of all 7-isogenies from E when the j-invariant is 1728.
970

971
    OUTPUT:
972

973
    (list) 7-isogenies with codomain E.  In general these are
974
    normalised; but over `\QQ` the codomain is a minimal model.
975

976
    .. note::
977

978
       This implementation requires that the characteristic is not 2,
979
       3, or 7.
980

981
    .. note::
982

983
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(7)``.
984

985
    EXAMPLES::
986

987
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_1728
988
        sage: E = EllipticCurve(GF(47), [1, 0])
989
        sage: isogenies_7_1728(E)
990
        [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,
991
        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]
992

993
    An example in characteristic 53 (for which an earlier implementation did not work)::
994

995
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_7_1728
996
        sage: E = EllipticCurve(GF(53), [1, 0])
997
        sage: isogenies_7_1728(E)
998
        []
999
        sage: E = EllipticCurve(GF(53^2,'a'), [1, 0])
1000
        sage: [iso.codomain().ainvs() for iso in isogenies_7_1728(E)]
1001
        [(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)]
1002

1003
    ::
1004

1005
        sage: K.<a> = NumberField(x^8 + 84*x^6 - 1890*x^4 + 644*x^2 - 567)
1006
        sage: E = EllipticCurve(K, [1, 0])
1007
        sage: isogs = isogenies_7_1728(E)
1008
        sage: [phi.codomain().a_invariants() for phi in isogs]
1009
        [(0,
1010
        0,
1011
        0,
1012
        35/636*a^6 + 55/12*a^4 - 79135/636*a^2 + 1127/212,
1013
        155/636*a^7 + 245/12*a^5 - 313355/636*a^3 - 3577/636*a),
1014
        (0,
1015
        0,
1016
        0,
1017
        35/636*a^6 + 55/12*a^4 - 79135/636*a^2 + 1127/212,
1018
        -155/636*a^7 - 245/12*a^5 + 313355/636*a^3 + 3577/636*a)]
1019
        sage: [phi.codomain().j_invariant() for phi in isogs]
1020
        [-526110256146528/53*a^6 + 183649373229024*a^4 - 3333881559996576/53*a^2 + 2910267397643616/53,
1021
        -526110256146528/53*a^6 + 183649373229024*a^4 - 3333881559996576/53*a^2 + 2910267397643616/53]
1022
        sage: E1 = isogs[0].codomain()
1023
        sage: E2 = isogs[1].codomain()
1024
        sage: E1.is_isomorphic(E2)
1025
        False
1026
        sage: E1.is_quadratic_twist(E2)
1027
        -1
1028
    """
1029
    if E.j_invariant()!=1728:
1030
        raise ValueError("j_invariant must be 1728 (in base field).")
1031
    F = E.base_field()
1032
    if F.characteristic() in [2,3,7]:
1033
        raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 7.")
1034
    Ew = E.short_weierstrass_model()
1035
    iso = E.isomorphism_to(Ew)
1036
    a = Ew.a4()
1037

1038
    ts = (Fricke_module(7)-1728).numerator().roots(F,multiplicities=False)
1039
    if len(ts)==0:
1040
        return []
1041
    ts.sort()
1042
    isogs = []
1043
    model = "minimal" if F is QQ else None
1044
    x = polygen(F)
1045
    for t0 in ts:
1046
        s2 = a/t0
1047
        ss = (x**2-s2).roots(multiplicities=False)
1048
        ss.sort()
1049
        ker = 9*x**3 + (-3*t0**3 - 36*t0**2 - 123*t0)*x**2 + (-8*t0**3 - 101*t0**2 - 346*t0 + 35)*x - 7*t0**3 - 88*t0**2 - 296*t0 + 28
1050

1051
        kers = [ker(x/s) for s in ss]
1052
        isogs += [Ew.isogeny(k.monic(), model=model) for k in kers]
1053
    [isog.set_pre_isomorphism(iso) for isog in isogs]
1054
    return isogs
1055

1056
def isogenies_13_0(E):
1057
    """
1058
    Returns list of all 13-isogenies from E when the j-invariant is 0.
1059

1060
    OUTPUT:
1061

1062
    (list) 13-isogenies with codomain E.  In general these are
1063
    normalised; but if `-3` is a square then there are two
1064
    endomorphisms of degree `13`, for which the codomain is the same
1065
    as the domain.
1066

1067
    .. note::
1068

1069
       This implementation requires that the characteristic is not 2,
1070
       3 or 13.
1071

1072
    .. note::
1073

1074
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(13)``.
1075

1076
    EXAMPLES::
1077

1078
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_13_0
1079

1080
    Endomorphisms of degree 13 will exist when -3 is a square::
1081

1082
        sage: K.<r> = QuadraticField(-3)
1083
        sage: E = EllipticCurve(K, [0, r]); E
1084
        Elliptic Curve defined by y^2 = x^3 + r over Number Field in r with defining polynomial x^2 + 3
1085
        sage: isogenies_13_0(E)
1086
        [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,
1087
        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]
1088
        sage: isogenies_13_0(E)[0].rational_maps()
1089
        (((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)))
1090

1091
    An example of endomorphisms over a finite field::
1092

1093
        sage: K = GF(19^2,'a')
1094
        sage: E = EllipticCurve(j=K(0)); E
1095
        Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in a of size 19^2
1096
        sage: isogenies_13_0(E)
1097
        [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,
1098
        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]
1099
        sage: isogenies_13_0(E)[0].rational_maps()
1100
        ((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))
1101

1102
    A previous implementation did not work in some characteristics::
1103

1104
        sage: K = GF(29)
1105
        sage: E = EllipticCurve(j=K(0))
1106
        sage: isogenies_13_0(E)
1107
        [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]
1108

1109
    ::
1110

1111
        sage: K = GF(101)
1112
        sage: E = EllipticCurve(j=K(0)); E.ainvs()
1113
        (0, 0, 0, 0, 1)
1114
        sage: [phi.codomain().ainvs() for phi in isogenies_13_0(E)]
1115
        [(0, 0, 0, 64, 36), (0, 0, 0, 42, 66)]
1116

1117
    ::
1118

1119
        sage: x = polygen(QQ)
1120
        sage: f = x^12 + 78624*x^9 - 130308048*x^6 + 2270840832*x^3 - 54500179968
1121
        sage: K.<a> = NumberField(f)
1122
        sage: E = EllipticCurve(j=K(0)); E.ainvs()
1123
        (0, 0, 0, 0, 1)
1124
        sage: [phi.codomain().ainvs() for phi in isogenies_13_0(E)]
1125
        [(0, 0, 0, -739946459/23857162861049856*a^11 - 2591641747/1062017577504*a^8 + 16583647773233/4248070310016*a^5 - 14310911337/378211388*a^2, 26146225/4248070310016*a^9 + 7327668845/14750244132*a^6 + 174618431365/756422776*a^3 - 378332499709/94552847), (0, 0, 0, 3501275/5964290715262464*a^11 + 24721025/531008788752*a^8 - 47974903745/1062017577504*a^5 - 6773483100/94552847*a^2, 6699581/4248070310016*a^9 + 1826193509/14750244132*a^6 - 182763866047/756422776*a^3 - 321460597/94552847)]
1126
    """
1127
    if E.j_invariant()!=0:
1128
        raise ValueError("j-invariant must be 0.")
1129
    F = E.base_field()
1130
    if F.characteristic() in [2,3,13]:
1131
        raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 13.")
1132
    Ew = E.short_weierstrass_model()
1133
    iso = E.isomorphism_to(Ew)
1134
    a = Ew.a6()
1135
    model = "minimal" if F is QQ else None
1136
    x = polygen(F)
1137

1138
    # there will be 2 endomorphisms if -3 is a square:
1139
    ts = (x**2+3).roots(multiplicities=False)
1140
    ts.sort()
1141
    kers = [13*x**2 + (78*t + 26)*x + 24*t + 40 for t in ts]
1142
    kers = [k(x**3/a).monic() for k in kers]
1143
    isogs = [Ew.isogeny(k,model=model) for k in kers]
1144
    if len(isogs)>0:
1145
        [endo.set_post_isomorphism(endo.codomain().isomorphism_to(E)) for endo in isogs]
1146

1147
    # we may have up to 12 other isogenies:
1148
    ts = (x**4 + 7*x**3 + 20*x**2 + 19*x + 1).roots(multiplicities=False)
1149
    ts.sort()
1150
    for t0 in ts:
1151
        s3 = a / (6*t0**3 + 32*t0**2 + 68*t0 + 4)
1152
        ss = (x**3-s3).roots(multiplicities=False)
1153
        ss.sort()
1154
        ker = (x**6 + (20*t0**3 + 106*t0**2 + 218*t0 + 4)*x**5
1155
            + (-826*t0**3 - 4424*t0**2 - 9244*t0 - 494)*x**4
1156
            + (13514*t0**3 + 72416*t0**2 + 151416*t0 + 8238)*x**3
1157
            + (-101948*t0**3 - 546304*t0**2 - 1142288*t0 - 62116)*x**2
1158
            + (354472*t0**3 + 1899488*t0**2 + 3971680*t0 + 215960)*x
1159
            - 459424*t0**3 - 2461888*t0**2 - 5147648*t0 - 279904)
1160
        kers = [ker(x/s).monic() for s in ss]
1161
        isogs += [Ew.isogeny(k, model=model) for k in kers]
1162

1163
    [isog.set_pre_isomorphism(iso) for isog in isogs]
1164

1165
    return isogs
1166

1167
def isogenies_13_1728(E):
1168
    """
1169
    Returns list of all 13-isogenies from E when the j-invariant is 1728.
1170

1171
    OUTPUT:
1172

1173
    (list) 13-isogenies with codomain E.  In general these are
1174
    normalised; but if `-1` is a square then there are two
1175
    endomorphisms of degree `13`, for which the codomain is the same
1176
    as the domain; and over `\QQ`, the codomain is a minimal model.
1177

1178
    .. note::
1179

1180
       This implementation requires that the characteristic is not
1181
       2, 3 or 13.
1182

1183
    .. note::
1184

1185
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(13)``.
1186

1187
    EXAMPLES::
1188

1189
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_13_1728
1190

1191
        sage: K.<i> = QuadraticField(-1)
1192
        sage: E = EllipticCurve([0,0,0,i,0]); E.ainvs()
1193
        (0, 0, 0, i, 0)
1194
        sage: isogenies_13_1728(E)
1195
        [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,
1196
        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]
1197

1198
    ::
1199

1200
        sage: K = GF(83)
1201
        sage: E = EllipticCurve(K, [0,0,0,5,0]); E.ainvs()
1202
        (0, 0, 0, 5, 0)
1203
        sage: isogenies_13_1728(E)
1204
        []
1205
        sage: K = GF(89)
1206
        sage: E = EllipticCurve(K, [0,0,0,5,0]); E.ainvs()
1207
        (0, 0, 0, 5, 0)
1208
        sage: isogenies_13_1728(E)
1209
        [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,
1210
        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]
1211

1212
    ::
1213

1214
        sage: K = GF(23)
1215
        sage: E = EllipticCurve(K, [1,0])
1216
        sage: isogenies_13_1728(E)
1217
        [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]
1218

1219
    ::
1220

1221
        sage: x = polygen(QQ)
1222
        sage: f = x^12 + 1092*x^10 - 432432*x^8 + 6641024*x^6 - 282896640*x^4 - 149879808*x^2 - 349360128
1223
        sage: K.<a> = NumberField(f)
1224
        sage: E = EllipticCurve(K, [1,0])
1225
        sage: [phi.codomain().ainvs() for phi in isogenies_13_1728(E)]
1226
        [(0,
1227
        0,
1228
        0,
1229
        11090413835/20943727039698624*a^10 + 32280103535965/55849938772529664*a^8 - 355655987835845/1551387188125824*a^6 + 19216954517530195/5235931759924656*a^4 - 1079766118721735/5936430566808*a^2 + 156413528482727/8080141604822,
1230
        214217013065/82065216155553792*a^11 + 1217882637605/427423000810176*a^9 - 214645003230565/189965778137856*a^7 + 22973355421236025/1282269002430528*a^5 - 2059145797340695/2544184528632*a^3 - 23198483147321/989405094468*a),
1231
        (0,
1232
        0,
1233
        0,
1234
        11090413835/20943727039698624*a^10 + 32280103535965/55849938772529664*a^8 - 355655987835845/1551387188125824*a^6 + 19216954517530195/5235931759924656*a^4 - 1079766118721735/5936430566808*a^2 + 156413528482727/8080141604822,
1235
        -214217013065/82065216155553792*a^11 - 1217882637605/427423000810176*a^9 + 214645003230565/189965778137856*a^7 - 22973355421236025/1282269002430528*a^5 + 2059145797340695/2544184528632*a^3 + 23198483147321/989405094468*a)]
1236

1237
    """
1238
    if E.j_invariant()!=1728:
1239
        raise ValueError("j-invariant must be 1728.")
1240
    F = E.base_field()
1241
    if F.characteristic() in [2, 3, 13]:
1242
        raise NotImplementedError("Not implemented when the characteristic of the base field is 2, 3 or 13.")
1243
    Ew = E.short_weierstrass_model()
1244
    iso = E.isomorphism_to(Ew)
1245
    a = Ew.a4()
1246
    model = "minimal" if F is QQ else None
1247
    x = polygen(F)
1248

1249
    # we will have two endomorphisms if -1 is a square:
1250
    ts = (x**2+1).roots(multiplicities=False)
1251
    ts.sort()
1252
    kers = [13*x**3 + (-26*i - 13)*x**2 + (-52*i - 13)*x - 2*i - 3 for i in ts]
1253
    kers = [k(x**2/a).monic() for k in kers]
1254
    isogs = [Ew.isogeny(k,model=model) for k in kers]
1255
    if len(isogs)>0:
1256
        [endo.set_post_isomorphism(endo.codomain().isomorphism_to(E)) for endo in isogs]
1257

1258
    # we may have up to 12 other isogenies:
1259

1260
    ts = (x**6 + 10*x**5 + 46*x**4 + 108*x**3 + 122*x**2 + 38*x - 1).roots(multiplicities=False)
1261
    ts.sort()
1262
    for t0 in ts:
1263
        s2 = a/(66*t0**5 + 630*t0**4 + 2750*t0**3 + 5882*t0**2 + 5414*t0 + 162)
1264
        ss = (x**2-s2).roots(multiplicities=False)
1265
        ss.sort()
1266
        ker = (x**6 + (-66*t0**5 - 630*t0**4 - 2750*t0**3 - 5882*t0**2
1267
              - 5414*t0 - 162)*x**5 + (-21722*t0**5 - 205718*t0**4 -
1268
              890146*t0**3 - 1873338*t0**2 - 1652478*t0 + 61610)*x**4
1269
              + (-3391376*t0**5 - 32162416*t0**4 - 139397232*t0**3 -
1270
              294310576*t0**2 - 261885968*t0 + 6105552)*x**3 +
1271
              (-241695080*t0**5 - 2291695976*t0**4 - 9930313256*t0**3
1272
              - 20956609720*t0**2 - 18625380856*t0 + 469971320)*x**2 +
1273
              (-8085170432*t0**5 - 76663232384*t0**4 -
1274
              332202985024*t0**3 - 701103233152*t0**2 -
1275
              623190845440*t0 + 15598973056)*x - 101980510208*t0**5 -
1276
              966973468160*t0**4 - 4190156868352*t0**3 -
1277
              8843158270336*t0**2 - 7860368751232*t0 + 196854655936)
1278

1279
        kers = [ker(x/s).monic() for s in ss]
1280
        isogs += [Ew.isogeny(k, model=model) for k in kers]
1281

1282
    [isog.set_pre_isomorphism(iso) for isog in isogs]
1283

1284
    return isogs
1285

1286
# List of primes l for which X_0(l) is (hyper)elliptic and X_0^+(l) has genus 0
1287

1288
hyperelliptic_primes = [11, 17, 19, 23, 29, 31, 41, 47, 59, 71]
1289

1290
@cached_function
1291
def _hyperelliptic_isogeny_data(l):
1292
    r"""
1293
    Helper function for elliptic curve isogenies.
1294

1295
    INPUT:
1296

1297
    - ``l`` -- a prime in [11, 17, 19, 23, 29, 31, 41, 47, 59, 71]
1298

1299
    OUTPUT:
1300

1301
    - A dict holding a collection of precomputed data needed for computing `l`-isogenies.
1302

1303
    EXAMPLES::
1304

1305
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import _hyperelliptic_isogeny_data
1306
        sage: HID = _hyperelliptic_isogeny_data(11)
1307
        sage: HID['A2']
1308
        55*u - 33
1309
        sage: HID['A4']
1310
        -183*u^2 + 738*u - 180*v - 135
1311
        sage: HID['A6']
1312
        1330*u^3 - 11466*u^2 + 1332*u*v + 2646*u - 1836*v + 1890
1313
        sage: HID['alpha']
1314
        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
1315
        sage: HID['beta']
1316
        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
1317
        sage: HID['hyper_poly']
1318
        u^4 - 16*u^3 + 2*u^2 + 12*u - 7
1319

1320
        sage: _hyperelliptic_isogeny_data(37)
1321
        Traceback (most recent call last):
1322
        ...
1323
        ValueError: 37 must be one of [11, 17, 19, 23, 29, 31, 41, 47, 59, 71].
1324

1325
    """
1326
    if not l in hyperelliptic_primes:
1327
        raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
1328
    data = {}
1329
    Zu = PolynomialRing(ZZ,'u')
1330
    Zuv = PolynomialRing(ZZ,['u','v'])
1331
    Zxuv = PolynomialRing(ZZ,['x','u','v'])
1332
    x,u,v = Zxuv.gens()
1333
    if l == 11:
1334
        data['hyper_poly'] = Zu([-7, 12, 2, -16, 1])
1335
        data['A2'] = Zu([-33, 55])
1336
        data['A4'] = Zuv(Zu([-135, 738, -183])+v*Zu([-180]))
1337
        data['A6'] = Zuv(Zu([1890, 2646, -11466, 1330]) + v*Zu([-1836, 1332]))
1338
        data['alpha'] = Zu([-6750, 24300, 40095, -187407, 132066, 133056, -177408, 69630, -12716, 1188, -55, 1])
1339
        data['beta'] = Zu([0, -12150, 27135, 10665, -48573, 29313, -7187, 843, -47, 1])
1340
        #beta factors as (u - 15) * (u - 6) * (u - 3) * (u - 1) * u * (u**2 - 12*u - 9) * (u**2 - 10*u + 5)
1341
        return data
1342
    if l == 17:
1343
        data['hyper_poly'] = Zu([-8, 4, -3, -10, 1])
1344
        data['A2'] = Zu([68, -204, 136])
1345
        data['A4'] = Zuv(Zu([60, 720, -2595, 2250, -435]) + v*Zu([-360, 792, -432]))
1346
        data['A6'] = Zuv(Zu([-8512, 22608, -5064, -57528, 87288, -43704, 4912] ) + v*Zu( [2520, -15372, 28098, -20160, 4914]))
1347
        data['alpha'] = Zu([16000, -67200, 2720, 557600, -1392232, 1073992, 1104830, -3131026, 2450210, 73746, -1454945, 1110355, -424065, 95659, -13243, 1105, -51, 1])
1348
        data['beta'] = Zu([0, 22400, -105920, 146208, 111616, -593800, 680948, -102282, -457950, 468035, -219274, 58549, -9374, 889, -46, 1])
1349
        #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)
1350
        data['endo'] = 17*x**8 + 17*(-4*u + 4)*v*x**6 + 17*(4*u + 6)*v**2*x**4 + 17*(4*u + 4)*v**3*x**2 + (-4*u + 1)*v**4
1351
        data['endo_u'] = 1
1352
        return data
1353
    if l == 19:
1354
        data['hyper_poly'] = Zu([-8, 20, -8, -8, 1])
1355
        data['A2'] = Zu([-114, 57, 171])
1356
        data['A4'] = Zuv(Zu([-1020, 444, 2733, 726, -543]) + v*Zu([-180, -720, -540]))
1357
        data['A6'] = Zuv(Zu([-10080, 21816, 54324, -37386, -86742, -20070, 6858]) + v*Zu([-2968, -13748, -11284, 6356, 6860]))
1358
        data['alpha'] = Zu([16000, -22400, -337440, 475456, 1562104, -1988616, -3025294, 3245960, 2833014, -2420087, -1140950, 932406, 129580, -180443, 21090, 11153, -4066, 570, -38, 1])
1359
        data['beta'] = Zu([0, 33600, -8160, -292400, 23472, 791244, 39282, -847909, -47024, 392654, -24046, -82469, 19162, 4833, -2652, 446, -34, 1])
1360
        #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)
1361
        data['endo'] = 19*x**9 + 19*(-12*u - 24)*v*x**6 + 19*(-24*u - 24)*v**2*x**3 + (96*u - 224)*v**3
1362
        data['endo_u'] = -1
1363
        return data
1364
    if l == 23:
1365
        data['hyper_poly'] = Zu([-7, 10, -11, 2, 2, -8, 1])
1366
        data['A2'] = Zu([69, -230, 253])
1367
        data['A4'] = Zuv(Zu([405, 180, -930, 2820, -795]) + v*Zu([360, -792]))
1368
        data['A6'] = Zuv(Zu([-15498, 34020, -36918, -8120, 51114, -72492, 12166]) + v*Zu([-1080, 7704, -24840, 12168]))
1369
        data['alpha'] = Zu([-6750, 48600, -83835, -170775, 1115109, -2492280, 2732814, -116403, -4877702, 8362616, -6612454, 302266, 5423124, -6447728, 3209696, 336674, -1470068, 953856, -336927, 74221, -10465, 920, -46, 1])
1370
        data['beta'] = Zu( [0, 12150, -72495, 168588, -144045, -254034, 930982, -1256170, 604358, 693650, -1563176, 1271974, -225188, -444070, 421050, -184350, 47754, -7696, 759, -42, 1])
1371
        #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)
1372
        return data
1373
    if l == 29:
1374
        data['hyper_poly'] = Zu([-7, 8, 8, 2, -12, -4, 1])
1375
        data['A2'] = Zu([-174, -232, 348, 406])
1376
        data['A4'] = Zuv(Zu([-1215, -3096, 132, 7614, 6504, -360, -1263] ) + v*Zu( [180, -720, -2160, -1260]))
1377
        data['A6'] = Zuv(Zu([-18900, -63504, 24696, 285068, 285264, -185136, -506268, -275520, 504, 24388] ) + v*Zu( [4482, -2448, -59868, -94968, -18144, 48276, 24390]))
1378
        data['alpha'] = Zu([-6750, -12150, 281880, 570024, -1754181, -5229135, 2357613, 19103721, 9708910, -31795426, -38397537, 19207947, 54103270, 9216142, -37142939, -18871083, 14041394, 10954634, -3592085, -3427365, 853818, 622398, -189399, -53679, 26680, -580, -1421, 319, -29, 1])
1379
        data['beta'] = Zu([0, -24300, -57510, 257850, 839187, -373185, -3602119, -2371192, 5865017, 8434433, -2363779, -10263744, -2746015, 5976011, 3151075, -2093854, -1356433, 569525, 299477, -129484, -28279, 19043, -895, -1076, 273, -27, 1])
1380
        #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)
1381
        data['endo'] = 29*x**14 + 29*(-14*u + 3)*v*x**12 + 29*(-20*u + 73)*v**2*x**10 + 29*(-58*u + 115)*v**3*x**8 + 29*(-56*u + 59)*v**4*x**6 + 29*(30*u + 1)*v**5*x**4 + 29*(12*u - 5)*v**6*x**2 + (2*u + 5)*v**7
1382
        data['endo_u'] = -1
1383
        return data
1384
    if l == 31:
1385
        data['hyper_poly'] = Zu([-3, -14, -11, 18, 6, -8, 1])
1386
        data['A2'] = Zu([558, 837, -1488, 465])
1387
        data['A4'] = Zuv(Zu([-4140, -12468, 15189, 16956, -27054, 11184, -1443]) + v*Zu([2160, -7560, 6120, -1440]))
1388
        data['A6'] = Zuv(Zu([71280, 592056, -108324, -2609730, 2373048, 1282266, -2793204, 1530882, -356976, 29790]) + v*Zu([-81312, 181664, 294728, -868392, 701400, -238840, 29792]))
1389
        data['alpha'] = Zu([108000, 475200, -7053120, -27353408, 90884374, 303670296, -665806437, -1361301729, 3259359840, 2249261823, -9368721606, 2279583264, 13054272515, -12759480061, -4169029296, 14390047139, -7803693550, -2988803682, 6239473912, -3296588360, 134066754, 908915598, -685615437, 294482733, -87483178, 18983315, -3052818, 361336, -30659, 1767, -62, 1])
1390
        data['beta'] = Zu([0, 712800, 1216080, -18430560, -15262464, 168899202, -12931221, -720077416, 624871714, 1239052988, -2259335558, 68648452, 2679085427, -2318039014, -229246628, 1710545918, -1243026758, 211524870, 296674626, -291810274, 145889932, -48916468, 11793961, -2085662, 269348, -24778, 1540, -58, 1])
1391
        #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)
1392
        data['endo'] = 31*x**15 + 31*(-66*u + 86)*v*x**12 + 31*(168*u + 280)*v**2*x**9 + 31*(576*u + 1792)*v**3*x**6 + 31*(384*u + 896)*v**4*x**3 + (-3072*u - 2048)*v**5
1393
        data['endo_u'] = 2
1394
        return data
1395
    if l == 41:
1396
        data['hyper_poly'] = Zu([-8, -20, -15, 8, 20, 10, -8, -4, 1])
1397
        data['A2'] = Zu([328, 656, -656, -1148, 820])
1398
        data['A4'] = Zuv(Zu([-1380, -4008, 1701, 10872, 6144, -18378, -2160, 9732, -2523]) + v*Zu([720, -1440, -2160, 5400, -2520]))
1399
        data['A6'] = Zuv(Zu([4480, 155616, 16080, -550720, -343968, 832680, 938632, -621648, -1468608, 953920, 427632, -413016, 68920]) + v*Zu([-14616, 6804, 96390, -2016, -324324, 184464, 260568, -276192, 68922]))
1400
        data['alpha'] = Zu([16000, 67200, -465760, -2966432, -1742664, 20985112, 46140990, -31732934, -217030548, -147139488, 436080674, 745775322, -271341362, -1542677562, -605560447, 1832223375, 1772593672, -1270633050, -2400692229, 343522723, 2179745361, 282422801, -1503727029, -421357697, 879637411, 261059095, -462271351, -61715127, 193718727, -24135265, -49355103, 20512341, 3613289, -4706595, 1099661, 163057, -162483, 46617, -7544, 738, -41, 1])
1401
        data['beta'] = Zu([0, 44800, 167040, -447040, -2734272, -1104272, 13488360, 21067652, -24681704, -83929974, -8986886, 169059382, 127641266, -196479899, -283039783, 124573790, 366614063, -12946368, -332987597, -58867672, 241909907, 60568430, -155045647, -17919564, 79114945, -12025938, -24060781, 11190142, 1979597, -2931764, 750233, 110144, -122263, 37484, -6439, 666, -39, 1])
1402
        #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)
1403
        data['endo'] = 41*x**20 + 41*(-12*u - 22)*v*x**18 + 41*(-252*u - 247)*v**2*x**16 + 41*(-176*u - 424)*v**3*x**14 + 41*(464*u - 254)*v**4*x**12 + 41*(1688*u - 868)*v**5*x**10 + 41*(1720*u - 1190)*v**6*x**8 + 41*(528*u - 232)*v**7*x**6 + 41*(16*u + 29)*v**8*x**4 + 41*(20*u + 10)*v**9*x**2 + (4*u + 5)*v**10
1404
        data['endo_u'] = 1
1405
        return data
1406
    if l == 47:
1407
        data['hyper_poly'] = Zu([-11, 28, -38, 30, -13, -16, 19, -24, 11, -6, 1])
1408
        data['A2'] = Zu([376, -1504, 2209, -1598, 1081])
1409
        data['A4'] = Zuv(Zu([2400, -4080, -1440, 18000, -26355, 34740, -22050, 12900, -3315]) + v*Zu([1152, -3384, 3672, -3312]))
1410
        data['A6'] = Zuv(Zu([-119504, 606336, -1505280, 2109392, -1509360, -515808, 2920702, -4614012, 4334322, -3260312, 1571442, -622428, 103822]) + v*Zu([2016, 48384, -235872, 438984, -627480, 503496, -311976, 103824]))
1411
        data['alpha'] = Zu([-65536, 688128, -2502656, -96256, 38598656, -187217920, 508021120, -845669120, 552981696, 1469334304, -5945275904, 11705275552, -14673798654, 9100068184, 8421580132, -34288012648, 56657584158, -60426283952, 36612252089, 9942017442, -60791892299, 93046207239, -92028642340, 59196883097, -10454018992, -33364599371, 57280402355, -57873890484, 41879296232, -20241250112, 2065827049, 8435506655, -11611941072, 10182603298, -7040645261, 4071881378, -2013138357, 856757031, -313468474, 97893151, -25770006, 5617769, -990431, 136864, -14194, 1034, -47, 1])
1412
        data['beta'] = Zu([0, 114688, -1114112, 4854784, -11205632, 7426048, 42663936, -182555136, 394092544, -508851472, 213245648, 743315936, -2203729384, 3409478688, -3280008936, 1139839970, 2576264698, -6272528962, 8005203155, -6671665088, 2744569094, 1996771588, -5520074039, 6637395180, -5455622885, 3028415830, -601645255, -1012737914, 1632999370, -1525982346, 1093778952, -644352392, 319489974, -134176208, 47566499, -14083902, 3424200, -667810, 101271, -11438, 901, -44, 1])
1413
        #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)
1414
        return data
1415
    if l == 59:
1416
        data['hyper_poly'] = Zu([-8, -4, 20, -24, -3, 40, -62, 40, 3, -28, 22, -8, 1])
1417
        data['A2'] = Zu([590, -1475, -295, 4130, -4425, 1711])
1418
        data['A4'] = Zuv(Zu([-2460, 8844, -3843, -20718, 57153, -50418, -12600, 72762, -69339, 30978, -5223]) + v*Zu([900, 360, -7560, 10800, -5220]))
1419
        data['A6'] = Zuv(Zu([25760, -373560, 568020, 1147870, -4634370, 5318070, 1631996, -14270202, 21535998, -14119408, -2820102, 14275410, -13535292, 6790074, -1847898, 205378]) + v*Zu([-23688, 27972, 183708, -696024, 721980, 453600, -1925028, 2039184, -1027404, 205380]))
1420
        data['alpha'] = Zu([16000, -67200, -783520, 5573376, -5127336, -60792184, 241324042, -170978932, -1262437160, 4310971231, -3953349811, -10887235780, 41679530185, -51342089572, -33068562195, 230682514316, -372641172307, 121615007703, 682044179678, -1549365239197, 1373184591667, 614906882627, -3566756201696, 4920423266916, -2342393877496, -3589340274442, 8772457933356, -8488557160148, 1742977715620, 7131088674129, -11643540780203, 8512399456274, -315658868113, -6917286294515, 8713332734648, -5190227733987, -54249978263, 3397583328372, -3658171840037, 1987950394792, -179519591637, -748989116551, 800595050760, -459184355769, 134398080099, 28871590941, -64236756338, 46651654354, -23352309386, 9059054346, -2830320860, 721829600, -150487052, 25475079, -3452149, 365800, -29205, 1652, -59, 1])
1421
        data['beta'] = Zu([0, -56000, 320800, 391440, -7693120, 21125500, 11515130, -204780145, 486681785, -102547033, -2147060784, 5552726794, -4419031758, -9431888681, 33728080307, -42367773552, -2994127157, 105330637610, -188172973931, 127559513693, 123083802224, -421097252069, 490425751691, -161944881372, -408669953969, 799965143719, -668167261718, 69589638764, 563644022562, -787681290965, 505670881115, 2900924856, -364669742737, 407962360532, -223582547975, 9985786664, 102435489491, -105519055992, 58212400117, -14331637533, -6742538722, 10205452686, -6853903214, 3244679736, -1188153136, 347102566, -81626216, 15409226, -2307408, 268126, -23322, 1429, -55, 1])
1422
        #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)
1423
        return data
1424
    if l == 71:
1425
        data['hyper_poly'] = Zu([-7, 6, -27, 40, -58, 66, -66, 40, 15, -48, 66, -66, 37, -10, 1])
1426
        data['A2'] = Zu([213, -1420, 4260, -4970, 9940, -9088, 2485])
1427
        data['A4'] = Zuv(Zu([2565, -10008, 18024, -26532, 23208, 7584, -104418, 189432, -251736, 275148, -182232, 60144, -7563]) + v*Zu([720, -4320, 7560, -20160, 23040, -7560]))
1428
        data['A6'] = Zuv(Zu([-69930, 382536, -1898568, 5206124, -11813256, 23115792, -35705670, 44318064, -41531952, 20674360, 23881872, -77986944, 114989770, -124612152, 103122936, -59431204, 21485688, -4294416, 357910]) + v*Zu([18576, -53856, 57672, 161856, -961920, 3199176, -5706288, 8032896, -9352584, 6786720, -2505888, 357912]))
1429
        data['alpha'] = Zu([-6750, 97200, -603855, 2263977, -4854483, -2486349, 75190491, -399596520, 1441975423, -4089818964, 9450153463, -17516526653, 23635982289, -11859874932, -53385529273, 230566737711, -585283867605, 1136695427037, -1753961304140, 2020891913264, -1147488305875, -1930304898882, 8102336330029, -17218530732347, 27006964902986, -32365758791872, 25902000374138, -468390635342, -46332664858222, 107139839089502, -162234735929274, 182582147217312, -140033523896938, 22513210292184, 152367877270246, -334009986053250, 451855980915164, -443144048889720, 284518400252142, -11142427766850, -289840331821002, 512373447321402, -576967281819172, 466024421705696, -230395084854230, -36287337331916, 241209603962570, -330646545417814, 304702155703516, -205131886553392, 87504290135653, 5131997859077, -54867900326127, 66216047255551, -54817285755105, 36239054778472, -20052219750661, 9464634765852, -3841191816845, 1343947848527, -405138280373, 104923131180, -23228729413, 4364552115, -689157169, 90223321, -9613968, 812240, -52327, 2414, -71, 1])
1430
        data['beta'] = Zu([0, 12150, -163215, 1115640, -5311143, 18820224, -50700172, 99823812, -102454041, -183909134, 1354660714, -4462311942, 10695310224, -20015395554, 28262441676, -23240987282, -17879387475, 124501604946, -315187724212, 564766450688, -765154573538, 705985549104, -115433273216, -1206098873334, 3175185881748, -5228317292044, 6292310032120, -5077451367560, 719644756530, 6451571564682, -14460150103020, 19999710623352, -19681838601268, 11819712227412, 2180981559572, -17790742756618, 29025463386612, -31179247603548, 23207078145510, -8345354986332, -7468523752270, 18486966963350, -21719818051100, 17831212433536, -10100011266030, 2336962513536, 2906983627184, -4989755986066, 4711466210012, -3361479243242, 1952316811463, -948555371584, 389878900245, -136099552242, 40341734984, -10121407164, 2136756509, -376218102, 54551634, -6399080, 591884, -41538, 2078, -66, 1])
1431
        #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)
1432
        return data
1433

1434
@cached_function
1435
def Psi2(l):
1436
    """
1437
    Returns the generic kernel polynomial for hyperelliptic `l`-isogenies.
1438

1439
    INPUT:
1440

1441
    - ``l`` -- either 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
1442

1443
    OUTPUT:
1444

1445
    The generic `l`-kernel polynomial.
1446

1447
    TESTS::
1448

1449
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2
1450
        sage: Psi2(11)
1451
        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
1452

1453
    """
1454
    if not l in hyperelliptic_primes:
1455
        raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
1456

1457
    data = _hyperelliptic_isogeny_data(l)
1458
    R = PolynomialRing(QQ,['x','u'])
1459
    x, u = R.gens()
1460
    L = PolynomialRing(R,'y')
1461
    y = L.gen()
1462
    K = R.extension(y**2-R(data['hyper_poly']),name = 'v')
1463
    v = K.gen()
1464
    from sage.categories.homset import Hom
1465
    h = Hom(K,K)(-v)
1466

1467
    A = K(data['A4'])
1468
    B = K(data['A6'])
1469
    Abar = h(A)*l**2
1470
    Bbar = -h(B)*l**3
1471
    s1 = K(data['A2'])
1472

1473
    d = (l-1)//2
1474
    s = [1]
1475
    t = [d,s1,((1-10*d)*A - Abar)*(1/QQ(30))]
1476
    t += [((1-28*d)*B - 42*t[1]*A - Bbar)*(1/QQ(70))]
1477
    c = [0,6*t[2] + 2*A*t[0],10*t[3] + 6*A*t[1] + 4*B*t[0]]
1478
    for n in range(2,d):
1479
        k = sum(c[i]*c[n-i] for i in range(1,n))
1480
        c += [(3*k-(2*n-1)*(n-1)*A*c[n-1]-(2*n-2)*(n-2)*B*c[n-2])*(1/QQ((n-1)*(2*n+5)))]
1481
    for n in range(3,d):
1482
        t += [(c[n]-(4*n-2)*A*t[n-1]-(4*n-4)*B*t[n-2])*(1/QQ(4*n+2))]
1483
    for n in range(1,d+1):
1484
        s += [(-1/QQ(n))*sum((-1)**i*t[i]*s[n-i] for i in range(1,n+1))]
1485
    psi = sum((-1)**i*s[i]*x**(d-i) for i in range(0,d+1))
1486
    R = PolynomialRing(QQ,['x','u','v'])
1487
    return R(psi)
1488

1489

1490
def isogenies_prime_degree_genus_plus_0(E, l=None):
1491
    """
1492
    Returns list of ``l`` -isogenies with domain ``E``.
1493

1494
    INPUT:
1495

1496
    - ``E`` -- an elliptic curve.
1497

1498
    - ``l`` -- either None or 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
1499

1500
    OUTPUT:
1501

1502
    (list) When ``l`` is None a list of all isogenies of degree 11, 17, 19, 23,
1503
    29, 31, 41, 47, 59, or 71, otherwise a list of isogenies of the given degree.
1504

1505
    .. note::
1506

1507
       This function would normally be invoked indirectly via
1508
       ``E.isogenies_prime_degree(l)``, which automatically calls the appropriate function.
1509

1510
    ALGORITHM:
1511

1512
    See [KT2013]_, Chapter 5.
1513

1514
    EXAMPLES::
1515

1516
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_plus_0
1517

1518
        sage: E = EllipticCurve('121a1')
1519
        sage: isogenies_prime_degree_genus_plus_0(E, 11)
1520
        [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]
1521

1522
        sage: E = EllipticCurve([1, 1, 0, -660, -7600])
1523
        sage: isogenies_prime_degree_genus_plus_0(E, 17)
1524
        [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]
1525

1526
        sage: E = EllipticCurve([0, 0, 1, -1862, -30956])
1527
        sage: isogenies_prime_degree_genus_plus_0(E, 19)
1528
        [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]
1529

1530
        sage: K = QuadraticField(-295,'a')
1531
        sage: a = K.gen()
1532
        sage: E = EllipticCurve_from_j(-484650135/16777216*a + 4549855725/16777216)
1533
        sage: isogenies_prime_degree_genus_plus_0(E, 23)
1534
        [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]
1535

1536
        sage: K = QuadraticField(-199,'a')
1537
        sage: a = K.gen()
1538
        sage: E = EllipticCurve_from_j(94743000*a + 269989875)
1539
        sage: isogenies_prime_degree_genus_plus_0(E, 29)
1540
        [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]
1541

1542
        sage: K = QuadraticField(253,'a')
1543
        sage: a = K.gen()
1544
        sage: E = EllipticCurve_from_j(208438034112000*a - 3315409892960000)
1545
        sage: isogenies_prime_degree_genus_plus_0(E, 31)
1546
        [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]
1547

1548
        sage: E = EllipticCurve_from_j(GF(5)(1))
1549
        sage: isogenies_prime_degree_genus_plus_0(E, 41)
1550
        [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]
1551

1552
        sage: K = QuadraticField(5,'a')
1553
        sage: a = K.gen()
1554
        sage: E = EllipticCurve_from_j(184068066743177379840*a - 411588709724712960000)
1555
        sage: isogenies_prime_degree_genus_plus_0(E, 47) # long time (4.3s)
1556
        [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]
1557

1558
        sage: K = QuadraticField(-66827,'a')
1559
        sage: a = K.gen()
1560
        sage: E = EllipticCurve_from_j(-98669236224000*a + 4401720074240000)
1561
        sage: isogenies_prime_degree_genus_plus_0(E, 59)   # long time (25s, 2012)
1562
        [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]
1563

1564
        sage: E = EllipticCurve_from_j(GF(13)(5))
1565
        sage: isogenies_prime_degree_genus_plus_0(E, 71) # long time
1566
        [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]
1567

1568
        sage: E = EllipticCurve(GF(13),[0,1,1,1,0])
1569
        sage: isogenies_prime_degree_genus_plus_0(E)
1570
        [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,
1571
        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,
1572
        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,
1573
        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,
1574
        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,
1575
        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]
1576

1577
    """
1578
    if l is None:
1579
        return sum([isogenies_prime_degree_genus_plus_0(E, l) for l in hyperelliptic_primes],[])
1580

1581
    if not l in hyperelliptic_primes:
1582
        raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
1583

1584
    F = E.base_ring()
1585
    j = E.j_invariant()
1586
    if F.characteristic() in [2, 3, l]:
1587
        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.")
1588

1589
    if j == F(0):
1590
        return isogenies_prime_degree_genus_plus_0_j0(E, l)
1591
    if j == F(1728):
1592
        return isogenies_prime_degree_genus_plus_0_j1728(E, l)
1593

1594
    Fu = PolynomialRing(F,'u')
1595
    u = Fu.gen()
1596
    Fuv = PolynomialRing(F,['u','v'])
1597
    Fxuv = PolynomialRing(F,['x','u','v'])
1598
    X = u
1599
    data = _hyperelliptic_isogeny_data(l)
1600
    a = Fu(data['alpha'])
1601
    b = Fu(data['beta'])
1602
    f = Fu(data['hyper_poly'])
1603
    P = a
1604
    Q = Fu((a**2 - f*b**2)/Fu(4))
1605
    u_list = (j**2-P*j+Q).roots(multiplicities=False)
1606

1607
    S = []
1608
    for u0 in u_list:
1609
        if b(u0) == 0:
1610
            S += [[u0,v0] for v0 in (X**2-f(u0)).roots(multiplicities=False)]
1611
        else:
1612
            S += [[u0,(2*j-a(u0))/b(u0)]]
1613
    if len(S) == 0:
1614
        return []
1615
    S.sort()
1616

1617
    c4, c6 = E.c_invariants()
1618
    b2 = E.b2()
1619
    kernels = []
1620

1621
    psi = Fxuv(Psi2(l))
1622
    for u0, v0 in S:
1623
        A4 = Fuv(data['A4'])(u0,v0) #non-zero since j!=0
1624
        A6 = Fuv(data['A6'])(u0,v0) #non-zero since j!=1728
1625
        T = (c4*A6)/(2*c6*A4)
1626
        kernels += [psi((36*X+3*b2)*T,u0,v0).monic()]
1627
    return [E.isogeny(ker) for ker in kernels]
1628

1629

1630

1631
def isogenies_prime_degree_genus_plus_0_j0(E, l):
1632
    """
1633
    Returns a list of hyperelliptic ``l`` -isogenies  with domain ``E`` when `j(E)=0`.
1634

1635
    INPUT:
1636

1637
    - ``E`` -- an elliptic curve with j-invariant 0.
1638

1639
    - ``l`` -- 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
1640

1641
    OUTPUT:
1642

1643
    (list) a list of all isogenies of degree 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
1644

1645
    .. note::
1646

1647
       This implementation requires that the characteristic is not 2, 3 or ``l``.
1648

1649
    .. note::
1650

1651
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``.
1652

1653
    EXAMPLES::
1654

1655
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_plus_0_j0
1656

1657
        sage: u = polygen(QQ)
1658
        sage: K.<a> = NumberField(u^4+228*u^3+486*u^2-540*u+225)
1659
        sage: E = EllipticCurve(K,[0,-121/5*a^3-20691/5*a^2-29403/5*a+3267])
1660
        sage: isogenies_prime_degree_genus_plus_0_j0(E,11)
1661
        [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]
1662

1663
        sage: E = EllipticCurve(GF(5^6,'a'),[0,1])
1664
        sage: isogenies_prime_degree_genus_plus_0_j0(E,17)
1665
        [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]
1666
    """
1667
    if not l in hyperelliptic_primes:
1668
        raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
1669
    F = E.base_field()
1670
    if E.j_invariant() != 0:
1671
        raise ValueError,("j-invariant must be 0.")
1672
    if F.characteristic() in [2,3,l]:
1673
        raise NotImplementedError("Not implemented in characteristic 2, 3 or l.")
1674

1675
    Fu = PolynomialRing(F,'u')
1676
    u = Fu.gen()
1677
    Fuv = PolynomialRing(F,['u','v'])
1678
    Fxuv = PolynomialRing(F,['x','u','v'])
1679
    X = u
1680
    data = _hyperelliptic_isogeny_data(l)
1681
    a = Fu(data['alpha'])
1682
    b = Fu(data['beta'])
1683
    f = Fu(data['hyper_poly'])
1684
    Q = Fu((a**2 - f*b**2)/Fu(4))
1685
    u_list = Q.roots(multiplicities=False)
1686
    c6, b2 = E.c6(), E.b2()
1687
    kernels = []
1688

1689
    if l % 3 == 1 and F(-3).is_square():
1690
        p = F(-3).sqrt()
1691
        endo = Fxuv(data['endo'])
1692
        kernels += [endo(36*X+3*b2,p,-54*c6).monic(), endo(36*X+3*b2,-p,-54*c6).monic()]
1693

1694
    S = []
1695
    for u0 in u_list:
1696
        if l % 3 == 1 and u0 == F(data['endo_u']):
1697
            continue
1698
        if b(u0) == 0:
1699
            S += [[u0,v0] for v0 in (X**2-f(u0)).roots(multiplicities=False)]
1700
        else:
1701
            S += [[u0,-a(u0)/b(u0)]]
1702
    if len(S)==0 and len(kernels) == 0:
1703
        return []
1704
    S.sort()
1705

1706
    psi = Fxuv(Psi2(l))
1707
    for u0,v0 in S:
1708
        A6 = Fuv(data['A6'])(u0,v0) # non-zero since j!=1728
1709
        kernels += [psi((36*X+3*b2)*T,u0,v0).monic() for T in (X**3-A6/(-54*c6)).roots(multiplicities=False)]
1710
    return [E.isogeny(ker) for ker in kernels]
1711

1712
def isogenies_prime_degree_genus_plus_0_j1728(E, l):
1713
    """
1714
    Returns a list of ``l`` -isogenies  with domain ``E`` when `j(E)=1728`.
1715

1716
    INPUT:
1717

1718
    - ``E`` -- an elliptic curve with j-invariant 1728.
1719

1720
    - ``l`` -- 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
1721

1722
    OUTPUT:
1723

1724
    (list) a list of all isogenies of degree 11, 17, 19, 23, 29, 31, 41, 47, 59, or 71.
1725

1726
    .. note::
1727

1728
       This implementation requires that the characteristic is not 2, 3 or ``l``.
1729

1730
    .. note::
1731

1732
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree(l)``.
1733

1734
    EXAMPLES::
1735

1736
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_genus_plus_0_j1728
1737

1738
        sage: u = polygen(QQ)
1739
        sage: K.<a> = NumberField(u^6 - 522*u^5 - 10017*u^4 + 2484*u^3 - 5265*u^2 + 12150*u - 5103)
1740
        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])
1741
        sage: isogenies_prime_degree_genus_plus_0_j1728(E,11)
1742
        [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]
1743
        sage: i = QuadraticField(-1,'i').gen()
1744
        sage: E = EllipticCurve([-1-2*i,0])
1745
        sage: isogenies_prime_degree_genus_plus_0_j1728(E,17)
1746
        [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,
1747
        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]
1748
        sage: Emin = E.global_minimal_model()
1749
        sage: [(p,len(isogenies_prime_degree_genus_plus_0_j1728(Emin,p))) for p in [17, 29, 41]]
1750
        [(17, 2), (29, 2), (41, 2)]
1751
    """
1752
    if not l in  hyperelliptic_primes:
1753
        raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
1754
    F = E.base_ring()
1755
    if E.j_invariant() != 1728:
1756
        raise ValueError("j-invariant must be 1728.")
1757
    if F.characteristic() in [2,3,l]:
1758
        raise NotImplementedError("Not implemented in characteristic 2, 3 or l.")
1759

1760
    Fu = PolynomialRing(F,'u')
1761
    u = Fu.gen()
1762
    Fuv = PolynomialRing(F,['u','v'])
1763
    Fxuv = PolynomialRing(F,['x','u','v'])
1764
    X = u
1765
    data = _hyperelliptic_isogeny_data(l)
1766
    a = Fu(data['alpha'])
1767
    b = Fu(data['beta'])
1768
    f = Fu(data['hyper_poly'])
1769
    P = a
1770
    Q = Fu((a**2 - f*b**2)/Fu(4))
1771
    u_list = (1728**2-P*1728+Q).roots(multiplicities=False)
1772
    c4, b2 = E.c4(), E.b2()
1773
    kernels = []
1774

1775
    if l % 4 == 1 and  F(-1).is_square():
1776
        i = F(-1).sqrt()
1777
        endo = Fxuv(data['endo'])
1778
        kernels += [endo(36*X+3*b2,i,-27*c4).monic(), endo(36*X+3*b2,-i,-27*c4).monic()]
1779

1780
    S = []
1781
    for u0 in u_list:
1782
        if l % 4 == 1 and u0 == F(data['endo_u']):
1783
            continue
1784
        if b(u0) == 0:
1785
            S += [[u0,v0] for v0 in (X**2-f(u0)).roots(multiplicities=False)]
1786
        else:
1787
            S += [[u0,(2*1728-a(u0))/b(u0)]]
1788
    if len(S)==0 and len(kernels) == 0:
1789
        return []
1790
    S.sort()
1791

1792
    psi = Fxuv(Psi2(l))
1793
    for u0,v0 in S:
1794
        A4 = Fuv(data['A4'])(u0,v0) # non-zero since j!=0
1795
        kernels += [psi((36*X+3*b2)*T,u0,v0).monic() for T in (X**2-A4/(-27*c4)).roots(multiplicities=False)]
1796
    return [E.isogeny(ker) for ker in kernels]
1797

1798
@cached_function
1799
def _least_semi_primitive(p):
1800
    """
1801
    Returns the smallest semi-primitive root modulo `p`, i.e., generator of the group `(\ZZ/p\ZZ)^*/\{1,-1\}`.
1802

1803
    INPUT:
1804

1805
    - ``p`` -- an odd prime.
1806

1807
    OUTPUT:
1808

1809
    the smallest semi-primitive root modulo `p`.
1810

1811
    .. note::
1812

1813
       This function would normally be invoked indirectly via ``E.isogenies_prime_degree_general(l)``.
1814

1815
    EXAMPLES::
1816

1817
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import _least_semi_primitive
1818
        sage: _least_semi_primitive(5)
1819
        2
1820
        sage: _least_semi_primitive(13)
1821
        2
1822
        sage: _least_semi_primitive(17)
1823
        3
1824
        sage: _least_semi_primitive(73)
1825
        5
1826
        sage: _least_semi_primitive(997)
1827
        7
1828
    """
1829
    if not p.is_prime() or p<3:
1830
        raise ValueError("%s is not an odd prime"%p)
1831

1832
    def is_semi_primitive(a,p):
1833
        from sage.rings.finite_rings.integer_mod_ring import Integers
1834
        d = Integers(p)(a).multiplicative_order()
1835
        if p%4==1:
1836
            return (d==p-1)
1837
        else:
1838
            return d >= (p-1)/2
1839

1840
    a = 2
1841
    while not is_semi_primitive(a,p):
1842
        a += 1
1843
    return a
1844

1845

1846
def isogenies_prime_degree_general(E, l):
1847
    """
1848
    Returns a list of ``l`` -isogenies  with domain ``E``.
1849

1850
    INPUT:
1851

1852
    - ``E`` -- an elliptic curve.
1853

1854
    - ``l`` -- a prime.
1855

1856
    OUTPUT:
1857

1858
    (list) a list of all isogenies of degree l.
1859

1860
    ALGORITHM:
1861

1862
    This algorithm factors the ``l``-division polynomial, then
1863
    combines its factors to otain kernels. See [KT2013]_, Chapter 3.
1864

1865
    .. note::
1866

1867
       This function works for any prime `l`.  Normally one should use
1868
       the function :meth:`isogenies_prime_degree` which uses special
1869
       functions for certain small primes.
1870

1871
    EXAMPLES::
1872

1873
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general
1874
        sage: E = EllipticCurve_from_j(GF(2^6,'a')(1))
1875
        sage: isogenies_prime_degree_general(E, 7)
1876
        [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]
1877
        sage: E = EllipticCurve_from_j(GF(3^12,'a')(2))
1878
        sage: isogenies_prime_degree_general(E, 17)
1879
        [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]
1880
        sage: E = EllipticCurve('50a1')
1881
        sage: isogenies_prime_degree_general(E, 3)
1882
        [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]
1883
        sage: isogenies_prime_degree_general(E, 5)
1884
        [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]
1885
        sage: E = EllipticCurve([0, 0, 1, -1862, -30956])
1886
        sage: isogenies_prime_degree_general(E, 19)
1887
        [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]
1888
        sage: E = EllipticCurve([0, -1, 0, -6288, 211072])
1889
        sage: isogenies_prime_degree_general(E, 37)  # long time (10s)
1890
        [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]
1891

1892
        sage: E = EllipticCurve([-3440, 77658])
1893
        sage: isogenies_prime_degree_general(E, 43)  # long time (16s)
1894
        [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]
1895

1896
    Isogenies of degree equal to the characteristic are computed (but
1897
    only the separable isogeny).  In the following example we consider
1898
    an elliptic curve which is supersingular in characteristic 2
1899
    only::
1900

1901
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general
1902
        sage: ainvs = (0,1,1,-1,-1)
1903
        sage: for l in prime_range(50):
1904
        ....:     E = EllipticCurve(GF(l),ainvs)
1905
        ....:     isogenies_prime_degree_general(E,l)
1906
        []
1907
        [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]
1908
        [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]
1909
        [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]
1910
        [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]
1911
        [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]
1912
        [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]
1913
        [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]
1914
        [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]
1915
        [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]
1916
        [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]
1917
        [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]
1918
        [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]
1919
        [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]
1920
        [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]
1921

1922
    """
1923
    if not l.is_prime():
1924
        raise ValueError("%s is not prime."%l)
1925
    if l==2:
1926
        return isogenies_2(E)
1927
    if l==3:
1928
        return isogenies_3(E)
1929

1930
    psi_l = E.division_polynomial(l)
1931
    factors = [h for h,e in psi_l.factor() if (l-1)/2 % h.degree() == 0]
1932
    a = _least_semi_primitive(l)
1933
    m = E.multiplication_by_m(a, x_only=True)
1934
    F = psi_l.parent()
1935
    x = F.gen()
1936
    ker = []
1937
    from sage.rings.arith import gcd
1938
    from sage.misc.all import prod
1939
    def mult(f):
1940
        return gcd(F(f(m(x)).numerator()),psi_l).monic()
1941
    while len(factors) > 0:
1942
        f = factors[0]
1943
        factors.remove(f)
1944
        d = f.degree()
1945
        S = [f]
1946
        for i in range((l-1)/(2*d)-1):
1947
            g = mult(S[i])
1948
            S.append(g)
1949
            if g in factors:
1950
                factors.remove(g)
1951
        if mult(S[-1]) == f:
1952
            ker.append(prod(S))
1953
    return [E.isogeny(k) for k in ker]
1954

1955
def isogenies_prime_degree(E, l):
1956
    """
1957
    Returns a list of ``l`` -isogenies  with domain ``E``.
1958

1959
    INPUT:
1960

1961
    - ``E`` -- an elliptic curve.
1962

1963
    - ``l`` -- a prime.
1964

1965
    OUTPUT:
1966

1967
    (list) a list of all isogenies of degree `l`.  If the
1968
    characteristic is `l` then only separable isogenies are
1969
    constructed.
1970

1971
    EXAMPLES::
1972

1973
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree
1974
        sage: E = EllipticCurve_from_j(GF(2^6,'a')(1))
1975
        sage: isogenies_prime_degree(E, 7)
1976
        [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]
1977
        sage: E = EllipticCurve_from_j(GF(3^12,'a')(2))
1978
        sage: isogenies_prime_degree(E, 17)
1979
        [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]
1980
        sage: E = EllipticCurve('50a1')
1981
        sage: isogenies_prime_degree(E, 3)
1982
        [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]
1983
        sage: isogenies_prime_degree(E, 5)
1984
        [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]
1985
        sage: E = EllipticCurve([0, 0, 1, -1862, -30956])
1986
        sage: isogenies_prime_degree(E, 19)
1987
        [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]
1988
        sage: E = EllipticCurve([0, -1, 0, -6288, 211072])
1989
        sage: isogenies_prime_degree(E, 37)
1990
        [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]
1991

1992

1993
    Isogenies of degree equal to the characteristic are computed (but
1994
    only the separable isogeny).  In the following example we consider
1995
    an elliptic curve which is supersingular in characteristic 2
1996
    only::
1997

1998
        sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree
1999
        sage: ainvs = (0,1,1,-1,-1)
2000
        sage: for l in prime_range(50):
2001
        ....:     E = EllipticCurve(GF(l),ainvs)
2002
        ....:     isogenies_prime_degree(E,l)
2003
        []
2004
        [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]
2005
        [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]
2006
        [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]
2007
        [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]
2008
        [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]
2009
        [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]
2010
        [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]
2011
        [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]
2012
        [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]
2013
        [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]
2014
        [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]
2015
        [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]
2016
        [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]
2017
        [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]
2018

2019
    Note that the computation is faster for degrees equal to one of
2020
    the genus 0 primes (2, 3, 5, 7, 13) or one of the hyperelliptic
2021
    primes (11, 17, 19, 23, 29, 31, 41, 47, 59, 71) than when the
2022
    generic code must be used::
2023

2024
        sage: E = EllipticCurve(GF(101), [-3440, 77658])
2025
        sage: E.isogenies_prime_degree(71) # fast
2026
        []
2027
        sage: E.isogenies_prime_degree(73) # not tested (very long time: 32s)
2028
        []
2029

2030

2031
    """
2032
    if not l.is_prime():
2033
        raise ValueError("%s is not prime."%l)
2034
    if l==2:
2035
        return isogenies_2(E)
2036
    if l==3:
2037
        return isogenies_3(E)
2038

2039
    p = E.base_ring().characteristic()
2040
    if l==p:
2041
        return isogenies_prime_degree_general(E,l)
2042

2043
    if l in [5,7,13] and not p in [2,3]:
2044
        return isogenies_prime_degree_genus_0(E,l)
2045

2046
    if l in hyperelliptic_primes and not p in [2,3]:
2047
        return isogenies_prime_degree_genus_plus_0(E,l)
2048

2049
    return isogenies_prime_degree_general(E,l)
2050

2051
Product

Resources

Company
