# Ticket #16115: ell_curve_isogeny.py

File ell_curve_isogeny.py, 138.3 KB (added by sbesnier, 6 years ago)

first draft

Line
1r"""
2Isogenies
3
4An isogeny \varphi: E_1\to E_2 between two elliptic curves E_1 and
5E_2 is a morphism of curves that sends the origin of E_1 to the
6origin of E_2. Such a morphism is automatically a morphism of group
7schemes and the kernel is a finite subgroup scheme of E_1.  Such a
8subscheme can either be given by a list of generators, which have to
9be torsion points, or by a polynomial in the coordinate x of the
10Weierstrass equation of E_1.
11
12The usual way to create and work with isogenies is illustrated with
13the following example::
14
15    sage: k = GF(11)
16    sage: E = EllipticCurve(k,[1,1])
17    sage: Q = E(6,5)
18    sage: phi = E.isogeny(Q)
19    sage: phi
20    Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 7*x + 8 over Finite Field of size 11
21    sage: P = E(4,5)
22    sage: phi(P)
23    (10 : 0 : 1)
24    sage: phi.codomain()
25    Elliptic Curve defined by y^2 = x^3 + 7*x + 8 over Finite Field of size 11
26    sage: phi.rational_maps()
27    ((x^7 + 4*x^6 - 3*x^5 - 2*x^4 - 3*x^3 + 3*x^2 + x - 2)/(x^6 + 4*x^5 - 4*x^4 - 5*x^3 + 5*x^2), (x^9*y - 5*x^8*y - x^7*y + x^5*y - x^4*y - 5*x^3*y - 5*x^2*y - 2*x*y - 5*y)/(x^9 - 5*x^8 + 4*x^6 - 3*x^4 + 2*x^3))
28
29The functions directly accessible from an elliptic curve E over a
30field are isogeny and isogeny_codomain.
31
32The most useful functions that apply to isogenies are
33
34- codomain
35- degree
36- domain
37- dual
38- rational_maps
39- kernel_polynomial
40
41.. Warning::
42
43   Only cyclic, separable isogenies are implemented (except for [2]). Some
44   algorithms may need the isogeny to be normalized.
45
46AUTHORS:
47
48- Daniel Shumow <shumow@gmail.com>: 2009-04-19: initial version
49
50- Chris Wuthrich : 7/09: changes: add check of input, not the full list is needed.
51  10/09: eliminating some bugs.
52
53"""
54
55#*****************************************************************************
56#       Copyright (C) 2009 Daniel Shumow <shumow@gmail.com>
57#
60#*****************************************************************************
61
62from copy import deepcopy, copy
63
64from sage.categories import homset
65
66from sage.categories.morphism import Morphism
67
68from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
69from sage.rings.polynomial.polynomial_ring import polygen
70from sage.rings.all import Integer, ZZ
71from sage.rings.laurent_series_ring import LaurentSeriesRing
72from sage.rings.polynomial.all import is_Polynomial
73from sage.schemes.elliptic_curves.all import EllipticCurve
74from sage.schemes.elliptic_curves.all import is_EllipticCurve
75
76from sage.rings.number_field.number_field_base import is_NumberField
77
78from sage.rings.rational_field import is_RationalField, QQ
79
80from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
81
82from sage.sets.set import Set
83
84from sage.misc.cachefunc import cached_function
85
86#
87# Private function for parsing input to determine the type of
88# algorithm
89#
90def isogeny_determine_algorithm(E, kernel, codomain, degree, model):
91    r"""
92    Helper function that allows the various isogeny functions to infer
93    the algorithm type from the parameters passed in.
94
95    If kernel is a list of points on the EllipticCurve E, then
96    we assume the algorithm to use is Velu.
97
98    If kernel is a list of coefficients or a univariate polynomial
99    we try to use the Kohel's algorithms.
100
101    EXAMPLES:
102
103    This helper function will be implicitly called by the following examples::
104
105        sage: R.<x> = GF(5)[]
106        sage: E = EllipticCurve(GF(5), [0,0,0,1,0])
107        sage: phi = EllipticCurveIsogeny(E, x+3)
108        sage: phi2 = EllipticCurveIsogeny(E, [GF(5)(3),GF(5)(1)])
109        sage: phi == phi2
110        True
111        sage: phi3 = EllipticCurveIsogeny(E,  E((2,0)) )
112        sage: phi3 == phi2
113        True
114        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_determine_algorithm
115        sage: isogeny_determine_algorithm(E, x+3, None, None, None)
116        'kohel'
117        sage: isogeny_determine_algorithm(E, [3, 1], None, None, None)
118        'kohel'
119        sage: isogeny_determine_algorithm(E, E((2,0)), None, None, None)
120        'velu'
121
122    """
123
124    kernel_is_list = (type(kernel) == list)
125
126    if not kernel_is_list and kernel in E :
127        kernel = [kernel]
128        kernel_is_list = True
129
130    if (is_Polynomial(kernel) or ( kernel_is_list) and (kernel[0] in E.base_ring()) ):
131        algorithm = "kohel"
132    elif (kernel_is_list) and (kernel[0] in E): # note that if kernel[0] is on an extension of E this condition will be false
133        algorithm = "velu"
134    else:
135        raise ValueError, "Invalid Parameters to EllipticCurveIsogeny constructor."
136
137    return algorithm
138
139
140def isogeny_codomain_from_kernel(E, kernel, degree=None):
141    r"""
142    This function computes the isogeny codomain given a kernel.
143
144    INPUT:
145
146    - E - The domain elliptic curve.
147
148    - kernel - Either a list of points in the kernel of the isogeny, or a
149                   kernel polynomial (specified as a either a univariate
150                   polynomial or a coefficient list.)
151
152    - degree - an integer, (default:None)  optionally specified degree
153                   of the kernel.
154
155    OUTPUT:
156
157    (elliptic curve) the codomain of the separable normalized isogeny
158    from this kernel
159
160    EXAMPLES::
161
162        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_codomain_from_kernel
163        sage: E = EllipticCurve(GF(7), [1,0,1,0,1])
164        sage: R.<x> = GF(7)[]
165        sage: isogeny_codomain_from_kernel(E, [4,1], degree=3)
166        Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7
167        sage: EllipticCurveIsogeny(E, [4,1]).codomain() == isogeny_codomain_from_kernel(E, [4,1], degree=3)
168        True
169        sage: isogeny_codomain_from_kernel(E, x^3 + x^2 + 4*x + 3)
170        Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7
171        sage: isogeny_codomain_from_kernel(E, x^3 + 2*x^2 + 4*x + 3)
172        Elliptic Curve defined by y^2 + x*y + y = x^3 + 5*x + 2 over Finite Field of size 7
173
174        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
175        sage: kernel_list = [E((15,10)), E((10,3)),E((6,5))]
176        sage: isogeny_codomain_from_kernel(E, kernel_list)
177        Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19
178
179    """
180
181    algorithm = isogeny_determine_algorithm(E, kernel, None, degree, None);
182
183    if ("velu"==algorithm):
184        # if we are using Velu's formula, just instantiate the isogeny
185        # and return the codomain
186        codomain = EllipticCurveIsogeny(E, kernel).codomain()
187    elif ("kohel"==algorithm):
188        codomain = compute_codomain_kohel(E, kernel, degree)
189
190    return codomain
191
192
193def compute_codomain_formula(E, v, w):
194    r"""
195    Given parameters v and w (as in Velu / Kohel / etc formulas)
196    computes the codomain curve.
197
198    EXAMPLES:
199
200    This formula is used by every Isogeny Instantiation::
201
202        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
203        sage: phi = EllipticCurveIsogeny(E, E((1,2)) )
204        sage: phi.codomain()
205        Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19
206        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_formula
207        sage: v = phi._EllipticCurveIsogeny__v
208        sage: w = phi._EllipticCurveIsogeny__w
209        sage: compute_codomain_formula(E, v, w)
210        Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19
211
212    """
213
214    a1,a2,a3,a4,a6 = E.ainvs()
215
216    A4 = a4 - 5*v
217    A6 = a6 - (a1**2 + 4*a2)*v - 7*w
218
219    return EllipticCurve([a1, a2, a3, A4, A6])
220
221
222def compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4):
223    r"""
224    The formula for computing v and w using Kohel's formulas for
225    isogenies of degree 2.
226
227    EXAMPLES:
228
229    This function will be implicitly called by the following example::
230
231        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
232        sage: phi = EllipticCurveIsogeny(E, [9,1])
233        sage: phi
234        Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 19 to Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19
235        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg1
236        sage: a1,a2,a3,a4,a6 = E.ainvs()
237        sage: x0 = -9
238        sage: y0 = -(a1*x0 + a3)/2
239        sage: compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4)
240        (18, 9)
241
242    """
243
244    v = (3*x0**2 + 2*a2*x0 + a4 - a1*y0)
245    w = x0*v
246
247    return (v,w)
248
249
250def compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3):
251    r"""
252    The formula for computing v and w using Kohel's formulas for
253    isogenies of degree 3.
254
255    EXAMPLES:
256
257    This function will be implicitly called by the following example::
258
259        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
260        sage: R.<x> = GF(19)[]
261        sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12)
262        sage: phi
263        Isogeny of degree 4 from Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 19 to Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19
264        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg3
265        sage: (b2,b4) = (E.b2(), E.b4())
266        sage: (s1, s2, s3) = (-7, 15, -12)
267        sage: compute_vw_kohel_even_deg3(b2, b4, s1, s2, s3)
268        (4, 7)
269
270    """
271
272    temp1 = (s1**2 - 2*s2)
273    v = 3*temp1 + b2*s1/2 + 3*b4/2
274    w = 3*(s1**3 - 3*s1*s2 + 3*s3) + b2*temp1/2 + b4*s1/2
275
276    return (v,w)
277
278
279def compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n):
280    r"""
281    This function computes the v and w according to Kohel's formulas.
282
283    EXAMPLES:
284
285    This function will be implicitly called by the following example::
286
287        sage: E = EllipticCurve(GF(19), [18,17,16,15,14])
288        sage: R.<x> = GF(19)[]
289        sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11)
290        sage: phi
291        Isogeny of degree 7 from Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 15*x + 14 over Finite Field of size 19 to Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19
292        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_odd
293        sage: (b2,b4,b6) = (E.b2(), E.b4(), E.b6())
294        sage: (s1,s2,s3) = (-14,3,-11)
295        sage: compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,3)
296        (7, 1)
297
298    """
299
300    v = 6*(s1**2 - 2*s2) + b2*s1 + n*b4
301    w = 10*(s1**3 - 3*s1*s2 + 3*s3) + 2*b2*(s1**2 - 2*s2) + 3*b4*s1 + n*b6
302
303    return (v,w)
304
305
306def compute_codomain_kohel(E, kernel, degree):
307    r"""
308    This function computes the codomain from the kernel polynomial as
309    per Kohel's formulas.
310
311    EXAMPLES::
312
313        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_kohel
314        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
315        sage: phi = EllipticCurveIsogeny(E, [9,1])
316        sage: phi.codomain() == isogeny_codomain_from_kernel(E, [9,1])
317        True
318        sage: compute_codomain_kohel(E, [9,1], 2)
319        Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19
320        sage: R.<x> = GF(19)[]
321        sage: E = EllipticCurve(GF(19), [18,17,16,15,14])
322        sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11)
323        sage: phi.codomain() == isogeny_codomain_from_kernel(E, x^3 + 14*x^2 + 3*x + 11)
324        True
325        sage: compute_codomain_kohel(E, x^3 + 14*x^2 + 3*x + 11, 7)
326        Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19
327        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
328        sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12)
329        sage: isogeny_codomain_from_kernel(E, x^3 + 7*x^2 + 15*x + 12) == phi.codomain()
330        True
331        sage: compute_codomain_kohel(E, x^3 + 7*x^2 + 15*x + 12,4)
332        Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19
333
334    NOTES:
335
336        This function uses the formulas of Section 2.4 of [K96].
337
338    REFERENCES:
339
340    - [K96] Kohel, "Endomorphism Rings of Elliptic Curves over Finite Fields"
341
342    """
343
344    # First set up the polynomial ring
345
346    base_field = E.base_ring()
347
348    if (is_Polynomial(kernel)):
349        psi = kernel
350        kernel_list = psi.list()
351        poly_ring = psi.parent()
352        x = psi.variables()[0]
353    elif (list == type(kernel)) and (kernel[0] in base_field):
354        kernel_list = kernel
355        poly_ring = base_field.polynomial_ring()
356        psi = poly_ring(kernel_list)
357        x = poly_ring.gen()
358    else:
359        raise ValueError, "input not of correct type"
360
361
362    # next determine the even / odd part of the isogeny
363    psi_2tor = two_torsion_part(E, poly_ring, psi, degree)
364
365    if (0 != psi_2tor.degree()): # even degree case
366
367        psi_quo = poly_ring(psi/psi_2tor)
368
369        if (0 != psi_quo.degree()):
370            raise ArithmeticError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion."
371
372        n = psi_2tor.degree()
373
374        if (1 == n):
375
376            a1,a2,a3,a4,a6 = E.ainvs()
377
378            x0 = -psi_2tor.constant_coefficient()
379
380            # determine y0
381            if (2 == base_field.characteristic()):
382                y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt()
383            else:
384                y0 = -(a1*x0 + a3)/2
385
386            (v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4)
387
388        elif (3 == n):
389
390            b2 = E.b2()
391            b4 = E.b4()
392
393            s = psi_2tor.list()
394            s1 = -s[n-1]
395            s2 = s[n-2]
396            s3 = -s[n-3]
397
398            (v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3)
399
400    else:
401
402        n = psi.degree()
403
404        b2 = E.b2()
405        b4 = E.b4()
406        b6 = E.b6()
407
408        s1 = 0; s2 = 0; s3 = 0
409
410        if (1 <= n):
411            s1 = -kernel_list[n-1]
412
413        if (2 <= n):
414            s2 = kernel_list[n-2]
415
416        if (3 <= n):
417            s3 = -kernel_list[n-3]
418
419        # initializing these allows us to calculate E2.
420        (v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n);
421
422    return compute_codomain_formula(E, v, w)
423
424
425def two_torsion_part(E, poly_ring, psi, degree):
426    r"""
427
428    Returns the greatest common divisor of psi and the 2 torsion
429    polynomial of E.
430
431    EXAMPLES:
432
433    Every function that computes the kernel polynomial via Kohel's
434    formulas will call this function::
435
436        sage: E = EllipticCurve(GF(19), [1,2,3,4,5])
437        sage: R.<x> = GF(19)[]
438        sage: phi = EllipticCurveIsogeny(E, x + 13)
439        sage: isogeny_codomain_from_kernel(E, x + 13) == phi.codomain()
440        True
441        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part
442        sage: two_torsion_part(E, R, x+13, 2)
443        x + 13
444
445    """
446    if (None==degree) or (0 == degree % 2):
447
448        x = poly_ring.gens()[0]
449        psi_2 = E.two_division_polynomial(x)
450        psi_G = poly_ring(psi.gcd(psi_2))
451
452    else:
453
454        psi_G = poly_ring(1)
455
456    return psi_G
457
458
459class EllipticCurveIsogeny(Morphism):
460    r"""
461    Class Implementing Isogenies of Elliptic Curves
462
463    This class implements cyclic, separable, normalized isogenies of
464    elliptic curves.
465
466    Several different algorithms for computing isogenies are
467    available.  These include:
468
469    - Velu's Formulas: Velu's original formulas for computing
470      isogenies.  This algorithm is selected by giving as the
471      kernel parameter a list of points which generate a finite
472      subgroup.
473
474    - Kohel's Formulas: Kohel's original formulas for computing
475      isogenies.  This algorithm is selected by giving as the
476      kernel parameter a monic polynomial (or a coefficient list
477      (little endian)) which will define the kernel of the isogeny.
478
479    INPUT:
480
481    - E         - an elliptic curve, the domain of the isogeny to
482                      initialize.
483
484    - kernel    - a kernel, either a point in E, a list of points
485                      in E, a monic kernel polynomial, or None.
486                      If initializing from a domain/codomain, this must be
487                      set to None.
488
489    - codomain  - an elliptic curve (default:None).  If kernel
490                      is None, then this must be the codomain of a cyclic,
491                      separable, normalized isogeny, furthermore, degree
492                      must be the degree of the isogeny from E to
493                      codomain. If kernel is not None, then this
494                      must be isomorphic to the codomain of the cyclic normalized
495                      separable isogeny defined by kernel, in this case, the
496                      isogeny is post composed with an isomorphism so that this
497                      parameter is the codomain.
498
499    - degree    - an integer (default:None).
500                      If kernel is None, then this is the degree of the
501                      isogeny from E to codomain.
502                      If kernel is not None, then this is used to determine
503                      whether or not to skip a gcd of the kernel polynomial with the
504                      two torsion polynomial of E.
505
506    - model     - a string (default:None).  Only supported variable is
507                      minimal, in which case if E is a curve over the
508                      rationals, then the codomain is set to be the unique global
509                      minimum model.
510
511    - check (default: True) checks if the input is valid to define an isogeny
512
513    EXAMPLES:
514
515    A simple example of creating an isogeny of a field of small
516    characteristic::
517
518        sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
519        sage: phi = EllipticCurveIsogeny(E, E((0,0)) ); phi
520        Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7
521        sage: phi.degree() == 2
522        True
523        sage: phi.kernel_polynomial()
524        x
525        sage: phi.rational_maps()
526        ((x^2 + 1)/x, (x^2*y - y)/x^2)
527        sage: phi == loads(dumps(phi))  # known bug
528        True
529
530    A more complicated example of a characteristic 2 field::
531
532        sage: E = EllipticCurve(GF(2^4,'alpha'), [0,0,1,0,1])
533        sage: P = E((1,1))
534        sage: phi_v = EllipticCurveIsogeny(E, P); phi_v
535        Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field in alpha of size 2^4
536        sage: phi_ker_poly = phi_v.kernel_polynomial()
537        sage: phi_ker_poly
538        x + 1
539        sage: ker_poly_list = phi_ker_poly.list()
540        sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list)
541        sage: phi_k == phi_v
542        True
543        sage: phi_k.rational_maps()
544        ((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1))
545        sage: phi_v.rational_maps()
546        ((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1))
547        sage: phi_k.degree() == phi_v.degree()
548        True
549        sage: phi_k.degree()
550        3
551        sage: phi_k.is_separable()
552        True
553        sage: phi_v(E(0))
554        (0 : 1 : 0)
555        sage: alpha = E.base_field().gen()
556        sage: Q = E((0, alpha*(alpha + 1)))
557        sage: phi_v(Q)
558        (1 : alpha^2 + alpha : 1)
559        sage: phi_v(P) == phi_k(P)
560        True
561        sage: phi_k(P) == phi_v.codomain()(0)
562        True
563
564    We can create an isogeny that has kernel equal to the full 2
565    torsion::
566
567        sage: E = EllipticCurve(GF(3), [0,0,0,1,1])
568        sage: ker_list = E.division_polynomial(2).list()
569        sage: phi = EllipticCurveIsogeny(E, ker_list); phi
570        Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3
571        sage: phi(E(0))
572        (0 : 1 : 0)
573        sage: phi(E((0,1)))
574        (1 : 0 : 1)
575        sage: phi(E((0,2)))
576        (1 : 0 : 1)
577        sage: phi(E((1,0)))
578        (0 : 1 : 0)
579        sage: phi.degree()
580        4
581
582    We can also create trivial isogenies with the trivial kernel::
583
584        sage: E = EllipticCurve(GF(17), [11, 11, 4, 12, 10])
585        sage: phi_v = EllipticCurveIsogeny(E, E(0))
586        sage: phi_v.degree()
587        1
588        sage: phi_v.rational_maps()
589        (x, y)
590        sage: E == phi_v.codomain()
591        True
592        sage: P = E.random_point()
593        sage: phi_v(P) == P
594        True
595
596        sage: E = EllipticCurve(GF(31), [23, 1, 22, 7, 18])
597        sage: phi_k = EllipticCurveIsogeny(E, [1])
598        sage: phi_k
599        Isogeny of degree 1 from Elliptic Curve defined by y^2 + 23*x*y + 22*y = x^3 + x^2 + 7*x + 18 over Finite Field of size 31 to Elliptic Curve defined by y^2 + 23*x*y + 22*y = x^3 + x^2 + 7*x + 18 over Finite Field of size 31
600        sage: phi_k.degree()
601        1
602        sage: phi_k.rational_maps()
603        (x, y)
604        sage: phi_k.codomain() == E
605        True
606        sage: phi_k.kernel_polynomial()
607        1
608        sage: P = E.random_point(); P == phi_k(P)
609        True
610
611    Velu and Kohel also work in characteristic 0::
612
613        sage: E = EllipticCurve(QQ, [0,0,0,3,4])
614        sage: P_list = E.torsion_points()
615        sage: phi = EllipticCurveIsogeny(E, P_list)
616        sage: phi
617        Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 27*x + 46 over Rational Field
618        sage: P = E((0,2))
619        sage: phi(P)
620        (6 : -10 : 1)
621        sage: phi_ker_poly = phi.kernel_polynomial()
622        sage: phi_ker_poly
623        x + 1
624        sage: ker_poly_list = phi_ker_poly.list()
625        sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k
626        Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 27*x + 46 over Rational Field
627        sage: phi_k(P) == phi(P)
628        True
629        sage: phi_k == phi
630        True
631        sage: phi_k.degree()
632        2
633        sage: phi_k.is_separable()
634        True
635
636    A more complicated example over the rationals (of odd degree)::
637
638        sage: E = EllipticCurve('11a1')
639        sage: P_list = E.torsion_points()
640        sage: phi_v = EllipticCurveIsogeny(E, P_list); phi_v
641        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field
642        sage: P = E((16,-61))
643        sage: phi_v(P)
644        (0 : 1 : 0)
645        sage: ker_poly = phi_v.kernel_polynomial(); ker_poly
646        x^2 - 21*x + 80
647        sage: ker_poly_list = ker_poly.list()
648        sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k
649        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field
650        sage: phi_k == phi_v
651        True
652        sage: phi_v(P) == phi_k(P)
653        True
654        sage: phi_k.is_separable()
655        True
656
657    We can also do this same example over the number field defined by
658    the irreducible two torsion polynomial of E::
659
660        sage: E = EllipticCurve('11a1')
661        sage: P_list = E.torsion_points()
662        sage: K.<alpha> = NumberField(x^3 - 2* x^2 - 40*x - 158)
663        sage: EK = E.change_ring(K)
664        sage: P_list = [EK(P) for P in P_list]
665        sage: phi_v = EllipticCurveIsogeny(EK, P_list); phi_v
666        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 to Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-7820)*x + (-263580) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158
667        sage: P = EK((alpha/2,-1/2))
668        sage: phi_v(P)
669        (122/121*alpha^2 + 1633/242*alpha - 3920/121 : -1/2 : 1)
670        sage: ker_poly = phi_v.kernel_polynomial()
671        sage: ker_poly
672        x^2 - 21*x + 80
673        sage: ker_poly_list = ker_poly.list()
674        sage: phi_k = EllipticCurveIsogeny(EK, ker_poly_list)
675        sage: phi_k
676        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 to Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-7820)*x + (-263580) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158
677        sage: phi_v == phi_k
678        True
679        sage: phi_k(P) == phi_v(P)
680        True
681        sage: phi_k == phi_v
682        True
683        sage: phi_k.degree()
684        5
685        sage: phi_v.is_separable()
686        True
687
688    The following example shows how to specify an isogeny from domain
689    and codomain::
690
691        sage: E = EllipticCurve('11a1')
692        sage: R.<x> = QQ[]
693        sage: f = x^2 - 21*x + 80
694        sage: phi = E.isogeny(f)
695        sage: E2 = phi.codomain()
696        sage: phi_s = EllipticCurveIsogeny(E, None, E2, 5)
697        sage: phi_s
698        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field
699        sage: phi_s == phi
700        True
701        sage: phi_s.rational_maps() == phi.rational_maps()
702        True
703
704    However only cyclic normalized isogenies can be constructed this
705    way. So it won't find the isogeny [3]::
706
707        sage: E.isogeny(None, codomain=E,degree=9)
708        Traceback (most recent call last):
709        ...
710        ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 9
711
712    Also the presumed isogeny between the domain and codomain must be
713    normalized::
714
715        sage: E2.isogeny(None,codomain=E,degree=5)
716        Traceback (most recent call last):
717        ...
718        ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 5
719        sage: phi.dual()
720        Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field
721        sage: phi.dual().is_normalized()
722        False
723
724    Here an example of a construction of a endomorphisms with cyclic
725    kernel on a CM-curve::
726
727        sage: K.<i> = NumberField(x^2+1)
728        sage: E = EllipticCurve(K, [1,0])
729        sage: RK.<X> = K[]
730        sage: f = X^2 - 2/5*i + 1/5
731        sage: phi= E.isogeny(f)
732        sage: isom = phi.codomain().isomorphism_to(E)
733        sage: phi.set_post_isomorphism(isom)
734        sage: phi.codomain() == phi.domain()
735        True
736        sage: phi.rational_maps()
737        (((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)),
738         ((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)))
739    """
740
741    ####################
742    # member variables
743    ####################
744    __check = None
745    #
746    # variables common to all algorithms
747    #
748    __E1 = None  # domain curve
749    __E2 = None  # codomain curve
750
751    __degree = None
752
753    __separable = True # This class only implements separable isogenies (for now.)
754
755    __algorithm = None
756
757    __this_hash = None
758
759    __check = None
760    #
761    # pre isomorphism
762    #
763    __intermediate_domain = None
764    __pre_isomorphism = None
765    __prei_x_coord_ratl_map = None
766    __prei_y_coord_ratl_map = None
767
768    #
769    # post isomorphism
770    #
771
772    __intermediate_codomain = None
773    __post_isomorphism = None
774    __posti_x_coord_ratl_map = None
775    __posti_y_coord_ratl_map = None
776
777    #
778    # algebraic structs
779    #
780    __base_field = None
781    __poly_ring = None
782    __x_var = None
783    __y_var = None
784
785    #
786    # Rational Maps
787    #
788    __rational_maps_initialized = False
789    __X_coord_rational_map = None
790    __Y_coord_rational_map = None
791
792    #
793    # The dual
794    #
795    __dual = None
796
797    #
798    # Kernel Data
799    #
800
801    __kernel_list = None  # list of elements in the kernel
802
803    __kernel_polynomial_list = None # polynomial stored as a little endian list of coefficients
804
805    __kernel_polynomial = None # polynomial with roots at x values for x-coordinate of points in the kernel
806
807    __inner_kernel_polynomial = None # the inner kernel polynomial (ignoring preisomorphism)
808
809    __n = None
810
811
812    #
813    # member variables common to Velu's formula
814    #
815
816    # we keep track of the 2 torsion and non2torsion separately
817    __kernel_2tor = None
818    __kernel_non2tor = None
819
820    # variables used in Velu's formula (as well as Kohel's variant)
821    __v = None
822    __w = None
823
824
825    #
826    # member variables specific to Kohel's algorithm.
827    #
828
829    __psi = None # psi polynomial
830    __phi = None # phi polynomial
831    __omega = None # omega polynomial
832
833
834    #
835    # Python Special Functions
836    #
837
838    def __init__(self, E, kernel, codomain=None, degree=None, model=None, check=True):
839        r"""
840        Constructor for EllipticCurveIsogeny class.
841
842        EXAMPLES::
843
844            sage: E = EllipticCurve(GF(2), [0,0,1,0,1])
845            sage: phi = EllipticCurveIsogeny(E, [1,1])
846            sage: phi
847            Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + 1 over Finite Field of size 2 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field of size 2
848
849            sage: E = EllipticCurve(GF(31), [0,0,0,1,0])
850            sage: P = E((2,17))
851            sage: phi = EllipticCurveIsogeny(E, P)
852            sage: phi
853            Isogeny of degree 8 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 31 to Elliptic Curve defined by y^2 = x^3 + 10*x + 28 over Finite Field of size 31
854
855            sage: E = EllipticCurve('17a1')
856            sage: phi = EllipticCurveIsogeny(E, [41/3, -55, -1, -1, 1])
857            sage: phi
858            Isogeny of degree 9 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - x - 14 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - 56*x - 10124 over Rational Field
859
860            sage: E = EllipticCurve('37a1')
861            sage: triv = EllipticCurveIsogeny(E, E(0))
862            sage: triv
863            Isogeny of degree 1 from Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
864            sage: triv.rational_maps()
865            (x, y)
866
867            sage: E = EllipticCurve('49a3')
868            sage: R.<X> = QQ[]
869            sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False)
870            Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 107*x + 552 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 5252*x - 178837 over Rational Field
871
872        """
873        if not is_EllipticCurve(E):
874            raise ValueError, "E parameter must be an EllipticCurve."
875
876        if type(kernel) != type([1,1]) and kernel in E :
877            # a single point was given, we put it in a list
878            # the first condition assures that [1,1] is treated as x+1
879            kernel = [kernel]
880
881        # if the kernel is None and the codomain isn't
882        # calculate the kernel polynomial
883        pre_isom = None
884        post_isom = None
885
886        self.__check = check
887
888        if (kernel is None) and (codomain is not None):
889
890            if (degree is None):
891                raise ValueError, "If specifying isogeny by domain and codomain, degree parameter must be set."
892
893            # save the domain/codomain: really used now (trac #7096)
894            old_domain = E
895            old_codomain = codomain
896
897            (pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree)
898        self.__init_algebraic_structs(E)
899
900        algorithm = isogeny_determine_algorithm(E, kernel, codomain, degree, model);
901
902        self.__algorithm = algorithm
903
904        if ("velu"==algorithm):
905            self.__init_from_kernel_list(kernel)
906        elif ("kohel"==algorithm):
907            self.__init_from_kernel_polynomial(kernel, degree)
908
909        self.__compute_E2()
910
911        self.__setup_post_isomorphism(codomain, model)
912
913        if (pre_isom is not None):
914            self.set_pre_isomorphism(pre_isom)
915
916        if (post_isom is not None):
917            self.__set_post_isomorphism(old_codomain, post_isom)   #(trac #7096)
918
919        # Inheritance house keeping
920
921        self.__perform_inheritance_housekeeping()
922
923        return
924
925    # S.Besnier 31/3/2014 : __call__ -> _call_ in order to use Map __call__
926    def _call_(self, P, output_base_ring=None):
927        r"""
928        Function that implements the call-ability of elliptic curve
929        isogenies.
930
931        EXAMPLES::
932
933            sage: E = EllipticCurve(GF(17), [1, 9, 5, 4, 3])
934            sage: phi = EllipticCurveIsogeny(E, [6,13,1])
935            sage: phi(E((1,0)))
936            (15 : 13 : 1)
937
938            sage: E = EllipticCurve(GF(23), [0,0,0,1,0])
939            sage: phi = EllipticCurveIsogeny(E, E((0,0)))
940            sage: phi(E((1,5)))
941            (2 : 0 : 1)
942            sage: phi(E(15,20), output_base_ring=GF(23^2,'alpha'))
943            (12 : 1 : 1)
944
945            sage: E = EllipticCurve(QQ, [0,0,0,3,0])
946            sage: P = E((1,2))
947            sage: phi = EllipticCurveIsogeny(E, [0,1])
948            sage: phi(P)
949            (4 : -4 : 1)
950            sage: phi(-P)
951            (4 : 4 : 1)
952
953            sage: E = EllipticCurve(GF(17), [0,-1,0,-3,-1])
954            sage: Q = E((16,0))
955            sage: tau = E.isogeny([Q],E)
956            sage: tau(Q)
957            (0 : 1 : 0)
958
959        TESTS (trac 10888)::
960
961            sage: K.<th> = NumberField(x^2+3)
962            sage: E = EllipticCurve(K,[7,0])
963            sage: phi = E.isogeny(E(0,0))
964            sage: P = E(-3,4*th)
965            sage: phi(P)
966            (-16/3 : 8/9*th : 1)
967            sage: Q = phi(P)
968            sage: phihat = phi.dual()
969            sage: phihat(Q)
970            (-1/48 : 127/576*th : 1)
971
972        """
973        E1 = self.__E1
974        E_P = P.curve()
975        change_output_ring = False
976
977        # check that the parent curve of the input point is this curve
978        # or that the point is on the same curve but whose base ring
979        # is an extension of this ring
980        if (E1 != E_P):
981            if (E1.a_invariants() != E_P.a_invariants()) :
982                raise ValueError, "P must be on a curve with same Weierstrass model as the domain curve of this isogeny."
983            change_output_ring = True
984
985
986        if(P.is_zero()):
987            return self.__E2(0)
988
989        (xP, yP) = P.xy()
990
991        if not self.__E1.is_on_curve(xP,yP):
992            raise InputError, "Input point must be on the domain curve of this isogeny."
993
994        # if there is a pre isomorphism, apply it
995        if (self.__pre_isomorphism is not None):
996            temp_xP = self.__prei_x_coord_ratl_map(xP, yP)
997            temp_yP = self.__prei_y_coord_ratl_map(xP, yP)
998            (xP, yP) = (temp_xP, temp_yP)
999
1000        if ("velu" == self.__algorithm):
1001            outP = self.__compute_via_velu_numeric(xP, yP)
1002        elif ("kohel" == self.__algorithm):
1003            outP = self.__compute_via_kohel_numeric(xP,yP)
1004
1005        # the intermediate functions return the point at infinity
1006        # if the input point is in the kernel
1007        if (outP == self.__intermediate_codomain(0)):
1008            return self.__E2(0)
1009
1010        # if there is a post isomorphism, apply it
1011        if (self.__post_isomorphism is not None):
1012            tempX = self.__posti_x_coord_ratl_map(outP[0], outP[1])
1013            tempY = self.__posti_y_coord_ratl_map(outP[0], outP[1])
1014            outP = [tempX, tempY]
1015
1016        if change_output_ring:
1017            if (output_base_ring is None):
1018                output_base_ring = E_P.base_ring()
1019            outE2 = self.__E2.change_ring(output_base_ring)
1020        else:
1021            output_base_ring = self.__E2.base_ring()
1022            outE2 = self.__E2
1023            outP = self.__E2.point(outP,check=False)
1024
1025        R = output_base_ring
1026
1027        return outE2.point([R(outP[0]), R(outP[1]), R(1)], check=False)
1028
1029
1030    def __getitem__(self, i):
1031        self.__initialize_rational_maps()
1032        if (i < 0) or (i > 2):
1033            raise IndexError
1034
1035        if i == 0:
1036            return self.__X_coord_rational_map
1037        else:
1038            return self.__Y_coord_rational_map
1039
1040    def __iter__(self):
1041        self.__initialize_rational_maps()
1042        return iter((self.__X_coord_rational_map, self.__Y_coord_rational_map))
1043
1044    def __hash__(self):
1045        r"""
1046        Function that implements the hash ability of Isogeny objects.
1047
1048        This hashes the underlying kernel polynomial so that equal
1049        isogeny objects have the same hash value.  Also, this hashes
1050        the base field, and domain and codomain curves as well, so
1051        that isogenies with the same kernel polynomial (over different
1052        base fields / curves) hash to different values.
1053
1054        EXAMPLES::
1055
1056            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
1057            sage: phi_v = EllipticCurveIsogeny(E, E((0,0)))
1058            sage: phi_k = EllipticCurveIsogeny(E, [0,1])
1059            sage: phi_k.__hash__() == phi_v.__hash__()
1060            True
1061            sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,1])
1062            sage: phi_p = EllipticCurveIsogeny(E_F17, E_F17([0,1]))
1063            sage: phi_p.__hash__() == phi_v.__hash__()
1064            False
1065
1066            sage: E = EllipticCurve('49a3')
1067            sage: R.<X> = QQ[]
1068            sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False)
1069            Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 107*x + 552 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 5252*x - 178837 over Rational Field
1070
1071        """
1072
1073        if (self.__this_hash is not None):
1074            return self.__this_hash
1075
1076        ker_poly_list = self.__kernel_polynomial_list
1077
1078        if (ker_poly_list is None):
1079            ker_poly_list = self.__init_kernel_polynomial()
1080
1081        this_hash = 0
1082
1083        for a in ker_poly_list:
1084            this_hash = this_hash.__xor__(hash(a))
1085
1086        this_hash = this_hash.__xor__(hash(self.__E1))
1087        this_hash = this_hash.__xor__(hash(self.__E2))
1088        this_hash = this_hash.__xor__(hash(self.__base_field))
1089
1090        self.__this_hash = this_hash
1091
1092        return self.__this_hash
1093
1094
1095    def __cmp__(self, other):
1096        r"""
1097        Function that implements comparisons between isogeny objects.
1098
1099        This function works by comparing the underlying kernel
1100        objects.
1101
1102        EXAMPLES::
1103
1104            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
1105            sage: phi_v = EllipticCurveIsogeny(E, E((0,0)))
1106            sage: phi_k = EllipticCurveIsogeny(E, [0,1])
1107            sage: phi_k == phi_v
1108            True
1109            sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,0])
1110            sage: phi_p = EllipticCurveIsogeny(E_F17, [0,1])
1111            sage: phi_p == phi_v
1112            False
1113            sage: E = EllipticCurve('11a1')
1114            sage: phi = E.isogeny(E(5,5))
1115            sage: psi = E.isogeny(phi.kernel_polynomial())
1116            sage: phi == psi
1117            True
1118            sage: phi.dual() == psi.dual()
1119            True
1120
1121
1122        """
1123        if (not isinstance(other, EllipticCurveIsogeny)):
1124            return -1
1125
1126        if (self.__kernel_polynomial is None):
1127            self.__init_kernel_polynomial()
1128
1129        return cmp(self.__kernel_polynomial, other.kernel_polynomial())
1130
1131
1132    def __neg__(self):
1133        r"""
1134        Function to implement unary negation (-) operator on
1135        isogenies. Returns a copy of this isogeny that has been
1136        negated.
1137
1138        EXAMPLES:
1139
1140        The following examples inherently exercise this function::
1141
1142            sage: E = EllipticCurve(j=GF(17)(0))
1143            sage: phi = EllipticCurveIsogeny(E,  E((-1,0)) )
1144            sage: negphi = -phi
1145            sage: phi(E((0,1))) + negphi(E((0,1)))
1146            (0 : 1 : 0)
1147
1148            sage: E = EllipticCurve(j=GF(19)(1728))
1149            sage: R.<x> = GF(19)[]
1150            sage: phi = EllipticCurveIsogeny(E, x)
1151            sage: negphi = -phi
1152            sage: phi(E((3,7))) + negphi(E((3,12))) == phi(2*E((3,7)))
1153            True
1154            sage: negphi(E((18,6)))
1155            (17 : 0 : 1)
1156
1157            sage: R.<x> = QQ[]
1158            sage: E = EllipticCurve('17a1')
1159            sage: R.<x> = QQ[]
1160            sage: f = x - 11/4
1161            sage: phi = EllipticCurveIsogeny(E, f)
1162            sage: negphi = -phi
1163            sage: phi.rational_maps()[0] == negphi.rational_maps()[0]
1164            True
1165            sage: P = E((7,13))
1166            sage: phi(P) + negphi(P)
1167            (0 : 1 : 0)
1168
1169        """
1170        # save off the kernel lists
1171        kernel_list = self.__kernel_list
1172        self.__kernel_list = None
1173
1174        output = deepcopy(self)
1175
1176        # reset the kernel lists
1177        output.__kernel_list = copy(kernel_list)
1178        self.__kernel_list = kernel_list
1179
1180        output.switch_sign()
1181        return output
1182
1183
1184
1185    #
1186    # Sage Special Functions
1187    #
1188
1189    def _repr_(self):
1190        r"""
1191        Special sage specific function that implement the
1192        functionality to display the isogeny self as a string.
1193
1194        EXAMPLES::
1195
1196            sage: E = EllipticCurve(GF(31), [1,0,1,1,0])
1197            sage: phi = EllipticCurveIsogeny(E, E((0,0)) )
1198            sage: phi._repr_()
1199            'Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 31 to Elliptic Curve defined by y^2 + x*y + y = x^3 + 14*x + 9 over Finite Field of size 31'
1200
1201            sage: E = EllipticCurve(QQ, [1,0,0,1,9])
1202            sage: phi = EllipticCurveIsogeny(E, [2,1])
1203            sage: phi._repr_()
1204            'Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y = x^3 + x + 9 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - 59*x + 165 over Rational Field'
1205
1206        """
1207        s= 'Isogeny of degree ' + self.__degree.__repr__() + ':\n  From: ' + \
1208                 self.domain().__repr__() + '\n  To: ' + self.codomain().__repr__()
1209        d = self._repr_defn()
1210        if d != '':
1211            s += "\n  Defn: %s"%('\n        '.join(self._repr_defn().split('\n')))
1212        return s
1213
1214    def _latex_(self):
1215        r"""
1216        Special sage specific function that implements functionality
1217        to display an isogeny object as a latex string.
1218
1219        This function returns a latex string representing the isogeny
1220        self as the x and y coordinate rational functions.
1221
1222        EXAMPLES::
1223
1224            sage: E = EllipticCurve(QQ, [0,0,0,1,-1])
1225            sage: phi = EllipticCurveIsogeny(E, E(0))
1226            sage: phi._latex_()
1227            '\\left( x , y \\right)'
1228
1229            sage: E = EllipticCurve(GF(17), [0,0,0,1,-1])
1230            sage: R.<X> = GF(17)[]
1231            sage: phi = EllipticCurveIsogeny(E, X+11)
1232            sage: phi._latex_()
1233            '\\left( \\frac{x^{2} + 11 x + 7}{x + 11} , \\frac{x^{2} y + 5 x y + 12 y}{x^{2} + 5 x + 2} \\right)'
1234
1235
1236        """
1237        ratl_maps = self.rational_maps()
1238        return '\\left( %s , %s \\right)' % (ratl_maps[0]._latex_(), ratl_maps[1]._latex_())
1239
1240
1241    ###########################
1242    # Private Common Functions
1243    ###########################
1244
1245    # delete the hash value
1246    def __clear_cached_values(self):
1247        r"""
1248        A private function to clear the hash if the codomain has been
1249        modified by a pre or post isomorphism.
1250
1251        EXAMPLES::
1252
1253            sage: F = GF(7);
1254            sage: E = EllipticCurve(j=F(0))
1255            sage: phi = EllipticCurveIsogeny(E, [E((0,-1)), E((0,1))])
1256            sage: old_hash = hash(phi)
1257            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
1258            sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,2,-3,4)))
1259            sage: hash(phi) == old_hash
1260            False
1261
1262            sage: R.<x> = QQ[]
1263            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
1264            sage: phi = EllipticCurveIsogeny(E, x)
1265            sage: old_ratl_maps = phi.rational_maps()
1266            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
1267            sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,0,0,0)))
1268            sage: old_ratl_maps == phi.rational_maps()
1269            False
1270            sage: old_ratl_maps[1] == -phi.rational_maps()[1]
1271            True
1272
1273            sage: F = GF(127); R.<x> = F[]
1274            sage: E = EllipticCurve(j=F(1728))
1275            sage: f = x^5 + 43*x^4 + 97*x^3 + 81*x^2 + 42*x + 82
1276            sage: phi = EllipticCurveIsogeny(E, f)
1277            sage: old_hash = hash(phi)
1278            sage: old_ratl_maps = phi.rational_maps()
1279            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
1280            sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-13,13,-13,13)))
1281            sage: old_hash == hash(phi)
1282            False
1283            sage: old_ratl_maps == phi.rational_maps()
1284            False
1285            sage: phi._EllipticCurveIsogeny__clear_cached_values()
1286
1287        """
1288        self.__this_hash = None
1289        self.__rational_maps_initialized = False
1290        self.__X_coord_rational_map = None
1291        self.__Y_coord_rational_map = None
1292        self.__dual
1293
1294
1295    # performs the inheritance house keeping
1296    def __perform_inheritance_housekeeping(self):
1297        r"""
1298        Internal helper function, sets values on the super classes of
1299        this class.
1300
1301        EXAMPLES:
1302
1303        The following examples will implicitly exercise this
1304        function::
1305
1306            sage: E = EllipticCurve(GF(43), [2,3,5,7,11])
1307            sage: R.<x> = GF(43)[]; f = x + 42
1308            sage: phi = EllipticCurveIsogeny(E, f)
1309            sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping()
1310            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
1311            sage: E2 = phi.codomain()
1312            sage: post_isom = WeierstrassIsomorphism(E2, (41, 37, 31, 29))
1313            sage: phi.set_post_isomorphism(post_isom)
1314            sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain()
1315            sage: pre_isom = E1pr.isomorphism_to(E)
1316            sage: phi.set_pre_isomorphism(pre_isom)
1317
1318        """
1319
1320        # one of the superclasses uses these fields
1321        self._domain = self.__E1
1322        self._codomain = self.__E2
1323
1324        # sets up the parent
1325        parent = homset.Hom(self.__E1(0).parent(), self.__E2(0).parent())
1326        Morphism.__init__(self, parent)
1327
1328        return
1329
1330
1331    # initializes the base field
1332    def __init_algebraic_structs(self, E):
1333        r"""
1334        An internal function for EllipticCurveIsogeny objects that
1335        sets up the member variables necessary for algebra.
1336
1337        EXAMPLES:
1338
1339        The following tests inherently exercise this function::
1340
1341            sage: E = EllipticCurve(j=GF(17)(0))
1342            sage: phi = EllipticCurveIsogeny(E,  E((-1,0)))
1343            sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)
1344
1345            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
1346            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
1347            sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)
1348
1349            sage: F = GF(19); R.<x> = F[]
1350            sage: E = EllipticCurve(j=GF(19)(0))
1351            sage: phi = EllipticCurveIsogeny(E, x)
1352            sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E)
1353
1354        """
1355        self.__E1 = E
1356        self.__base_field = E.base_ring()
1357
1358        poly_ring = self.__poly_ring = PolynomialRing(self.__base_field, ['x','y'])
1359
1360        self.__x_var = poly_ring('x')
1361        self.__y_var = poly_ring('y')
1362
1363        self.__intermediate_domain = E
1364
1365        return
1366
1367
1368    def __compute_E2(self):
1369        r"""
1370        Private function that computes and sets the isogeny codomain.
1371
1372        EXAMPLES:
1373
1374        These examples inherently exercise this function::
1375
1376            sage: E = EllipticCurve(j=GF(7)(1728))
1377            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
1378            sage: phi.codomain()
1379            Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7
1380            sage: phi._EllipticCurveIsogeny__compute_E2()
1381
1382            sage: R.<x> = GF(7)[]
1383            sage: phi = EllipticCurveIsogeny(E, x)
1384            sage: phi.codomain()
1385            Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7
1386            sage: phi._EllipticCurveIsogeny__compute_E2()
1387
1388        """
1389
1390        if ("velu" == self.__algorithm):
1391            E2 = self.__compute_E2_via_velu()
1392        elif ("kohel" == self.__algorithm):
1393            E2 = self.__compute_E2_via_kohel()
1394
1395        self.__E2 = E2
1396        self.__intermediate_codomain = E2
1397
1398        return
1399
1400
1401    # initializes the rational maps fields
1402    def __initialize_rational_maps(self, precomputed_maps=None):
1403        r"""
1404        Private function that computes and initializes the rational
1405        maps.
1406
1407        INPUT:
1408
1409        - 
1410
1411        EXAMPLES:
1412
1413        The following examples inherently exercise this function::
1414
1415            sage: E = EllipticCurve(j=GF(7)(1728))
1416            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
1417            sage: phi._EllipticCurveIsogeny__initialize_rational_maps()
1418            sage: phi.rational_maps()
1419            ((x^2 + 1)/x, (x^2*y - y)/x^2)
1420
1421            sage: R.<x> = GF(7)[]
1422            sage: phi = EllipticCurveIsogeny(E, x)
1423            sage: phi = EllipticCurveIsogeny(E, x)
1424            sage: phi.rational_maps()
1425            ((x^2 + 1)/x, (x^2*y - y)/x^2)
1426            sage: phi._EllipticCurveIsogeny__initialize_rational_maps()
1427
1428            sage: E = EllipticCurve([1,2,3,4,5])
1429            sage: Eshort = E.short_weierstrass_model()
1430            sage: phi = E.isogeny(E(0), Eshort)
1431            sage: phiX, phiY = phi.rational_maps()
1432            sage: phiX(1,2), phiY(1,2)
1433            (63, 864)
1434        """
1435        if self.__rational_maps_initialized:
1436            return
1437
1438        if precomputed_maps is None:
1439            if ("velu"==self.__algorithm):
1440                (X_map, Y_map) = self.__initialize_rational_maps_via_velu()
1441            if ("kohel"==self.__algorithm):
1442                (X_map, Y_map) = self.__initialize_rational_maps_via_kohel()
1443        else:
1444            X_map, Y_map = precomputed_maps
1445
1446        if self.__prei_x_coord_ratl_map is not None:
1447            prei_X_map = self.__prei_x_coord_ratl_map
1448            prei_Y_map = self.__prei_y_coord_ratl_map
1449            X_map, Y_map = X_map.subs(x=prei_X_map, y=prei_Y_map), \
1450                           Y_map.subs(x=prei_X_map, y=prei_Y_map)
1451
1452        if self.__posti_x_coord_ratl_map is not None:
1453            X_map, Y_map = \
1454            self.__posti_x_coord_ratl_map.subs(x=X_map, y=Y_map), \
1455            self.__posti_y_coord_ratl_map.subs(x=X_map, y=Y_map)
1456
1457        self.__X_coord_rational_map = X_map
1458        self.__Y_coord_rational_map = Y_map
1459        self.__rational_maps_initialized = True
1460
1461
1462    def __init_kernel_polynomial(self):
1463        r"""
1464        Private function that initializes the kernel polynomial (if
1465        the algorithm does not take it as a parameter.)
1466
1467        EXAMPLES:
1468
1469        The following examples inherently exercise this function::
1470
1471            sage: E = EllipticCurve(j=GF(7)(1728))
1472            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
1473            sage: phi.kernel_polynomial()
1474            x
1475            sage: phi._EllipticCurveIsogeny__init_kernel_polynomial()
1476            [0, 1]
1477
1478        """
1479
1480        if (self.__kernel_polynomial_list is not None):
1481            return self.__kernel_polynomial_list
1482
1483        if ("velu" == self.__algorithm):
1484            ker_poly_list = self.__init_kernel_polynomial_velu()
1485        else:
1486            raise InputError, "The kernel polynomial should already be defined!"
1487
1488        return ker_poly_list
1489
1490
1491    def __set_pre_isomorphism(self, domain, isomorphism):
1492        r"""
1493        Private function to set the pre isomorphism and domain (and
1494        keep track of the domain of the isogeny.)
1495
1496        EXAMPLES::
1497
1498            sage: E = EllipticCurve(GF(43), [2,3,5,7,11])
1499            sage: R.<x> = GF(43)[]; f = x + 42
1500            sage: phi = EllipticCurveIsogeny(E, f)
1501            sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping()
1502            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
1503            sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain()
1504            sage: pre_isom = E1pr.isomorphism_to(E)
1505            sage: phi.set_pre_isomorphism(pre_isom)
1506            sage: phi._EllipticCurveIsogeny__set_pre_isomorphism(E, WeierstrassIsomorphism(E, (-1, 3, -3, 4)))
1507            sage: E == phi.domain()
1508            True
1509
1510        """
1511
1512        self.__E1 = domain
1513
1514        # set the isomorphism
1515        self.__pre_isomorphism = isomorphism
1516
1517        # calculate the isomorphism as a rational map.
1518
1519        (u, r, s, t) = isomorphism.tuple()
1520
1521        x = self.__x_var;
1522        y = self.__y_var;
1523
1524        self.__prei_x_coord_ratl_map = (x - r)/u**2
1525        self.__prei_y_coord_ratl_map = (y - s*(x-r) - t)/u**3
1526
1527        if (self.__kernel_polynomial is not None):
1528            ker_poly = self.__kernel_polynomial
1529            ker_poly = ker_poly.subs(x=self.__prei_x_coord_ratl_map)
1531            ker_poly = (1/kp_lc)*ker_poly
1532            self.__kernel_polynomial = ker_poly
1533
1534        self.__perform_inheritance_housekeeping()
1535
1536        return;
1537
1538
1539    def __set_post_isomorphism(self, codomain, isomorphism):
1540        r"""
1541        Private function to set the post isomorphism and codomain (and
1542        keep track of the codomain of the isogeny.)
1543
1544        EXAMPLES:
1545
1546        The following examples inherently exercise this function::
1547
1548            sage: E = EllipticCurve(j=GF(7)(1728))
1549            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
1550            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
1551            sage: E2 = phi.codomain()
1552            sage: isom = WeierstrassIsomorphism(E2, (-1,2,-3,4))
1553            sage: phi.set_post_isomorphism(isom)
1554            sage: phi._EllipticCurveIsogeny__set_post_isomorphism(E2, WeierstrassIsomorphism(phi.codomain(), (1,-2,3,-4)))
1555            sage: E2 == phi.codomain()
1556            True
1557
1558        """
1559
1560        # set the codomains
1561        self.__E2 = codomain
1562
1563        # set the isomorphism
1564        self.__post_isomorphism = isomorphism
1565
1566        # calculate the isomorphism as a rational map.
1567
1568        (u, r, s, t) = isomorphism.tuple()
1569
1570        x = self.__x_var;
1571        y = self.__y_var;
1572
1573        self.__posti_x_coord_ratl_map = (x - r)/u**2
1574        self.__posti_y_coord_ratl_map = (y - s*(x-r) - t)/u**3
1575
1576        self.__perform_inheritance_housekeeping()
1577
1578        return;
1579
1580
1581    def __setup_post_isomorphism(self, codomain, model):
1582        r"""
1583        Private function to set up the post isomorphism given the
1584        codomain.
1585
1586        EXAMPLES:
1587
1588        The following examples inherently exercise this function::
1589
1590            sage: E = EllipticCurve(j=GF(7)(1728))
1591            sage: E2 = EllipticCurve(GF(7), [0,0,0,5,0])
1592            sage: phi = EllipticCurveIsogeny(E,  E((0,0)), E2); phi
1593            Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 7
1594            sage: E3 = EllipticCurve(GF(7), [0,0,0,6,0])
1595            sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(E3, None)
1596            sage: phi
1597            Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7
1598
1599            sage: R.<x> = QQ[]
1600            sage: E = EllipticCurve(j=1728)
1601            sage: f = x^3 - x
1602            sage: phi = EllipticCurveIsogeny(E, f, model='minimal'); phi
1603            Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 - x over Rational Field to Elliptic Curve defined by y^2 = x^3 - x over Rational Field
1604
1605            sage: phi = EllipticCurveIsogeny(E, f, model=None)
1606            sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(None, 'minimal')
1607            sage: phi
1608            Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 - x over Rational Field to Elliptic Curve defined by y^2 = x^3 - x over Rational Field
1609
1610        """
1611
1612        # TODO: add checks to make sure that
1613        # codomain and model parameters are consistent with the
1614        # algorithm used.
1615
1616        post_isom = None
1617        newE2 = None
1618
1619        oldE2 = self.__E2
1620
1621        if (model is not None):
1622
1623            if (codomain is not None):
1624                raise ValueError, "Cannot specify a codomain and model flag simultaneously."
1625
1626            if ('minimal' == model):
1627
1628                if (not is_RationalField(oldE2.base_field())):
1629                    raise ValueError, "specifying minimal for model flag only valid with curves over the rational numbers."
1630
1631                newE2 = oldE2.minimal_model()
1632                post_isom = oldE2.isomorphism_to(newE2)
1633
1634            else:
1635                raise ValueError, "Unknown value of model flag."
1636
1637        elif (codomain is not None):
1638            if (not is_EllipticCurve(codomain)):
1639                raise ValueError,  "Codomain parameter must be an elliptic curve."
1640
1641            if (not oldE2.is_isomorphic(codomain)):
1642                raise ValueError, "Codomain parameter must be isomorphic to computed codomain isogeny"
1643
1644            newE2 = codomain
1645            post_isom = oldE2.isomorphism_to(newE2)
1646
1647        if (post_isom is not None):
1648            self.__set_post_isomorphism(newE2, post_isom)
1649
1650        return
1651
1652
1653    ###########################
1654    # Velu's Formula Functions
1655    ###########################
1656
1657    #
1658    # Setup function for Velu's formula
1659    #
1660
1661    def __init_from_kernel_list(self, kernel_gens):
1662        r"""
1663        Private function that initializes the isogeny from a list of
1664        points which generate the kernel (For Velu's formulas.)
1665
1666        EXAMPLES:
1667
1668        The following example inherently exercises this function::
1669
1670            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1671            sage: phi = EllipticCurveIsogeny(E,  E((0,0))); phi
1672            Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7
1673            sage: phi._EllipticCurveIsogeny__init_from_kernel_list([E(0), E((0,0))])
1674
1675        """
1676        if self.__check :
1677            for P in kernel_gens:
1678                if not P.has_finite_order():
1679                    raise ValueError, "The points in the kernel must be of finite order."
1680        # work around the current implementation of torsion points. When they are done better this could be
1681        # reduced but it won't speed things up too much.
1682        kernel_list = Set([self.__E1(0)])
1683        for P in kernel_gens:
1685            for j in range(P.order()):
1686                for Q in kernel_list:
1689
1690        self.__kernel_list = kernel_list.list()
1691        self.__kernel_2tor = {}
1692        self.__kernel_non2tor = {}
1693
1694        self.__degree = len(kernel_list)
1695
1696        self.__sort_kernel_list()
1697
1698        return
1699
1700
1701    #
1702    # Precompute the values in Velu's Formula.
1703    #
1704    def __sort_kernel_list(self):
1705        r"""
1706        Private function that sorts the list of points in the kernel
1707        (For Velu's formulas). Sorts out the 2 torsion points, and
1708        puts them in a dictionary.
1709
1710        EXAMPLES:
1711
1712        The following example inherently exercises this function::
1713
1714            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1715            sage: P = E((4,2))
1716            sage: phi = EllipticCurveIsogeny(E, P); phi
1717            Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 7
1718            sage: phi._EllipticCurveIsogeny__kernel_2tor = {}
1719            sage: phi._EllipticCurveIsogeny__kernel_non2tor = {}
1720            sage: phi._EllipticCurveIsogeny__sort_kernel_list()
1721
1722        """
1723
1724        a1,a2,a3,a4,a6 = self.__E1.ainvs()
1725
1726        v = 0
1727        w = 0
1728
1729        for Q in self.__kernel_list:
1730
1731            if Q.is_zero():
1732                continue
1733
1734            (xQ,yQ) = Q.xy()
1735
1736            gxQ = 3*xQ**2 + 2*a2*xQ + a4 - a1*yQ
1737            gyQ = -2*yQ - a1*xQ - a3
1738
1739            uQ = gyQ**2
1740
1741            # sort torsion points:
1742            if (2*yQ == -a1*xQ - a3): # Q is 2-torsion
1743                vQ = gxQ
1744                self.__kernel_2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ)
1745                v = v + vQ
1746                w = w + (uQ + xQ*vQ)
1747            elif xQ not in self.__kernel_non2tor: # Q is not a 2-torsion
1748                vQ = 2*gxQ - a1*gyQ
1749                self.__kernel_non2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ)
1750                v = v + vQ
1751                w = w + (uQ + xQ*vQ)
1752
1753        self.__v = v
1754        self.__w = w
1755
1756        return
1757
1758
1759    #
1760    # Velu's formula computing the codomain curve
1761    #
1762    def __compute_E2_via_velu(self):
1763        r"""
1764        Private function that computes the codomain via Velu's
1765        formulas.
1766
1767        EXAMPLES:
1768
1769        The following example inherently exercises this function::
1770
1771            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1772            sage: P = E((4,2))
1773            sage: phi = EllipticCurveIsogeny(E, P);
1774            sage: phi.codomain()
1775            Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 7
1776            sage: phi._EllipticCurveIsogeny__compute_E2_via_velu()
1777            Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 7
1778
1779        """
1780        v = self.__v
1781        w = self.__w
1782
1783        return compute_codomain_formula(self.__E1, v,w)
1784
1785
1786    def __velu_sum_helper(self, Qvalues, a1, a3, x, y):
1787        r"""
1788        Private function for Velu's formulas, helper function to help
1789        perform the summation.
1790
1791        EXAMPLES:
1792
1793        The following example inherently exercises this function::
1794
1795            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1796            sage: P = E((4,2))
1797            sage: phi = EllipticCurveIsogeny(E, P);
1798            sage: Q = E((0,0)); phi(Q)
1799            (0 : 0 : 1)
1800            sage: phi.rational_maps()
1801            ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),
1802             (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))
1803
1804            sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
1805            sage: phi = EllipticCurveIsogeny(E,  E((0,0)) )
1806            sage: Qvals = phi._EllipticCurveIsogeny__kernel_2tor[0]
1807            sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, 5, 5)
1808            (3, 3)
1809            sage: R.<x,y> = GF(7)[]
1810            sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, x, y)
1811            (1/x, y/x^2)
1812
1813        """
1814        xQ = Qvalues[0]
1815        yQ = Qvalues[1]
1816        gxQ = Qvalues[2]
1817        gyQ = Qvalues[3]
1818        vQ = Qvalues[4]
1819        uQ = Qvalues[5]
1820
1821        t1 = x - xQ
1822        inv_t1 = t1**-1
1823        inv_t1_2 = inv_t1**2
1824        inv_t1_3 = inv_t1_2*inv_t1
1825
1826        tX = vQ*inv_t1 + uQ*(inv_t1_2)
1827
1828        tY0 = uQ*(2*y + a1*x + a3)
1829        tY1 = vQ*(a1*t1 + y - yQ)
1830        tY2 = a1*uQ - gxQ*gyQ
1831
1832        tY =  ( tY0*inv_t1_3 + (tY1 + tY2)*inv_t1_2 )
1833
1834        return (tX, tY)
1835
1836
1837    def __compute_via_velu_numeric(self, xP, yP):
1838        r"""
1839        Private function that sorts the list of points in the kernel
1840        (for Velu's formulas). Sorts out the 2 torsion points, and
1841        puts them in a diction
1842
1843        EXAMPLES:
1844
1845        The following example inherently exercises this function::
1846
1847            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1848            sage: P = E((4,2))
1849            sage: phi = EllipticCurveIsogeny(E, P);
1850            sage: Q = E((0,0)); phi(Q)
1851            (0 : 0 : 1)
1852            sage: Q = E((-1,0)); phi(Q)
1853            (0 : 0 : 1)
1854            sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(0, 0)
1855            (0, 0)
1856            sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(-1, 0)
1857            (0, 0)
1858
1859        """
1860        # first check if the point is in the kernel
1861        if xP in self.__kernel_2tor or xP in self.__kernel_non2tor:
1862            return self.__intermediate_codomain(0)
1863
1864        outP = self.__compute_via_velu(xP,yP)
1865
1866        return outP
1867
1868
1869    def __compute_via_velu(self, xP, yP):
1870        r"""
1871        Private function for Velu's formulas, to perform the
1872        summation.
1873
1874        EXAMPLES:
1875
1876        The following example inherently exercises this function::
1877
1878            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1879            sage: P = E((4,2))
1880            sage: phi = EllipticCurveIsogeny(E, P);
1881            sage: Q = E((0,0)); phi(Q)
1882            (0 : 0 : 1)
1883            sage: phi.rational_maps()
1884            ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),
1885             (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))
1886            sage: phi._EllipticCurveIsogeny__compute_via_velu(0, 0)
1887            (0, 0)
1888            sage: R.<x,y> = GF(7)[]
1889            sage: phi._EllipticCurveIsogeny__compute_via_velu(x, y)
1890            ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),
1891             (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))
1892
1893        """
1894
1895        ker_2tor = self.__kernel_2tor
1896        ker_non2tor = self.__kernel_non2tor
1897
1898        X = 0
1899        Y = 0
1900
1901        a1 = self.__E1.a1()
1902        a3 = self.__E1.a3()
1903
1904        # next iterate over the 2torsion points of the kernel
1905        for Qvalues in ker_2tor.itervalues():
1906            (tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP)
1907            X = X + tX
1908            Y = Y + tY
1909
1910        for Qvalues in ker_non2tor.itervalues():
1911            (tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP)
1912            X = X + tX
1913            Y = Y + tY
1914
1915        X = xP + X
1916        Y = yP - Y
1917
1918        return (X,Y)
1919
1920
1921    def __initialize_rational_maps_via_velu(self):
1922        r"""
1923        Private function for Velu's formulas, helper function to initialize the rational maps.
1924
1925        EXAMPLES:
1926
1927        The following example inherently exercises this function::
1928
1929            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1930            sage: P = E((4,2))
1931            sage: phi = EllipticCurveIsogeny(E, P);
1932            sage: phi.rational_maps()
1933            ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),
1934             (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))
1935            sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_velu()
1936            ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2),
1937             (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1))
1938
1939        """
1940
1941        x = self.__x_var
1942        y = self.__y_var
1943
1944        return self.__compute_via_velu(x,y)
1945
1946
1947    def __init_kernel_polynomial_velu(self):
1948        r"""
1949        Private function for Velu's formulas, helper function to
1950        initialize the rational maps.
1951
1952        EXAMPLES:
1953
1954        The following example inherently exercises this function::
1955
1956            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
1957            sage: P = E((4,2))
1958            sage: phi = EllipticCurveIsogeny(E, P);
1959            sage: phi.kernel_polynomial()
1960            x^2 + 2*x + 4
1961            sage: phi._EllipticCurveIsogeny__init_kernel_polynomial_velu()
1962            [4, 2, 1]
1963
1964        """
1965
1966        poly_ring = self.__poly_ring
1967        x = self.__x_var
1968
1969        invX = 0
1970
1971        if (self.__pre_isomorphism is not None):
1972            pre_isom = self.__pre_isomorphism
1973            u = pre_isom.u
1974            r = pre_isom.r
1975            invX = (u**2)*x + r
1976        else:
1977            invX = x
1978
1979        psi = poly_ring(1)
1980
1981        for Qvalues in self.__kernel_2tor.itervalues():
1982            xQ = invX(x=Qvalues[0])
1983            psi = psi*(x - xQ)
1984
1985        for Qvalues in self.__kernel_non2tor.itervalues():
1986            xQ = invX(x=Qvalues[0])
1987            psi = psi*(x - xQ)
1988
1989        ker_poly_list = psi.univariate_polynomial().list()
1990
1991        self.__kernel_polynomial_list = ker_poly_list
1992        self.__kernel_polynomial = psi
1993
1994        return ker_poly_list
1995
1996
1997
1998    ###################################
1999    # Kohel's Variant of Velu's Formula
2000    ###################################
2001
2002    def __init_from_kernel_polynomial(self, kernel_polynomial, degree=None):
2003        r"""
2004        Private function that initializes the isogeny from a kernel
2005        polynomial.
2006
2007        EXAMPLES:
2008
2009        These examples inherently exercise this private function::
2010
2011            sage: R.<x> = GF(7)[]
2012            sage: E = EllipticCurve(GF(7), [0,0,0,-1,0])
2013            sage: phi = EllipticCurveIsogeny(E, x);phi
2014            Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7
2015
2016            sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x)
2017
2018            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2019            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi
2020            Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7
2021
2022            sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x+6, degree=3)
2023
2024        """
2025
2026        poly_ring = self.__poly_ring
2027        x = self.__x_var
2028
2029        E = self.__E1
2030
2031        if(is_Polynomial(kernel_polynomial)):
2032            kernel_polynomial = kernel_polynomial.list()
2033
2034        n = len(kernel_polynomial)-1
2035
2036        if kernel_polynomial[-1] != 1:
2037            raise ValueError, "The kernel polynomial must be monic."
2038
2039        self.__kernel_polynomial_list = kernel_polynomial
2040
2041        psi = 0
2042        for j in xrange(len(kernel_polynomial)):
2043            psi = psi*x + kernel_polynomial[n-j]
2044
2045
2046        #
2047        # Determine if kernel polynomial is entirely a two torsion
2048        #
2049        psi_G = two_torsion_part(E, poly_ring, psi, degree);
2050
2051        # force this polynomial to be monic:
2053
2054        if (0 != psi_G.degree()): # even degree case
2055
2056            psi_quo = poly_ring(psi/psi_G)
2057
2058            if (0 != psi_quo.degree()):
2059                raise NotImplementedError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion."
2060
2061            (phi, omega, v, w, n, d) = self.__init_even_kernel_polynomial(E, psi_G)
2062
2063        else: # odd degree case
2064
2065            (phi, omega, v, w, n, d) = self.__init_odd_kernel_polynomial(E, psi)
2066
2067
2068        #
2069        # Set up the necessary instance variables
2070        #
2071
2072        self.__kernel_polynomial = psi
2073        self.__inner_kernel_polynomial = psi
2074
2075        self.__n = n
2076        self.__degree = d
2077
2078        self.__psi = psi
2079        self.__phi = phi
2080        self.__omega = omega
2081
2082        self.__v = v
2083        self.__w = w
2084
2085        return
2086
2087
2088    def __init_even_kernel_polynomial(self, E, psi_G):
2089        r"""
2090        Private function that initializes the isogeny from a kernel
2091        polynomial, for Kohel's algorithm in the even degree case.
2092
2093        EXAMPLES:
2094
2095        These examples inherently exercise this private function::
2096
2097            sage: R.<x> = GF(7)[]
2098            sage: E = EllipticCurve(GF(7), [-1,0])
2099            sage: phi = EllipticCurveIsogeny(E, x);phi
2100            Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7
2101
2102            sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part
2103            sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var)
2104            sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)
2105            (x^3 - x, x^3*y + x*y, 6, 0, 1, 2)
2106
2107            sage: F = GF(2^4, 'alpha'); R.<x> = F[]
2108            sage: E = EllipticCurve(F, [1,1,0,1,0])
2109            sage: phi = EllipticCurveIsogeny(E, x); phi
2110            Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + x over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + 1 over Finite Field in alpha of size 2^4
2111
2112            sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var)
2113            sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)
2114            (x^3 + x, x^3*y + x^2 + x*y, 1, 0, 1, 2)
2115
2116            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2117            sage: R.<x> = GF(7)[]
2118            sage: f = x^3 + 6*x^2 + 1
2119            sage: phi = EllipticCurveIsogeny(E, f); phi
2120            Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 2*x + 5 over Finite Field of size 7
2121            sage: psig = two_torsion_part(E,R,f,None)
2122            sage: psig = two_torsion_part(E,R,f,None)(phi._EllipticCurveIsogeny__x_var)
2123            sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig)
2124            (x^7 - 2*x^6 + 2*x^5 - x^4 + 3*x^3 - 2*x^2 - x + 3,
2125            x^9*y - 3*x^8*y + 2*x^7*y - 3*x^3*y + 2*x^2*y + x*y - y,
2126            1,
2127            6,
2128            3,
2129            4)
2130
2131
2132        """
2133
2134
2135        #check if the polynomial really divides the two_torsion_polynomial
2136        if  self.__check and E.division_polynomial(2, x=self.__x_var) % psi_G  != 0 :
2137            raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve."
2138
2139        n = psi_G.degree()
2140        d = n+1
2141
2142        base_field = self.__base_field
2143        char = base_field.characteristic()
2144
2145        x = self.__x_var
2146        y = self.__y_var
2147
2148        a1,a2,a3,a4,a6 = E.ainvs()
2149
2150        b2 = E.b2()
2151        b4 = E.b4()
2152
2153        if (1 == n):
2154            x0 = -psi_G.constant_coefficient()
2155
2156            # determine y0
2157            if (2 == char):
2158                y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt()
2159            else:
2160                y0 = -(a1*x0 + a3)/2
2161
2162            (v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4)
2163
2164            phi = (x*psi_G + v)*psi_G
2165            omega = (y*psi_G**2 - v*(a1*psi_G + (y - y0)))*psi_G
2166
2167        elif (3 == n):
2168            s = psi_G.univariate_polynomial().list()
2169            s1 = -s[n-1]
2170            s2 = s[n-2]
2171            s3 = -s[n-3]
2172
2173            psi_G_pr = psi_G.derivative(x)
2174            psi_G_prpr = psi_G_pr.derivative(x)
2175
2176            phi = (psi_G_pr**2) + (-2*psi_G_prpr + (4*x - s1))*psi_G
2177
2178            phi_pr = phi.derivative(x)
2179
2180            psi_2 = 2*y + a1*x + a3
2181
2182            omega = (psi_2*(phi_pr*psi_G - phi*psi_G_pr) - (a1*phi + a3*psi_G)*psi_G)/2
2183
2184            phi = phi*psi_G
2185            omega = omega*psi_G
2186
2187            (v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3)
2188
2189        else:
2190            raise ValueError, "input polynomial must be of degree 1 or 3, not %d" % n
2191
2192        return (phi, omega, v, w, n, d)
2193
2194
2195    def __init_odd_kernel_polynomial(self, E, psi):
2196        r"""
2197        Private function that initializes the isogeny from a kernel
2198        polynomial.
2199
2200        EXAMPLES:
2201
2202        These examples inherently exercise this private function::
2203
2204            sage: R.<x> = GF(7)[]
2205            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2206            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi
2207            Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7
2208
2209            sage: R.<x,y> = GF(7)[]
2210            sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, x+6)
2211            (x^3 - 2*x^2 + 3*x + 2, x^3*y - 3*x^2*y + x*y, 2, 6, 1, 3)
2212
2213            sage: F = GF(2^4, 'alpha'); R.<x> = F[]
2214            sage: alpha = F.gen()
2215            sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1])
2216            sage: f = x + alpha^2 + 1
2217            sage: phi = EllipticCurveIsogeny(E, f); phi
2218            Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + (alpha^2+1)*x + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + alpha*x + alpha^3 over Finite Field in alpha of size 2^4
2219
2220            sage: R.<x,y> = F[]
2221            sage: f = x + alpha^2 + 1
2222            sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, f)
2223            (x^3 + (alpha^2 + 1)*x + (alpha^3 + alpha^2 + alpha),
2224             x^3*y + (alpha^2 + 1)*x^2*y + (alpha^2 + alpha + 1)*x^2 + (alpha^2 + 1)*x*y + (alpha^2 + alpha)*x + (alpha)*y + (alpha),
2225             alpha^2 + alpha + 1,
2226             alpha^3 + alpha^2 + alpha,
2227             1,
2228             3)
2229
2230            sage: E = EllipticCurve(j=-262537412640768000)
2231            sage: f = (E.isogenies_prime_degree()[0]).kernel_polynomial()
2232            sage: f.degree()
2233            81
2234            sage: E.isogeny(kernel=f)  # long time (25s on sage.math, 2012)
2235            Isogeny of degree 163 from Elliptic Curve defined by y^2 + y = x^3 - 2174420*x + 1234136692 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 57772164980*x - 5344733777551611 over Rational Field
2236
2237        """
2238        n = psi.degree()
2239        d = 2*n + 1
2240
2241        # check if the polynomial really divides the torsion polynomial :
2242        if self.__check:
2243            alpha = psi.parent().quotient(psi).gen()
2244            if not E.division_polynomial(d, x=alpha).is_zero():
2245                raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve."
2246
2247        x = self.__x_var
2248
2249        b2 = E.b2()
2250        b4 = E.b4()
2251        b6 = E.b6()
2252
2253        psi_coeffs = psi.univariate_polynomial().list()
2254
2255        s1 = 0; s2 = 0; s3 = 0
2256
2257        if (1 <= n):
2258            s1 = -psi_coeffs[n-1]
2259
2260        if (2 <= n):
2261            s2 = psi_coeffs[n-2]
2262
2263        if (3 <= n):
2264            s3 = -psi_coeffs[n-3]
2265
2266        # initializing these allows us to calculate E2.
2267        (v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n);
2268
2269        # initialize the polynomial temporary variables
2270
2271        psi_pr = psi.derivative(x)
2272        psi_prpr = psi_pr.derivative(x)
2273
2274        phi = (4*x**3 + b2*x**2 + 2*b4*x + b6)*(psi_pr**2 - psi_prpr*psi) - \
2275                (6*x**2 + b2*x + b4)*psi_pr*psi + (d*x - 2*s1)*psi**2
2276
2277        phi_pr = phi.derivative(x)
2278
2279        omega = 0
2280        if (2 != self.__base_field.characteristic()):
2281            omega = self.__compute_omega_fast(E, psi, psi_pr, phi, phi_pr)
2282        else:
2283            omega = self.__compute_omega_general(E, psi, psi_pr, phi, phi_pr)
2284
2285        return (phi, omega, v, w, n, d)
2286
2287
2288    #
2289    # This is the fast omega computation that works when characteristic is not 2
2290    #
2291    def __compute_omega_fast(self, E, psi, psi_pr, phi, phi_pr):
2292        r"""
2293        Private function that initializes the omega polynomial (from
2294        Kohel's formulas) in the case that the characteristic of the
2295        underlying field is not 2.
2296
2297        EXAMPLES:
2298
2299        These examples inherently exercise this private function::
2300
2301            sage: R.<x> = GF(7)[]
2302            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2303            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi
2304            Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7
2305
2306            sage: R.<x,y> = GF(7)[]
2307            sage: psi = phi._EllipticCurveIsogeny__psi
2308            sage: psi_pr = psi.derivative(x)
2309            sage: fi = phi._EllipticCurveIsogeny__phi
2310            sage: fi_pr = fi.derivative(x)
2311            sage: phi._EllipticCurveIsogeny__compute_omega_fast(E, psi, psi_pr, fi, fi_pr)
2312            x^3*y - 3*x^2*y + x*y
2313
2314        """
2315
2316        a1 = E.a1()
2317        a3 = E.a3()
2318
2319        x = self.__x_var; # 'x'
2320        y = self.__y_var; # 'y'
2321
2322        psi_2 = 2*y + a1*x + a3
2323
2324        # note, the formula below is correct
2325        # the formula in Kohel's thesis has some typos
2326        # notably the first plus sign should be a minus
2327        # as it is here below.
2328
2329        omega = phi_pr*psi*psi_2/2 - phi*psi_pr*psi_2 - \
2330                (a1*phi + a3*psi**2)*psi/2
2331
2332        return omega
2333
2334
2335    def __compute_omega_general(self, E, psi, psi_pr, phi, phi_pr):
2336        r"""
2337        Private function that initializes the omega polynomial (from
2338        Kohel's formulas) in the case of general characteristic of the
2339        underlying field.
2340
2341        EXAMPLES:
2342
2343        These examples inherently exercise this private function::
2344
2345            sage: F = GF(2^4, 'alpha'); R.<x> = F[]
2346            sage: alpha = F.gen()
2347            sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1])
2348            sage: f = x + alpha^2 + 1
2349            sage: phi = EllipticCurveIsogeny(E, f); phi
2350            Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + (alpha^2+1)*x + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + alpha*x + alpha^3 over Finite Field in alpha of size 2^4
2351
2352            sage: R.<x,y> = F[]
2353            sage: psi = phi._EllipticCurveIsogeny__psi
2354            sage: psi_pr = psi.derivative(x)
2355            sage: fi = phi._EllipticCurveIsogeny__phi
2356            sage: fi_pr = fi.derivative(x)
2357            sage: phi._EllipticCurveIsogeny__compute_omega_general(E, psi, psi_pr, fi, fi_pr)
2358            x^3*y + (alpha^2 + 1)*x^2*y + (alpha^2 + alpha + 1)*x^2 + (alpha^2 + 1)*x*y + (alpha^2 + alpha)*x + (alpha)*y + (alpha)
2359
2360        A bug fixed in ticket #7907::
2361
2362            sage: F = GF(128,'a')
2363            sage: a = F.gen()
2364            sage: E = EllipticCurve([1,0,0,0,(a**6+a**4+a**2+a)])
2365            sage: x = polygen(F)
2366            sage: ker =  (x^6 + (a^6 + a^5 + a^4 + a^3 + a^2 + a)*x^5 + (a^6 + a^5 + a^2 + 1)*x^4 + (a^6 + a^5 + a^4 + a^3 + a^2 + 1)*x^3 + (a^6 + a^3 + a)*x^2 + (a^4 + a^3 + 1)*x + a^5 + a^4 + a)
2367            sage: E.isogeny(ker)
2368            Isogeny of degree 13 from Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^4+a^2+a) over Finite Field in a of size 2^7 to Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^5+a^4+a^3+a^2+a)*x + (a^5+a^3) over Finite Field in a of size 2^7
2369
2370
2371        """
2372
2373        a1,a2,a3,a4,a6 = E.ainvs()
2374
2375        b2 = E.b2()
2376        b4 = E.b4()
2377
2378        n = psi.degree()
2379        d = 2*n+1
2380
2381        x = self.__x_var
2382        y = self.__y_var
2383
2384        psi_2 = 2*y + a1*x + a3
2385
2386        psi_coeffs = psi.univariate_polynomial().list()
2387
2388        if (0 < n):
2389            s1 = -psi_coeffs[n-1]
2390        else:
2391            s1 = 0
2392
2393        psi_prpr = 0
2394        cur_x_pow = 1
2395
2396        #
2397        # Note: we now get the "derivatives" of psi
2398        # these are not actually the derivatives
2399        # furthermore, the formulas in Kohel's
2400        # thesis are wrong, the correct formulas
2401        # are coded below
2402        #
2403        from sage.rings.arith import binomial
2404
2405        for j  in xrange(0,n-1):
2406            psi_prpr = psi_prpr + \
2407                binomial(j+2,2)*psi_coeffs[(j+2)]*cur_x_pow
2408            cur_x_pow = x*cur_x_pow
2409
2410        psi_prprpr = 0
2411        cur_x_pow = 1
2412
2413        for j in xrange(0,n-2):
2414            psi_prprpr = psi_prprpr + \
2415                (3*binomial(j+3,3))*psi_coeffs[(j+3)]*cur_x_pow
2416            cur_x_pow = x*cur_x_pow
2417
2418
2419        omega = phi_pr*psi*y - phi*psi_pr*psi_2 + \
2420                ((a1*x + a3)*(psi_2**2)*(psi_prpr*psi_pr-psi_prprpr*psi) + \
2421                (a1*psi_2**2 - 3*(a1*x + a3)*(6*x**2 + b2*x + b4))*psi_prpr*psi + \
2422                (a1*x**3 + 3*a3*x**2 + (2*a2*a3 - a1*a4)*x + (a3*a4 - 2*a1*a6))*psi_pr**2 + \
2423                (-(3*a1*x**2 + 6*a3*x + (-a1*a4 + 2*a2*a3)) + \
2424                (a1*x + a3)*(d*x - 2*s1) )*psi_pr*psi + (a1*s1 + a3*n)*psi**2)*psi
2425
2426        return omega
2427
2428
2429    def __compute_via_kohel_numeric(self, xP, yP):
2430        r"""
2431        Private function that computes a numeric result of this
2432        isogeny (via Kohel's formulas.)
2433
2434        EXAMPLES:
2435
2436        These examples inherently exercise this private function::
2437
2438            sage: R.<x> = GF(7)[]
2439            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2440            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)
2441            sage: P = E((0,1)); phi(P)
2442            (2 : 0 : 1)
2443            sage: P = E((1,1)); phi(P)
2444            (0 : 1 : 0)
2445            sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(0, 1)
2446            (2, 0)
2447            sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(1, 1)
2448            (0 : 1 : 0)
2449
2450        """
2451
2452        # first check if this is a kernel point
2453        # to avoid a divide by 0 error later
2454        if(0 == self.__inner_kernel_polynomial(x=xP)):
2455            return self.__intermediate_codomain(0)
2456
2457        (xP_out, yP_out) = self.__compute_via_kohel(xP,yP)
2458
2459        # for some dang reason in some cases
2460        # when the base_field is a number field
2461        # xP_out and yP_out do not get evaluated to field elements
2462        # but rather constant polynomials.
2463        # So in this case, we do some explicit casting to make sure
2464        # everything comes out right
2465
2466        if is_NumberField(self.__base_field) and (1 < self.__base_field.degree()) :
2467            xP_out = self.__poly_ring(xP_out).constant_coefficient()
2468            yP_out = self.__poly_ring(yP_out).constant_coefficient()
2469
2470        return (xP_out,yP_out)
2471
2472
2473    def __compute_via_kohel(self, xP, yP):
2474        r"""
2475        Private function that applies Kohel's formulas.
2476
2477        EXAMPLES:
2478
2479        These examples inherently exercise this private function::
2480
2481            sage: R.<x> = GF(7)[]
2482            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2483            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)
2484            sage: P = E((0,1)); phi(P)
2485            (2 : 0 : 1)
2486            sage: phi.rational_maps()
2487            ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),
2488             (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))
2489            sage: phi._EllipticCurveIsogeny__compute_via_kohel(0,1)
2490            (2, 0)
2491            sage: R.<x,y> = GF(7)[]
2492            sage: phi._EllipticCurveIsogeny__compute_via_kohel(x,y)
2493            ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),
2494             (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))
2495
2496        """
2497
2498        x = self.__x_var
2499        y = self.__y_var
2500
2501        psi_out = self.__psi(xP,yP)
2502        phi_out = self.__phi(xP,yP)
2503        omega_out =self.__omega(xP, yP)
2504
2505        psi_inv_out = 1/psi_out
2506
2507        psi_inv_sq_out = psi_inv_out**2
2508
2509        X_out = phi_out*(psi_inv_sq_out)
2510        Y_out = omega_out*(psi_inv_sq_out*psi_inv_out)
2511
2512        return (X_out, Y_out)
2513
2514
2515    def __initialize_rational_maps_via_kohel(self):
2516        r"""
2517        Private function that computes and initializes the rational
2518        maps of this isogeny.
2519
2520        EXAMPLES:
2521
2522        These examples inherently exercise this private function::
2523
2524            sage: R.<x> = GF(7)[]
2525            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2526            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)
2527            sage: phi.rational_maps()
2528            ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),
2529             (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))
2530            sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_kohel()
2531            ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1),
2532             (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1))
2533
2534
2535        """
2536        x = self.__x_var
2537        y = self.__y_var
2538
2539        (X,Y) = self.__compute_via_kohel(x,y)
2540
2541        return (X,Y)
2542
2543
2544    #
2545    # Kohel's formula computing the codomain curve
2546    #
2547    def __compute_E2_via_kohel(self):
2548        r"""
2549        Private function that computes and initializes the codomain of
2550        the isogeny (via Kohel's.)
2551
2552        EXAMPLES:
2553
2554        These examples inherently exercise this private function::
2555
2556            sage: R.<x> = GF(7)[]
2557            sage: E = EllipticCurve(GF(7), [0,-1,0,0,1])
2558            sage: phi = EllipticCurveIsogeny(E, x+6, degree=3)
2559            sage: phi.codomain()
2560            Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7
2561            sage: phi._EllipticCurveIsogeny__compute_E2_via_kohel()
2562            Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7
2563
2564        """
2565
2566        v = self.__v
2567        w = self.__w
2568
2569        return compute_codomain_formula(self.__E1, v,w)
2570
2571
2572
2573    #
2574    # public isogeny methods
2575    #
2576
2577#    def domain(self):
2578        r"""
2579        Returns the domain curve of this isogeny.
2580
2581        EXAMPLES::
2582
2583            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
2584            sage: phi = EllipticCurveIsogeny(E,  E(0,0))
2585            sage: phi.domain() == E
2586            True
2587
2588            sage: E = EllipticCurve(GF(31), [1,0,0,1,2])
2589            sage: phi = EllipticCurveIsogeny(E, [17, 1])
2590            sage: phi.domain()
2591            Elliptic Curve defined by y^2 + x*y = x^3 + x + 2 over Finite Field of size 31
2592
2593        """
2594        # !!!! S. Besnier change here !!!! : replace __E1 by __E1(self.__E1.base_field()) in order
2595        # to make self.domain() an AbelianGroup
2596#        return self.__E1(self.__E1.base_field())
2597
2598
2599#    def codomain(self):
2600        r"""
2601        Returns the codomain (range) curve of this isogeny.
2602
2603        EXAMPLES::
2604
2605            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
2606            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
2607            sage: phi.codomain()
2608            Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field
2609
2610            sage: E = EllipticCurve(GF(31), [1,0,0,1,2])
2611            sage: phi = EllipticCurveIsogeny(E, [17, 1])
2612            sage: phi.codomain()
2613            Elliptic Curve defined by y^2 + x*y = x^3 + 24*x + 6 over Finite Field of size 31
2614
2615        """
2616        # !!!! S. Besnier change here !!!! : replace __E2 by __E1(self.__E2.base_field())
2617#        return self.__E2(self.__E2.base_field())
2618
2619
2620    def degree(self):
2621        r"""
2622        Returns the degree of this isogeny.
2623
2624        EXAMPLES::
2625
2626            sage: E = EllipticCurve(QQ, [0,0,0,1,0])
2627            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
2628            sage: phi.degree()
2629            2
2630            sage: phi = EllipticCurveIsogeny(E, [0,1,0,1])
2631            sage: phi.degree()
2632            4
2633
2634            sage: E = EllipticCurve(GF(31), [1,0,0,1,2])
2635            sage: phi = EllipticCurveIsogeny(E, [17, 1])
2636            sage: phi.degree()
2637            3
2638
2639        """
2640        return self.__degree
2641
2642
2643    def rational_maps(self):
2644        r"""
2645        This function returns this isogeny as a pair of rational maps.
2646
2647        EXAMPLES::
2648
2649            sage: E = EllipticCurve(QQ, [0,2,0,1,-1])
2650            sage: phi = EllipticCurveIsogeny(E, [1])
2651            sage: phi.rational_maps()
2652            (x, y)
2653
2654            sage: E = EllipticCurve(GF(17), [0,0,0,3,0])
2655            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
2656            sage: phi.rational_maps()
2657            ((x^2 + 3)/x, (x^2*y - 3*y)/x^2)
2658
2659
2660        """
2661        if (not self.__rational_maps_initialized):
2662            self.__initialize_rational_maps()
2663        return (self.__X_coord_rational_map, self.__Y_coord_rational_map)
2664
2665
2666    def is_separable(self):
2667        r"""
2668        This function returns a bool indicating whether or not this
2669        isogeny is separable.
2670
2671        This function always returns True as currently this class
2672        only implements separable isogenies.
2673
2674        EXAMPLES::
2675
2676            sage: E = EllipticCurve(GF(17), [0,0,0,3,0])
2677            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
2678            sage: phi.is_separable()
2679            True
2680
2681            sage: E = EllipticCurve('11a1')
2682            sage: phi = EllipticCurveIsogeny(E, E.torsion_points())
2683            sage: phi.is_separable()
2684            True
2685
2686
2687        """
2688        return self.__separable
2689
2690
2691    def kernel_polynomial(self):
2692        r"""
2693        Returns the kernel polynomial of this isogeny.
2694
2695        EXAMPLES::
2696
2697            sage: E = EllipticCurve(QQ, [0,0,0,2,0])
2698            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
2699            sage: phi.kernel_polynomial()
2700            x
2701
2702            sage: E = EllipticCurve('11a1')
2703            sage: phi = EllipticCurveIsogeny(E, E.torsion_points())
2704            sage: phi.kernel_polynomial()
2705            x^2 - 21*x + 80
2706
2707            sage: E = EllipticCurve(GF(17), [1,-1,1,-1,1])
2708            sage: phi = EllipticCurveIsogeny(E, [1])
2709            sage: phi.kernel_polynomial()
2710            1
2711
2712            sage: E = EllipticCurve(GF(31), [0,0,0,3,0])
2713            sage: phi = EllipticCurveIsogeny(E, [0,3,0,1])
2714            sage: phi.kernel_polynomial()
2715            x^3 + 3*x
2716
2717
2718        """
2719        if (self.__kernel_polynomial is None):
2720            self.__init_kernel_polynomial()
2721
2722        return self.__kernel_polynomial.univariate_polynomial()
2723
2724
2725    def set_pre_isomorphism(self, preWI):
2726        r"""
2727        Modifies this isogeny object to pre compose with the given
2728        Weierstrass isomorphism.
2729
2730        EXAMPLES::
2731
2732            sage: E = EllipticCurve(GF(31), [1,1,0,1,-1])
2733            sage: R.<x> = GF(31)[]
2734            sage: f = x^3 + 9*x^2 + x + 30
2735            sage: phi = EllipticCurveIsogeny(E, f)
2736            sage: Epr = E.short_weierstrass_model()
2737            sage: isom = Epr.isomorphism_to(E)
2738            sage: phi.set_pre_isomorphism(isom)
2739            sage: phi.rational_maps()
2740            ((-6*x^4 - 3*x^3 + 12*x^2 + 10*x - 1)/(x^3 + x - 12),
2741             (3*x^7 + x^6*y - 14*x^6 - 3*x^5 + 5*x^4*y + 7*x^4 + 8*x^3*y - 8*x^3 - 5*x^2*y + 5*x^2 - 14*x*y + 14*x - 6*y - 6)/(x^6 + 2*x^4 + 7*x^3 + x^2 + 7*x - 11))
2742            sage: phi(Epr((0,22)))
2743            (13 : 21 : 1)
2744            sage: phi(Epr((3,7)))
2745            (14 : 17 : 1)
2746
2747            sage: E = EllipticCurve(GF(29), [0,0,0,1,0])
2748            sage: R.<x> = GF(29)[]
2749            sage: f = x^2 + 5
2750            sage: phi = EllipticCurveIsogeny(E, f)
2751            sage: phi
2752            Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 20*x over Finite Field of size 29
2753            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
2754            sage: inv_isom = WeierstrassIsomorphism(E, (1,-2,5,10))
2755            sage: Epr = inv_isom.codomain().codomain()
2756            sage: isom = Epr.isomorphism_to(E)
2757            sage: phi.set_pre_isomorphism(isom); phi
2758            Isogeny of degree 5 from Elliptic Curve defined by y^2 + 10*x*y + 20*y = x^3 + 27*x^2 + 6 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 20*x over Finite Field of size 29
2759            sage: phi(Epr((12,1)))
2760            (26 : 0 : 1)
2761            sage: phi(Epr((2,9)))
2762            (0 : 0 : 1)
2763            sage: phi(Epr((21,12)))
2764            (3 : 0 : 1)
2765            sage: phi.rational_maps()[0]
2766            (x^5 - 10*x^4 - 6*x^3 - 7*x^2 - x + 3)/(x^4 - 8*x^3 + 5*x^2 - 14*x - 6)
2767
2768            sage: E = EllipticCurve('11a1')
2769            sage: R.<x> = QQ[]
2770            sage: f = x^2 - 21*x + 80
2771            sage: phi = EllipticCurveIsogeny(E, f); phi
2772            Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field
2773            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
2774            sage: Epr = E.short_weierstrass_model()
2775            sage: isom = Epr.isomorphism_to(E)
2776            sage: phi.set_pre_isomorphism(isom)
2777            sage: phi
2778            Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 - 13392*x - 1080432 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field
2779            sage: phi(Epr((168,1188)))
2780            (0 : 1 : 0)
2781
2782        """
2783
2784        WIdom = preWI.domain().codomain()
2785        WIcod = preWI.codomain().codomain()
2786
2787        if (type(preWI) != WeierstrassIsomorphism):
2788            raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism."
2789
2790        if (self.__E1 != WIcod):
2791            raise ValueError, "Invalid parameter: isomorphism must have codomain curve equal to this isogenies' domain."
2792
2793        if (self.__pre_isomorphism is None):
2794            isom = preWI
2795            domain = WIdom
2796        else:
2797            isom = self.__pre_isomorphism*preWI
2798            domain = WIdom
2799
2800        self.__clear_cached_values()
2801
2802        self.__set_pre_isomorphism(domain, isom)
2803
2804        return
2805
2806
2807    def set_post_isomorphism(self, postWI):
2808        r"""
2809        Modifies this isogeny object to post compose with the given
2810        Weierstrass isomorphism.
2811
2812        EXAMPLES::
2813
2814            sage: E = EllipticCurve(j=GF(31)(0))
2815            sage: R.<x> = GF(31)[]
2816            sage: phi = EllipticCurveIsogeny(E, x+18)
2817            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
2818            sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (6,8,10,12)))
2819            sage: phi
2820            Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 31 to Elliptic Curve defined by y^2 + 24*x*y + 7*y = x^3 + 22*x^2 + 16*x + 20 over Finite Field of size 31
2821
2822            sage: E = EllipticCurve(j=GF(47)(0))
2823            sage: f = E.torsion_polynomial(3)/3
2824            sage: phi = EllipticCurveIsogeny(E, f)
2825            sage: E2 = phi.codomain()
2826            sage: post_isom = E2.isomorphism_to(E)
2827            sage: phi.set_post_isomorphism(post_isom)
2828            sage: phi.rational_maps() == E.multiplication_by_m(3)
2829            False
2830            sage: phi.switch_sign()
2831            sage: phi.rational_maps() == E.multiplication_by_m(3)
2832            True
2833
2834        Example over a number field::
2835
2836            sage: R.<x> = QQ[]
2837            sage: K.<a> = NumberField(x^2 + 2)
2838            sage: E = EllipticCurve(j=K(1728))
2839            sage: ker_list = E.torsion_points()
2840            sage: phi = EllipticCurveIsogeny(E, ker_list)
2841            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
2842            sage: post_isom = WeierstrassIsomorphism(phi.codomain(), (a,2,3,5))
2843            sage: phi
2844            Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^2 + 2 to Elliptic Curve defined by y^2 = x^3 + (-44)*x + 112 over Number Field in a with defining polynomial x^2 + 2
2845
2846        """
2847
2848        WIdom = postWI.domain().codomain()
2849        WIcod = postWI.codomain().codomain()
2850
2851        if (type(postWI) != WeierstrassIsomorphism):
2852            raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism."
2853
2854        if (self.__E2 != WIdom):
2855            raise ValueError, "Invalid parameter: isomorphism must have domain curve equal to this isogenies' codomain."
2856
2857        if (self.__post_isomorphism is None):
2858            isom = postWI
2859            codomain = WIcod
2860        else:
2861            isom = postWI*self.__post_isomorphism
2862            codomain = WIcod
2863
2864        self.__clear_cached_values()
2865
2866        self.__set_post_isomorphism(codomain, isom)
2867
2868        return
2869
2870
2871    def get_pre_isomorphism(self):
2872        r"""
2873        Returns the pre-isomorphism of this isogeny.  If there has
2874        been no pre-isomorphism set, this returns None.
2875
2876        EXAMPLES::
2877
2878            sage: E = EllipticCurve(GF(31), [1,1,0,1,-1])
2879            sage: R.<x> = GF(31)[]
2880            sage: f = x^3 + 9*x^2 + x + 30
2881            sage: phi = EllipticCurveIsogeny(E, f)
2882            sage: phi.get_post_isomorphism()
2883            sage: Epr = E.short_weierstrass_model()
2884            sage: isom = Epr.isomorphism_to(E)
2885            sage: phi.set_pre_isomorphism(isom)
2886            sage: isom == phi.get_pre_isomorphism()
2887            True
2888
2889            sage: E = EllipticCurve(GF(83), [1,0,1,1,0])
2890            sage: R.<x> = GF(83)[]; f = x+24
2891            sage: phi = EllipticCurveIsogeny(E, f)
2892            sage: E2 = phi.codomain()
2893            sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2)
2894            sage: phi2.get_pre_isomorphism()
2895            Generic morphism:
2896              From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 83
2897              To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83
2898              Via:  (u,r,s,t) = (1, 76, 41, 3)
2899
2900
2901
2902        """
2903        return self.__pre_isomorphism
2904
2905
2906    def get_post_isomorphism(self):
2907        r"""
2908        Returns the post-isomorphism of this isogeny.  If there has
2909        been no post-isomorphism set, this returns None.
2910
2911        EXAMPLES::
2912
2913            sage: E = EllipticCurve(j=GF(31)(0))
2914            sage: R.<x> = GF(31)[]
2915            sage: phi = EllipticCurveIsogeny(E, x+18)
2916            sage: phi.get_post_isomorphism()
2917            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
2918            sage: isom = WeierstrassIsomorphism(phi.codomain(), (6,8,10,12))
2919            sage: phi.set_post_isomorphism(isom)
2920            sage: isom == phi.get_post_isomorphism()
2921            True
2922
2923            sage: E = EllipticCurve(GF(83), [1,0,1,1,0])
2924            sage: R.<x> = GF(83)[]; f = x+24
2925            sage: phi = EllipticCurveIsogeny(E, f)
2926            sage: E2 = phi.codomain()
2927            sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2)
2928            sage: phi2.get_post_isomorphism()
2929            Generic morphism:
2930            From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83
2931            To:   Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 83
2932            Via:  (u,r,s,t) = (1, 7, 42, 80)
2933
2934        """
2935        return self.__post_isomorphism
2936
2937
2938    def switch_sign(self):
2939        r"""
2940        This function composes the isogeny with [-1] (flipping the
2941        coefficient between +/-1 on the y coordinate rational map).
2942
2943        EXAMPLES::
2944
2945            sage: E = EllipticCurve(GF(23), [0,0,0,1,0])
2946            sage: f = E.torsion_polynomial(3)/3
2947            sage: phi = EllipticCurveIsogeny(E, f, E)
2948            sage: phi.rational_maps() == E.multiplication_by_m(3)
2949            False
2950            sage: phi.switch_sign()
2951            sage: phi.rational_maps() == E.multiplication_by_m(3)
2952            True
2953
2954            sage: E = EllipticCurve(GF(17), [-2, 3, -5, 7, -11])
2955            sage: R.<x> = GF(17)[]
2956            sage: f = x+6
2957            sage: phi = EllipticCurveIsogeny(E, f)
2958            sage: phi
2959            Isogeny of degree 2 from Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 7*x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 4*x + 8 over Finite Field of size 17
2960            sage: phi.rational_maps()
2961            ((x^2 + 6*x + 4)/(x + 6), (x^2*y - 5*x*y + 8*x - 2*y)/(x^2 - 5*x + 2))
2962            sage: phi.switch_sign()
2963            sage: phi
2964            Isogeny of degree 2 from Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 7*x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 4*x + 8 over Finite Field of size 17
2965            sage: phi.rational_maps()
2966            ((x^2 + 6*x + 4)/(x + 6),
2967             (2*x^3 - x^2*y - 5*x^2 + 5*x*y - 4*x + 2*y + 7)/(x^2 - 5*x + 2))
2968
2969            sage: E = EllipticCurve('11a1')
2970            sage: R.<x> = QQ[]
2971            sage: f = x^2 - 21*x + 80
2972            sage: phi = EllipticCurveIsogeny(E, f)
2973            sage: (xmap1, ymap1) = phi.rational_maps()
2974            sage: phi.switch_sign()
2975            sage: (xmap2, ymap2) = phi.rational_maps()
2976            sage: xmap1 == xmap2
2977            True
2978            sage: ymap1 == -ymap2 - E.a1()*xmap2 - E.a3()
2979            True
2980
2981            sage: K.<a> = NumberField(x^2 + 1)
2982            sage: E = EllipticCurve(K, [0,0,0,1,0])
2983            sage: R.<x> = K[]
2984            sage: phi = EllipticCurveIsogeny(E, x-a)
2985            sage: phi.rational_maps()
2986            ((x^2 + (-a)*x - 2)/(x + (-a)), (x^2*y + (-2*a)*x*y + y)/(x^2 + (-2*a)*x - 1))
2987            sage: phi.switch_sign()
2988            sage: phi.rational_maps()
2989            ((x^2 + (-a)*x - 2)/(x + (-a)), (-x^2*y + (2*a)*x*y - y)/(x^2 + (-2*a)*x - 1))
2990
2991        """
2992        self.set_post_isomorphism(WeierstrassIsomorphism(self.__E2, (-1,0,-self.__E2.a1(),-self.__E2.a3())))
2993
2994    def is_normalized(self, via_formal=True, check_by_pullback=True):
2995        r"""
2996        Returns True if this isogeny is normalized. An isogeny
2997        \varphi\colon E\to E_2 between two given Weierstrass
2998        equations is said to be normalized if the constant c is 1
2999        in \varphi*(\omega_2) = c\cdot\omega, where \omega and
3000        omega_2 are the invariant differentials on E and E_2
3001        corresponding to the given equation.
3002
3003        INPUT:
3004
3005        - via_formal - (default: True) If True it simply checks if
3006                           the leading term of the formal series is 1. Otherwise
3007                           it uses a deprecated algorithm involving the second
3008                           optional argument.
3009
3010        - check_by_pullback -  (default:True) Deprecated.
3011
3012        EXAMPLES::
3013
3014            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
3015            sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
3016            sage: R.<x> = GF(7)[]
3017            sage: phi = EllipticCurveIsogeny(E, x)
3018            sage: phi.is_normalized()
3019            True
3020            sage: isom = WeierstrassIsomorphism(phi.codomain(), (3, 0, 0, 0))
3021            sage: phi.set_post_isomorphism(isom)
3022            sage: phi.is_normalized()
3023            False
3024            sage: isom = WeierstrassIsomorphism(phi.codomain(), (5, 0, 0, 0))
3025            sage: phi.set_post_isomorphism(isom)
3026            sage: phi.is_normalized()
3027            True
3028            sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
3029            sage: phi.set_post_isomorphism(isom)
3030            sage: phi.is_normalized()
3031            True
3032
3033            sage: F = GF(2^5, 'alpha'); alpha = F.gen()
3034            sage: E = EllipticCurve(F, [1,0,1,1,1])
3035            sage: R.<x> = F[]
3036            sage: phi = EllipticCurveIsogeny(E, x+1)
3037            sage: isom = WeierstrassIsomorphism(phi.codomain(), (alpha, 0, 0, 0))
3038            sage: phi.is_normalized()
3039            True
3040            sage: phi.set_post_isomorphism(isom)
3041            sage: phi.is_normalized()
3042            False
3043            sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/alpha, 0, 0, 0))
3044            sage: phi.set_post_isomorphism(isom)
3045            sage: phi.is_normalized()
3046            True
3047            sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
3048            sage: phi.set_post_isomorphism(isom)
3049            sage: phi.is_normalized()
3050            True
3051
3052            sage: E = EllipticCurve('11a1')
3053            sage: R.<x> = QQ[]
3054            sage: f = x^3 - x^2 - 10*x - 79/4
3055            sage: phi = EllipticCurveIsogeny(E, f)
3056            sage: isom = WeierstrassIsomorphism(phi.codomain(), (2, 0, 0, 0))
3057            sage: phi.is_normalized()
3058            True
3059            sage: phi.set_post_isomorphism(isom)
3060            sage: phi.is_normalized()
3061            False
3062            sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/2, 0, 0, 0))
3063            sage: phi.set_post_isomorphism(isom)
3064            sage: phi.is_normalized()
3065            True
3066            sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1))
3067            sage: phi.set_post_isomorphism(isom)
3068            sage: phi.is_normalized()
3069            True
3070
3071        """
3072        # easy algorithm using the formal expansion.
3073        if via_formal:
3074            phi_formal = self.formal(prec=5)
3075            return phi_formal[1] == 1
3076
3077        # this is the old algorithm. it should be deprecated.
3078        check_prepost_isomorphism = False
3079
3080        f_normalized = True
3081
3082        if (check_by_pullback):
3083
3084            (Xmap, Ymap) = self.rational_maps()
3085
3086            E1 = self.__E1
3087            E2 = self.__E2
3088
3089            a1 = E1.a1()
3090            a3 = E1.a3()
3091
3092            a1pr = E2.a1()
3093            a3pr = E2.a3()
3094
3095            x = self.__x_var
3096            y = self.__y_var
3097
3098            Xmap_pr = Xmap.derivative(x)
3099
3100            domain_inv_diff = 1/(2*y + a1*x + a3)
3101            codomain_inv_diff = Xmap_pr/(2*Ymap + a1pr*Xmap + a3pr)
3102
3103            inv_diff_quo = domain_inv_diff/codomain_inv_diff
3104
3105            if (1 == inv_diff_quo):
3106                f_normalized = True
3107            else:
3108                # For some reason, in certain cases, when the isogeny
3109                # is pre or post composed with a translation the
3110                # resulting rational functions are too complicated for
3111                # sage to simplify down to a constant in this case, we
3112                # do some cheating by checking if the post-composition
3113                # by isogeny has a non 1 scaling factor
3114                if ( inv_diff_quo.numerator().is_constant() and (inv_diff_quo.denominator().is_constant) ):
3115                    f_normalized = False
3116                else:
3117                    check_prepost_isomorphism = True
3118        else:
3119            check_prepost_isomorphism = True
3120
3121        # If we skip checking by the pullback of the invariant
3122        # differential OR if that was inconclusive We explicitly check
3123        # if there is a post isomorphism and if it has a non 1 scaling
3124        # factor or if it is a just a translation.  NOTE: This only
3125        # works because we are using algorithms for calculating the
3126        # isogenies that calculate a separable normalized isogeny, if
3127        # this changes, this check will no longer be correct.
3128        #
3129        if (check_prepost_isomorphism):
3130            post_isom = self.__post_isomorphism
3131            if (post_isom is not None):
3132                if (1 == self.__base_field(post_isom.u)):
3133                    f_post_normalized = True
3134                else:
3135                    f_post_normalized = False
3136            else:
3137                f_post_normalized = True
3138
3139            pre_isom = self.__pre_isomorphism
3140            if (pre_isom is not None):
3141                if (1 == self.__base_field(pre_isom.u)):
3142                    f_pre_normalized = True
3143                else:
3144                    f_pre_normalized = False
3145            else:
3146                f_pre_normalized = True
3147
3148            f_normalized = f_pre_normalized and f_post_normalized
3149
3150        return f_normalized
3151
3152    def dual(self):
3153        r"""
3154        Computes and returns the dual isogeny of this isogeny. If
3155        \varphi\colon E \to E_2 is the given isogeny, then the dual
3156        is by definition the unique isogeny \hat\varphi\colon E_2\to
3157        E such that the compositions \hat\varphi\circ\varphi and
3158        \varphi\circ\hat\varphi are the multiplication [n] by the
3159        degree of \varphi on E and E_2 respectively.
3160
3161        EXAMPLES::
3162
3163            sage: E = EllipticCurve('11a1')
3164            sage: R.<x> = QQ[]
3165            sage: f = x^2 - 21*x + 80
3166            sage: phi = EllipticCurveIsogeny(E, f)
3167            sage: phi_hat = phi.dual()
3168            sage: phi_hat.domain() == phi.codomain()
3169            True
3170            sage: phi_hat.codomain() == phi.domain()
3171            True
3172            sage: (X, Y) = phi.rational_maps()
3173            sage: (Xhat, Yhat) = phi_hat.rational_maps()
3174            sage: Xm = Xhat.subs(x=X, y=Y)
3175            sage: Ym = Yhat.subs(x=X, y=Y)
3176            sage: (Xm, Ym) == E.multiplication_by_m(5)
3177            True
3178
3179            sage: E = EllipticCurve(GF(37), [0,0,0,1,8])
3180            sage: R.<x> = GF(37)[]
3181            sage: f = x^3 + x^2 + 28*x + 33
3182            sage: phi = EllipticCurveIsogeny(E, f)
3183            sage: phi_hat = phi.dual()
3184            sage: phi_hat.codomain() == phi.domain()
3185            True
3186            sage: phi_hat.domain() == phi.codomain()
3187            True
3188            sage: (X, Y) = phi.rational_maps()
3189            sage: (Xhat, Yhat) = phi_hat.rational_maps()
3190            sage: Xm = Xhat.subs(x=X, y=Y)
3191            sage: Ym = Yhat.subs(x=X, y=Y)
3192            sage: (Xm, Ym) == E.multiplication_by_m(7)
3193            True
3194
3195            sage: E = EllipticCurve(GF(31), [0,0,0,1,8])
3196            sage: R.<x> = GF(31)[]
3197            sage: f = x^2 + 17*x + 29
3198            sage: phi = EllipticCurveIsogeny(E, f)
3199            sage: phi_hat = phi.dual()
3200            sage: phi_hat.codomain() == phi.domain()
3201            True
3202            sage: phi_hat.domain() == phi.codomain()
3203            True
3204            sage: (X, Y) = phi.rational_maps()
3205            sage: (Xhat, Yhat) = phi_hat.rational_maps()
3206            sage: Xm = Xhat.subs(x=X, y=Y)
3207            sage: Ym = Yhat.subs(x=X, y=Y)
3208            sage: (Xm, Ym) == E.multiplication_by_m(5)
3209            True
3210
3211        Test (for trac ticket 7096)::
3212
3213            sage: E = EllipticCurve('11a1')
3214            sage: phi = E.isogeny(E(5,5))
3215            sage: phi.dual().dual() == phi
3216            True
3217
3218            sage: k = GF(103)
3219            sage: E = EllipticCurve(k,[11,11])
3220            sage: phi = E.isogeny(E(4,4))
3221            sage: phi
3222            Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x + 11 over Finite Field of size 103 to Elliptic Curve defined by y^2 = x^3 + 25*x + 80 over Finite Field of size 103
3223            sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism
3224            sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(),(5,0,1,2)))
3225            sage: phi.dual().dual() == phi
3226            True
3227
3228            sage: E = EllipticCurve(GF(103),[1,0,0,1,-1])
3229            sage: phi = E.isogeny(E(60,85))
3230            sage: phi.dual()
3231            Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 84*x + 34 over Finite Field of size 103 to Elliptic Curve defined by y^2 + x*y = x^3 + x + 102 over Finite Field of size 103
3232
3233        """
3234
3235        if (self.__base_field.characteristic() in [2,3]):
3236            raise NotImplemented
3237
3238        if (self.__dual is not None):
3239            return self.__dual
3240
3241        # trac 7096
3242        (E1, E2pr, pre_isom, post_isom) = compute_intermediate_curves(self.__E2, self.__E1)
3243
3244        F = self.__base_field
3245
3246        d = self.__degree
3247
3248        # trac 7096
3249        if F(d) == 0:
3250            raise NotImplementedError, "The dual isogeny is not separable, but only separable isogenies are implemented so far"
3251
3252        # trac 7096
3253        # this should take care of the case when the isogeny is not normalized.
3254        u = self.formal(prec=5)[1]
3255        isom = WeierstrassIsomorphism(E2pr, (u/F(d), 0, 0, 0))
3256
3257        E2 = isom.codomain().codomain()
3258
3259        pre_isom = self.__E2.isomorphism_to(E1)
3260        post_isom = E2.isomorphism_to(self.__E1)
3261
3262        phi_hat = EllipticCurveIsogeny(E1, None, E2, d)
3263
3264        phi_hat.set_pre_isomorphism(pre_isom)
3265        phi_hat.set_post_isomorphism(post_isom)
3266        phi_hat.__perform_inheritance_housekeeping()
3267
3268        assert phi_hat.codomain() == self.domain()
3269
3270        # trac 7096 : this adjust a posteriori the automorphism
3271        # on the codomain of the dual isogeny.
3272        # we used _a_ Weierstrass isomorphism to get to the original
3273        # curve, but we may have to change it my an automorphism.
3274        # we impose that the composition has the degree
3275        # as a leading coefficient in the formal expansion.
3276
3277        phi_sc = self.formal(prec=5)[1]
3278        phihat_sc = phi_hat.formal(prec=5)[1]
3279
3280        sc = phi_sc * phihat_sc/F(d)
3281        print sc
3282        if sc != 1:
3283            auts = phi_hat.codomain().automorphsims()
3284            aut = [a for a in auts if a.u == sc]
3285            if len(aut) != 1:
3286                raise ValueError, "There is a bug in dual()."
3287            phi_hat.set_post_isomorphism(a[0])
3288
3289        self.__dual = phi_hat
3290
3291        return phi_hat
3292
3293    def formal(self,prec=20):
3294        r"""
3295        Computes the formal isogeny as a power series in the variable
3296        t=-x/y on the domain curve.
3297
3298        INPUT:
3299
3300        - prec - (default = 20), the precision with which the computations
3301                     in the formal group are carried out.
3302
3303        EXAMPLES::
3304
3305            sage: E = EllipticCurve(GF(13),[1,7])
3306            sage: phi = E.isogeny(E(10,4))
3307            sage: phi.formal()
3308            t + 12*t^13 + 2*t^17 + 8*t^19 + 2*t^21 + O(t^23)
3309
3310            sage: E = EllipticCurve([0,1])
3311            sage: phi = E.isogeny(E(2,3))
3312            sage: phi.formal(prec=10)
3313            t + 54*t^5 + 255*t^7 + 2430*t^9 + 19278*t^11 + O(t^13)
3314
3315            sage: E = EllipticCurve('11a2')
3316            sage: R.<x> = QQ[]
3317            sage: phi = E.isogeny(x^2 + 101*x + 12751/5)
3318            sage: phi.formal(prec=7)
3319            t - 2724/5*t^5 + 209046/5*t^7 - 4767/5*t^8 + 29200946/5*t^9 + O(t^10)
3320
3321
3322        """
3323        Eh = self.__E1.formal()
3324        f, g = self.rational_maps()
3325        xh = Eh.x(prec=prec)
3326        yh = Eh.y(prec=prec)
3327        fh = f(xh,yh)
3328        gh = g(xh,yh)
3329        return -fh/gh
3330
3331    #
3332    # Overload Morphism methods that we want to
3333    #
3334    # !!!! S. Besnier change here !!!! : comment the all function
3335    #def _composition_(self, right, homset):
3336        r"""
3337        Composition operator function inherited from morphism class.
3338
3339        EXAMPLES::
3340
3341            sage: E = EllipticCurve(j=GF(7)(0))
3342            sage: phi = EllipticCurveIsogeny(E, [E(0), E((0,1)), E((0,-1))])
3343            sage: phi._composition_(phi, phi.parent())
3344            Traceback (most recent call last):
3345            ...
3346            NotImplementedError
3347
3348        The following should test that :meth:_composition_ is called
3349        upon a product. However phi is currently improperly
3350        constructed (see :trac:12880), which triggers an assertion
3351        failure before the actual call ::
3352
3353            sage: phi*phi
3354            Traceback (most recent call last):
3355            ...
3356            TypeError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 is not in Category of hom sets in Category of Schemes
3357
3358        Here would be the desired output::
3359
3360            sage: phi*phi            # not tested
3361            Traceback (most recent call last):
3362            ...
3363            NotImplementedError
3364        """
3365        #raise NotImplementedError
3366
3367
3368    def is_injective(self):
3369        r"""
3370        Method inherited from the morphism class.  Returns True if
3371        and only if this isogeny has trivial kernel.
3372
3373        EXAMPLES::
3374
3375            sage: E = EllipticCurve('11a1')
3376            sage: R.<x> = QQ[]
3377            sage: f = x^2 + x - 29/5
3378            sage: phi = EllipticCurveIsogeny(E, f)
3379            sage: phi.is_injective()
3380            False
3381            sage: phi = EllipticCurveIsogeny(E, R(1))
3382            sage: phi.is_injective()
3383            True
3384
3385            sage: F = GF(7)
3386            sage: E = EllipticCurve(j=F(0))
3387            sage: phi = EllipticCurveIsogeny(E, [ E((0,-1)), E((0,1))])
3388            sage: phi.is_injective()
3389            False
3390            sage: phi = EllipticCurveIsogeny(E, E(0))
3391            sage: phi.is_injective()
3392            True
3393
3394        """
3395
3396        if (1 < self.__degree): return False
3397        return True
3398
3399
3400    def is_surjective(self):
3401        r"""
3402        For elliptic curve isogenies, always returns True (as a
3403        non-constant map of algebraic curves must be surjective).
3404
3405        EXAMPLES::
3406
3407            sage: E = EllipticCurve('11a1')
3408            sage: R.<x> = QQ[]
3409            sage: f = x^2 + x - 29/5
3410            sage: phi = EllipticCurveIsogeny(E, f)
3411            sage: phi.is_surjective()
3412            True
3413
3414            sage: E = EllipticCurve(GF(7), [0,0,0,1,0])
3415            sage: phi = EllipticCurveIsogeny(E,  E((0,0)))
3416            sage: phi.is_surjective()
3417            True
3418
3419            sage: F = GF(2^5, 'omega')
3420            sage: E = EllipticCurve(j=F(0))
3421            sage: R.<x> = F[]
3422            sage: phi = EllipticCurveIsogeny(E, x)
3423            sage: phi.is_surjective()
3424            True
3425
3426        """
3427        return True
3428
3429    def is_zero(self):
3430        r"""
3431        Member function inherited from morphism class.
3432
3433        EXAMPLES::
3434
3435            sage: E = EllipticCurve(j=GF(7)(0))
3436            sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])
3437            sage: phi.is_zero()
3438            Traceback (most recent call last):
3439            ...
3440            NotImplementedError
3441        """
3442        raise NotImplementedError
3443
3444    def post_compose(self, left):
3445        r"""
3446        Member function inherited from morphism class.
3447
3448        EXAMPLES::
3449
3450            sage: E = EllipticCurve(j=GF(7)(0))
3451            sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])
3452            sage: phi.post_compose(phi)
3453            Traceback (most recent call last):
3454            ...
3455            NotImplementedError
3456
3457        """
3458        raise NotImplementedError
3459
3460
3461    def pre_compose(self, right):
3462        r"""
3463        Member function inherited from morphism class.
3464
3465        EXAMPLES::
3466
3467            sage: E = EllipticCurve(j=GF(7)(0))
3468            sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])
3469            sage: phi.pre_compose(phi)
3470            Traceback (most recent call last):
3471            ...
3472            NotImplementedError
3473
3474        """
3475        raise NotImplementedError
3476
3477
3478    def n(self):
3479        r"""
3480        Numerical Approximation inherited from Map (through morphism),
3481        nonsensical for isogenies.
3482
3483        EXAMPLES::
3484
3485            sage: E = EllipticCurve(j=GF(7)(0))
3486            sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))])
3487            sage: phi.n()
3488            Traceback (most recent call last):
3489            ...
3490            NotImplementedError: Numerical approximations do not make sense for Elliptic Curve Isogenies
3491
3492        """
3493        raise NotImplementedError, "Numerical approximations do not make sense for Elliptic Curve Isogenies"
3494
3495# no longer needed (trac 7096)
3496# def starks_find_r_and_t(T, Z):
3497
3498def compute_isogeny_starks(E1, E2, ell):
3499    r"""
3500    Computes the degree ell isogeny between E1 and E2 via
3501    Stark's algorithm.  There must be a degree ell, separable,
3502    normalized cyclic isogeny from E1 to E2.
3503
3504    INPUT:
3505
3506    - E1  - an elliptic curve in short Weierstrass form.
3507    - E2  - an elliptic curve in short Weierstrass form.
3508    - ell - the degree of the isogeny from E1 to E2.
3509
3510    OUTPUT:
3511
3512    polynomial -- over the field of definition of E1, E2, that is the
3513                  kernel polynomial of the isogeny from E1 to E2.
3514
3515    ALGORITHM:
3516
3517    This function uses Starks Algorithm as presented in section 6.2 of
3518    [BMSS].
3519
3520    .. note::
3521
3522       As published there, the algorithm is incorrect, and a correct
3523       version (with slightly different notation) can be found in
3524       [M09].  The algorithm originates in [S72]
3525
3526    REFERENCES:
3527
3528    - [BMSS] Boston, Morain, Salvy, Schost, "Fast Algorithms for Isogenies."
3529    - [M09] Moody, "The Diffie-Hellman Problem and Generalization of Verheul's Theorem"
3530    - [S72] Stark, "Class-numbers of complex quadratic fields."
3531
3532    EXAMPLES::
3533
3534        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks, compute_sequence_of_maps
3535
3536        sage: E = EllipticCurve(GF(97), [1,0,1,1,0])
3537        sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21
3538        sage: phi = EllipticCurveIsogeny(E, f)
3539        sage: E2 = phi.codomain()
3540        sage: (isom1, isom2, E1pr, E2pr, ker_poly) = compute_sequence_of_maps(E, E2, 11)
3541        sage: compute_isogeny_starks(E1pr, E2pr, 11)
3542        x^10 + 37*x^9 + 53*x^8 + 66*x^7 + 66*x^6 + 17*x^5 + 57*x^4 + 6*x^3 + 89*x^2 + 53*x + 8
3543
3544        sage: E = EllipticCurve(GF(37), [0,0,0,1,8])
3545        sage: R.<x> = GF(37)[]
3546        sage: f = (x + 14) * (x + 30)
3547        sage: phi = EllipticCurveIsogeny(E, f)
3548        sage: E2 = phi.codomain()
3549        sage: compute_isogeny_starks(E, E2, 5)
3550        x^4 + 14*x^3 + x^2 + 34*x + 21
3551        sage: f**2
3552        x^4 + 14*x^3 + x^2 + 34*x + 21
3553
3554        sage: E = EllipticCurve(QQ, [0,0,0,1,0])
3555        sage: R.<x> = QQ[]
3556        sage: f = x
3557        sage: phi = EllipticCurveIsogeny(E, f)
3558        sage: E2 = phi.codomain()
3559        sage: compute_isogeny_starks(E, E2, 2)
3560        x
3561
3562    """
3563
3564    K = E1.base_field()
3565    R = PolynomialRing(K, 'x')
3566    x = R.gen()
3567
3568    wp1 = E1.weierstrass_p(prec=4*ell+4)  #BMSS claim 2*ell is enough, but it is not M09
3569    wp2 = E2.weierstrass_p(prec=4*ell+4)
3570
3571    # viewed them as power series in Z = z^2
3572    S = LaurentSeriesRing(K, 'Z')
3573    Z = S.gen()
3574    pe1 = 1/Z
3575    pe2 = 1/Z
3576    for i in xrange(2*ell+1):
3577        pe1 += wp1[2*i] * Z**i
3578        pe2 += wp2[2*i] * Z**i
3581
3582    #print 'wps = ',pe1
3583    #print 'wps2 = ',pe2
3584
3585    n = 1
3586    q = [R(1), R(0)]
3587    #p = [R(0), R(1)]
3588    T = pe2
3589
3590    while ( q[n].degree() < (ell-1) ):
3591        #print 'n=', n
3592
3593        n += 1
3594        a_n = 0
3595        r = -T.valuation()
3596        while (0 <= r):
3597            t_r = T[-r]
3598            #print '    r=',r
3599            #print '    t_r=',t_r
3600            #print '    T=',T
3601            a_n = a_n + t_r * x**r
3602            T = T - t_r*pe1**r
3603            r = -T.valuation()
3604
3605
3606        q_n = a_n*q[n-1] + q[n-2]
3607        q.append(q_n)
3608        #p_n = a_n*p[n-1] + q[n-2]
3609        #p.append(p_n)
3610
3611        if (n == ell+1 or T == 0):
3612            if (T == 0 or T.valuation()<2):
3613                raise ValueError("The two curves are not linked by a cyclic normalized isogeny of degree %s" % ell)
3614            #print 'breaks here'
3615            break
3616
3617        T = 1/T
3618        #print '  a_n=', a_n
3619        #print '  q_n=', q_n
3620        #print '  p_n=', p_n
3621        #print '  T = ', T
3622
3623    qn = q[n]
3624    #pn= p[n]
3625    #print 'final  T = ', T
3626    #print '  f =', pn/qn
3627
3630
3631    return qn
3632
3633def split_kernel_polynomial(E1, ker_poly, ell):
3634    r"""
3635    Internal helper function for compute_isogeny_kernel_polynomial.
3636
3637    Given a full kernel polynomial (where two torsion x-coordinates
3638    are roots of multiplicity 1, and all other roots have multiplicity
3639    2.)  of degree \ell-1, returns the maximum separable divisor.
3640    (i.e. the kernel polynomial with roots of multiplicity at most 1).
3641
3642    EXAMPLES:
3643
3644    The following example implicitly exercises this function::
3645
3646        sage: E = EllipticCurve(GF(37), [0,0,0,1,8])
3647        sage: R.<x> = GF(37)[]
3648        sage: f = (x + 10) * (x + 12) * (x + 16)
3649        sage: phi = EllipticCurveIsogeny(E, f)
3650        sage: E2 = phi.codomain()
3651        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks
3652        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import split_kernel_polynomial
3653        sage: ker_poly = compute_isogeny_starks(E, E2, 7); ker_poly
3654        x^6 + 2*x^5 + 20*x^4 + 11*x^3 + 36*x^2 + 35*x + 16
3655        sage: split_kernel_polynomial(E, ker_poly, 7)
3656        x^3 + x^2 + 28*x + 33
3657
3658    """
3659
3660    poly_ring = ker_poly.parent()
3661
3662    z = poly_ring.gen(0)
3663
3664    ker_poly_2tor = two_torsion_part(E1, poly_ring, ker_poly, ell)
3665    ker_poly_quo = poly_ring(ker_poly/ker_poly_2tor)
3666    ker_poly_quo_sqrt = ker_poly_quo.gcd(ker_poly_quo.derivative(z))
3667    ker_poly = ker_poly_2tor*ker_poly_quo_sqrt
3669
3670    return ker_poly
3671
3672
3673def compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm="starks"):
3674    r"""
3675    Computes the kernel polynomial of the degree ell isogeny
3676    between E1 and E2.  There must be a degree ell,
3677    cyclic, separable, normalized isogeny from E1 to E2.
3678
3679    INPUT:
3680
3681    - E1        - an elliptic curve in short Weierstrass form.
3682
3683    - E2        - an elliptic curve in short Weierstrass form.
3684
3685    - ell       - the degree of the isogeny from E1 to E2.
3686
3687    - algorithm - currently only starks (default) is implemented.
3688
3689    OUTPUT:
3690
3691    polynomial -- over the field of definition of E1, E2, that is the
3692                  kernel polynomial of the isogeny from E1 to E2.
3693
3694    EXAMPLES::
3695
3696        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_kernel_polynomial
3697
3698        sage: E = EllipticCurve(GF(37), [0,0,0,1,8])
3699        sage: R.<x> = GF(37)[]
3700        sage: f = (x + 14) * (x + 30)
3701        sage: phi = EllipticCurveIsogeny(E, f)
3702        sage: E2 = phi.codomain()
3703        sage: compute_isogeny_kernel_polynomial(E, E2, 5)
3704        x^2 + 7*x + 13
3705        sage: f
3706        x^2 + 7*x + 13
3707
3708        sage: R.<x> = QQ[]
3709        sage: K.<i> = NumberField(x^2 + 1)
3710        sage: E = EllipticCurve(K, [0,0,0,1,0])
3711        sage: E2 = EllipticCurve(K, [0,0,0,16,0])
3712        sage: compute_isogeny_kernel_polynomial(E, E2, 4)
3713        x^3 + x
3714
3715    """
3716
3717    ker_poly = compute_isogeny_starks(E1, E2, ell)
3718    ker_poly = split_kernel_polynomial(E1, ker_poly, ell)
3719
3720    return ker_poly
3721
3722
3723def compute_intermediate_curves(E1, E2):
3724    r"""
3725    Computes isomorphism from E1 to an intermediate domain and an
3726    isomorphism from an intermediate codomain to E2.
3727
3728    Intermediate domain and intermediate codomain, are in short
3729    Weierstrass form.
3730
3731    This is used so we can compute \wp functions from the short
3732    Weierstrass model more easily.
3733
3734    The underlying field must be of characteristic not equal to 2,3.
3735
3736    INPUT:
3737
3738    - E1 - an elliptic curve
3739    - E2 - an elliptic curve
3740
3741    OUTPUT:
3742
3743    tuple -- (pre_isomorphism, post_isomorphism, intermediate_domain,
3744              intermediate_codomain):
3745
3746    - intermediate_domain: a short Weierstrass model isomorphic to E1
3747    - intermediate_codomain: a short Weierstrass model isomorphic to E2
3748    - pre_isomorphism: normalized isomorphism from E1 to intermediate_domain
3749    - post_isomorphism: normalized isomorphism from intermediate_codomain to E2
3750
3751    EXAMPLES::
3752
3753        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_intermediate_curves
3754        sage: E = EllipticCurve(GF(83), [1,0,1,1,0])
3755        sage: R.<x> = GF(83)[]; f = x+24
3756        sage: phi = EllipticCurveIsogeny(E, f)
3757        sage: E2 = phi.codomain()
3758        sage: compute_intermediate_curves(E, E2)
3759        (Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83,
3760         Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83,
3761         Generic morphism:
3762          From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 83
3763          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83
3764          Via:  (u,r,s,t) = (1, 76, 41, 3),
3765         Generic morphism:
3766          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83
3767          To:   Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 83
3768          Via:  (u,r,s,t) = (1, 7, 42, 80))
3769
3770        sage: R.<x> = QQ[]
3771        sage: K.<i> = NumberField(x^2 + 1)
3772        sage: E = EllipticCurve(K, [0,0,0,1,0])
3773        sage: E2 = EllipticCurve(K, [0,0,0,16,0])
3774        sage: compute_intermediate_curves(E, E2)
3775        (Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,
3776         Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1,
3777         Generic morphism:
3778          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1
3779          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1
3780          Via:  (u,r,s,t) = (1, 0, 0, 0),
3781         Generic morphism:
3782          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1
3783          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1
3784          Via:  (u,r,s,t) = (1, 0, 0, 0))
3785
3786    """
3787
3788    if (E1.base_ring().characteristic() in [2,3]):
3789        raise NotImplemented
3790
3791    # compute the r,s,t values that clear the denominator of E1
3792    a1 = E1.a1()
3793    a2 = E1.a2()
3794    a3 = E1.a3()
3795
3796    s1 = -a1/2
3797    r1 = (s1**2 + s1*a1 - a2)/3
3798    t1 = (-r1*a1 - a3)/2
3799
3800    # compute the isomorphism from E1 to intermediate_domain
3801    pre_isom = WeierstrassIsomorphism(E1, (1, r1, s1, t1))
3802
3803    intermediate_domain = pre_isom.codomain().codomain()
3804
3805    # compute the r,s,t values that clear the denominator of E2
3806    a1pr = E2.a1()
3807    a2pr = E2.a2()
3808    a3pr = E2.a3()
3809
3810    s2 = -a1pr/2
3811    r2 = (s2**2 + s2*a1pr - a2pr)/3
3812    t2 = (-r2*a1pr - a3pr)/2
3813
3814    post_isom_inv = WeierstrassIsomorphism(E2, (1, r2, s2, t2))
3815    intermediate_codomain = post_isom_inv.codomain().codomain()
3816
3817    post_isom = WeierstrassIsomorphism(intermediate_codomain, (1, -r2, -s2, -t2))
3818
3819    return (intermediate_domain, intermediate_codomain, pre_isom, post_isom)
3820
3821
3822def compute_sequence_of_maps(E1, E2, ell):
3823    r"""
3824    Given domain E1 and codomain E2 such that there is a
3825    degree ell separable normalized isogeny from E1 to E2,
3826    returns pre/post isomorphism, as well as intermediate domain and
3827    codomain, and kernel polynomial.
3828
3829    EXAMPLES::
3830
3831        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_sequence_of_maps
3832        sage: E = EllipticCurve('11a1')
3833        sage: R.<x> = QQ[]; f = x^2 - 21*x + 80
3834        sage: phi = EllipticCurveIsogeny(E, f)
3835        sage: E2 = phi.codomain()
3836        sage: compute_sequence_of_maps(E, E2, 5)
3837        (Generic morphism:
3838          From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field
3839          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field
3840          Via:  (u,r,s,t) = (1, 1/3, 0, -1/2),
3841         Generic morphism:
3842          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field
3843          To:   Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field
3844          Via:  (u,r,s,t) = (1, -1/3, 0, 1/2),
3845         Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field,
3846         Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field,
3847         x^2 - 61/3*x + 658/9)
3848
3849        sage: K.<i> = NumberField(x^2 + 1)
3850        sage: E = EllipticCurve(K, [0,0,0,1,0])
3851        sage: E2 = EllipticCurve(K, [0,0,0,16,0])
3852        sage: compute_sequence_of_maps(E, E2, 4)
3853        (Generic morphism:
3854          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1
3855          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1
3856          Via:  (u,r,s,t) = (1, 0, 0, 0),
3857         Generic morphism:
3858          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1
3859          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1
3860          Via:  (u,r,s,t) = (1, 0, 0, 0),
3861         Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1,
3862         Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1,
3863         x^3 + x)
3864
3865        sage: E = EllipticCurve(GF(97), [1,0,1,1,0])
3866        sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21
3867        sage: phi = EllipticCurveIsogeny(E, f)
3868        sage: E2 = phi.codomain()
3869        sage: compute_sequence_of_maps(E, E2, 11)
3870        (Generic morphism:
3871          From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 97
3872          To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97
3873          Via:  (u,r,s,t) = (1, 8, 48, 44),
3874         Generic morphism:
3875          From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97
3876          To:   Abelian group of points on Elliptic Curve defined by y^2 + x*y + 9*y = x^3 + 83*x + 6 over Finite Field of size 97
3877          Via:  (u,r,s,t) = (1, 89, 49, 53),
3878         Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97,
3879         Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97,
3880         x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69)
3881
3882    """
3883
3884    (E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2)
3885
3886    ker_poly = compute_isogeny_kernel_polynomial(E1pr, E2pr, ell)
3887
3888    return (pre_isom, post_isom, E1pr, E2pr, ker_poly)
3889
3890
3891# Utility function for manipulating isogeny degree matrices
3892
3893def fill_isogeny_matrix(M):
3894    """
3895    Returns a filled isogeny matrix giving all degrees from one giving only prime degrees.
3896
3897    INPUT:
3898
3899    - M -- a square symmetric matrix whose off-diagonal i, j
3900      entry is either a prime l (if the i'th and j'th curves
3901      have an l-isogeny between them), otherwise is 0.
3902
3903    OUTPUT:
3904
3905    (matrix) a square matrix with entries 1 on the diagonal, and in
3906    general the i, j entry is d>0 if d is the minimal degree
3907    of an isogeny from the i'th to the j'th curve,
3908
3909    EXAMPLES::
3910
3911        sage: M = Matrix([[0, 2, 3, 3, 0, 0], [2, 0, 0, 0, 3, 3], [3, 0, 0, 0, 2, 0], [3, 0, 0, 0, 0, 2], [0, 3, 2, 0, 0, 0], [0, 3, 0, 2, 0, 0]]); M
3912        [0 2 3 3 0 0]
3913        [2 0 0 0 3 3]
3914        [3 0 0 0 2 0]
3915        [3 0 0 0 0 2]
3916        [0 3 2 0 0 0]
3917        [0 3 0 2 0 0]
3918        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix
3919        sage: fill_isogeny_matrix(M)
3920        [ 1  2  3  3  6  6]
3921        [ 2  1  6  6  3  3]
3922        [ 3  6  1  9  2 18]
3923        [ 3  6  9  1 18  2]
3924        [ 6  3  2 18  1  9]
3925        [ 6  3 18  2  9  1]
3926    """
3927    from sage.matrix.all import Matrix
3928    from sage.rings.infinity import Infinity
3929
3930    n = M.nrows()
3931    M0 = copy(M)
3932    for i in range(n):
3933        M0[i,i]=1
3934
3935    def fix(d):
3936        if d==0: return Infinity
3937        return d
3938
3939    def fix2(d):
3940        if d==Infinity: return 0
3941        return d
3942
3943    def pr(M1,M2):
3944        return Matrix([[fix2(min([fix(M1[i,k]*M2[k,j]) for k in range(n)])) for i in range(n)] for j in range(n)])
3945
3946    M1 = M0
3947    M2 = pr(M0,M1)
3948    while M1!=M2:
3949        M1 = M2
3950        M2 = pr(M0,M1)
3951
3952    return M1
3953
3954def unfill_isogeny_matrix(M):
3955    """
3956    Reverses the action of fill_isogeny_matrix.
3957
3958    INPUT:
3959
3960    - M -- a square symmetric matrix of integers.
3961
3962    OUTPUT:
3963
3964    (matrix) a square symmetric matrix obtained from M by
3965    replacing non-prime entries with 0.
3966
3967    EXAMPLES::
3968
3969        sage: M = Matrix([[0, 2, 3, 3, 0, 0], [2, 0, 0, 0, 3, 3], [3, 0, 0, 0, 2, 0], [3, 0, 0, 0, 0, 2], [0, 3, 2, 0, 0, 0], [0, 3, 0, 2, 0, 0]]); M
3970        [0 2 3 3 0 0]
3971        [2 0 0 0 3 3]
3972        [3 0 0 0 2 0]
3973        [3 0 0 0 0 2]
3974        [0 3 2 0 0 0]
3975        [0 3 0 2 0 0]
3976        sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix, unfill_isogeny_matrix
3977        sage: M1 = fill_isogeny_matrix(M); M1
3978        [ 1  2  3  3  6  6]
3979        [ 2  1  6  6  3  3]
3980        [ 3  6  1  9  2 18]
3981        [ 3  6  9  1 18  2]
3982        [ 6  3  2 18  1  9]
3983        [ 6  3 18  2  9  1]
3984        sage: unfill_isogeny_matrix(M1)
3985        [0 2 3 3 0 0]
3986        [2 0 0 0 3 3]
3987        [3 0 0 0 2 0]
3988        [3 0 0 0 0 2]
3989        [0 3 2 0 0 0]
3990        [0 3 0 2 0 0]
3991        sage: unfill_isogeny_matrix(M1) == M
3992        True
3993    """
3994    from sage.matrix.all import Matrix
3995    from sage.rings.infinity import Infinity
3996
3997    n = M.nrows()
3998    M1 = copy(M)
3999    zero = Integer(0)
4000    for i in range(n):
4001        M1[i,i] = zero
4002        for j in range(i):
4003            if not M1[i,j].is_prime():
4004                M1[i,j] = zero
4005                M1[j,i] = zero
4006    return M1