# source:sage/schemes/elliptic_curves/ell_generic.py@12287:d7533ae4895e

Revision 12287:d7533ae4895e, 95.2 KB checked in by Mike Hansen <mhansen@…>, 4 years ago (diff)

Updates for Pynac-0.1.7, main symbolics switch (#5930)

Line
1r"""
2Elliptic curves over a general ring.
3
4Elliptic curves are always represented by 'Weierstrass Models' with
5five coefficients [a_1,a_2,a_3,a_4,a_6] in standard
6notation. In Magma, 'Weierstrass Model' means a model with
7a1=a2=a3=0, which is called 'Short Weierstrass Model' in Sage;
8these only exist in characteristics other than 2 and 3.
9
10EXAMPLES:
11
12We construct an elliptic curve over an elaborate base ring::
13
14    sage: p = 97; a=1; b=3
15    sage: R, u = PolynomialRing(GF(p), 'u').objgen()
16    sage: S, v = PolynomialRing(R, 'v').objgen()
17    sage: T = S.fraction_field()
18    sage: E = EllipticCurve(T, [a, b]); E
19    Elliptic Curve defined by y^2  = x^3 + x + 3 over Fraction Field of Univariate Polynomial Ring in v over Univariate Polynomial Ring in u over Finite Field of size 97
20    sage: latex(E)
21    y^2  = x^3 + x + 3
22
23AUTHORS:
24
25- William Stein (2005): Initial version
26
27- Robert Bradshaw et al....
28
29- John Cremona (2008-01): isomorphisms, automorphisms and twists in all characteristics
30"""
31
32#*****************************************************************************
33#       Copyright (C) 2005 William Stein <wstein@gmail.com>
34#
35#  Distributed under the terms of the GNU General Public License (GPL)
36#
37#    This code is distributed in the hope that it will be useful,
38#    but WITHOUT ANY WARRANTY; without even the implied warranty of
39#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
40#    General Public License for more details.
41#
42#  The full text of the GPL is available at:
43#
44#                  http://www.gnu.org/licenses/
45#*****************************************************************************
46
47import math
48
49from sage.rings.all import PolynomialRing, polygen
50import sage.groups.abelian_gps as groups
51import sage.groups.generic as generic
52import sage.plot.all as plot
53
54import sage.rings.arith as arith
55import sage.rings.all as rings
56import sage.rings.number_field as number_field
57from sage.rings.number_field.all import is_NumberField
58from sage.rings.all import is_Infinite
59import sage.misc.misc as misc
60import sage.misc.latex as latex
61import sage.modular.modform as modform
62import sage.functions.transcendental as transcendental
63
64from sage.categories.morphism import IdentityMorphism
65from sage.categories.homset import Hom
66from sage.rings.arith import lcm
67
68# Schemes
69import sage.schemes.generic.projective_space as projective_space
70import sage.schemes.generic.homset as homset
71
72import ell_point
73import ell_torsion
74import constructor
75import formal_group
76import weierstrass_morphism as wm
77from constructor import EllipticCurve
78
79
80factor = arith.factor
81sqrt = math.sqrt
82exp = math.exp
83mul = misc.mul
84next_prime = arith.next_prime
85
86oo = rings.infinity       # infinity
87O = rings.O         # big oh
88
89import sage.schemes.plane_curves.projective_curve as plane_curve
90
91def is_EllipticCurve(x):
92    r"""
93    Utility function to test if x is an instance of an Elliptic Curve class.
94
95    EXAMPLES::
96
97        sage: from sage.schemes.elliptic_curves.ell_generic import is_EllipticCurve
98        sage: E = EllipticCurve([1,2,3/4,7,19])
99        sage: is_EllipticCurve(E)
100        True
101        sage: is_EllipticCurve(0)
102        False
103    """
104    return isinstance(x, EllipticCurve_generic)
105
106class EllipticCurve_generic(plane_curve.ProjectiveCurve_generic):
107    r"""
108    Elliptic curve over a generic base ring.
109
110    EXAMPLES::
111
112        sage: E = EllipticCurve([1,2,3/4,7,19]); E
113        Elliptic Curve defined by y^2 + x*y + 3/4*y = x^3 + 2*x^2 + 7*x + 19 over Rational Field
114        sage: loads(E.dumps()) == E
115        True
116        sage: E = EllipticCurve([1,3])
117        sage: P = E([-1,1,1])
118        sage: -5*P
119        (179051/80089 : -91814227/22665187 : 1)
120    """
121    def __init__(self, ainvs, extra=None):
122        r"""
123        Constructor from a-invariants (long or short Weierstrass coefficients).
124
125        INPUT:
126
127        - ainvs (list) -- either [a_1,a_2,a_3,a_4,a_6] or
128          [a_4,a_6] (with a_1=a_2=a_3=0 in the second case).
129
130        .. note::
131
132           See constructor.py for more variants.
133
134        EXAMPLES::
135
136            sage: E = EllipticCurve([1,2,3,4,5]); E
137            Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field
138            sage: E = EllipticCurve(GF(7),[1,2,3,4,5]); E
139            Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 7
140
141        Constructor from [a_4,a_6] sets a_1=a_2=a_3=0::
142
143            sage: EllipticCurve([4,5]).ainvs()
144            [0, 0, 0, 4, 5]
145
146        The base ring need not be a field::
147
148            sage: EllipticCurve(IntegerModRing(91),[1,2,3,4,5])
149            Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Ring of integers modulo 91
150        """
151        if extra != None:   # possibility of two arguments
152            K, ainvs = ainvs, extra
153        else:
154            K = ainvs[0].parent()
155        assert len(ainvs) == 2 or len(ainvs) == 5
156        self.__base_ring = K
157        ainvs = [K(x) for x in ainvs]
158        if len(ainvs) == 2:
159            ainvs = [K(0),K(0),K(0)] + ainvs
160        self.__ainvs = ainvs
161        if self.discriminant() == 0:
162            raise ArithmeticError, \
163                  "Invariants %s define a singular curve."%ainvs
164        PP = projective_space.ProjectiveSpace(2, K, names='xyz');
165        x, y, z = PP.coordinate_ring().gens()
166        a1, a2, a3, a4, a6 = ainvs
167        f = y**2*z + (a1*x + a3*z)*y*z \
168            - (x**3 + a2*x**2*z + a4*x*z**2 + a6*z**3)
169        plane_curve.ProjectiveCurve_generic.__init__(self, PP, f)
170        # TODO: cleanup, are these two point classes redundant?
171        if K.is_field():
172            if is_NumberField(K):
173                self._point_morphism_class = self._point_class = ell_point.EllipticCurvePoint_number_field
174            else:
175                self._point_morphism_class = self._point_class = ell_point.EllipticCurvePoint_field
176        else:
177            self._point_morphism_class = self._point_class = ell_point.EllipticCurvePoint
178
179    def _defining_params_(self):
180        r"""
181        Internal function. Returns a tuple of the base ring of this
182        elliptic curve and its a-invariants, from which it can be
183        reconstructed.
184
185        EXAMPLES::
186
187            sage: E=EllipticCurve(QQ,[1,1])
188            sage: E._defining_params_()
189            (Rational Field, [0, 0, 0, 1, 1])
190            sage: EllipticCurve(*E._defining_params_()) == E
191            True
192        """
193        return (self.__base_ring, self.__ainvs)
194
195    def _repr_(self):
196        """
197        String representation of elliptic curve.
198
199        EXAMPLES::
200
201            sage: E=EllipticCurve([1,2,3,4,5]); E._repr_()
202            'Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field'
203
204        ::
205
206            sage: R.<x> = QQ['x']
207            sage: K.<a> = NumberField(x^3-17)
208            sage: EllipticCurve([a^2-3, -2/3*a + 3])
209            Elliptic Curve defined by y^2  = x^3 + (a^2-3)*x + (-2/3*a+3) over Number Field in a
210            with defining polynomial x^3 - 17
211        """
212        #return "Elliptic Curve with a-invariants %s over %s"%(self.ainvs(), self.base_ring())
213        b = self.ainvs()
214        #return "y^2 + %s*x*y + %s*y = x^3 + %s*x^2 + %s*x + %s"%\
215        #       (a[0], a[2], a[1], a[3], a[4])
216        a = [z._coeff_repr() for z in b]
217        s = "Elliptic Curve defined by "
218        s += "y^2 "
219        if a[0] == "-1":
220            s += "- x*y "
221        elif a[0] == '1':
222            s += "+ x*y "
223        elif b[0]:
224            s += "+ %s*x*y "%a[0]
225        if a[2] == "-1":
226            s += "- y "
227        elif a[2] == '1':
228            s += "+ y "
229        elif b[2]:
230            s += "+ %s*y "%a[2]
231        s += "= x^3 "
232        if a[1] == "-1":
233            s += "- x^2 "
234        elif a[1] == '1':
235            s += "+ x^2 "
236        elif b[1]:
237            s += "+ %s*x^2 "%a[1]
238        if a[3] == "-1":
239            s += "- x "
240        elif a[3] == '1':
241            s += "+ x "
242        elif b[3]:
243            s += "+ %s*x "%a[3]
244        if a[4] == '-1':
245            s += "- 1 "
246        elif a[4] == '1':
247            s += "+ 1 "
248        elif b[4]:
249            s += "+ %s "%a[4]
250        s = s.replace("+ -","- ")
251        s += "over %s"%self.base_ring()
252        return s
253
254    def _latex_(self):
255        """
256        Internal function. Returns a latex string for this elliptic curve.
257        Users will normally use latex() instead.
258
259        EXAMPLES::
260
261            sage: E=EllipticCurve(QQ,[1,1])
262            sage: E._latex_()
263            'y^2 = x^3 + x + 1 '
264            sage: latex(E)
265            y^2 = x^3 + x + 1
266        """
267        b = self.ainvs()
268        a = [z._latex_coeff_repr() for z in b]
269        s = "y^2 "
270        if a[0] == '-1':
271            s += "- xy "
272        elif a[0] == '1':
273            s += "+ xy "
274        elif b[0]:
275            s += "+ %sxy "%a[0]
276        if a[2] == '-1':
277            s += "- y "
278        elif a[2] == '1':
279            s += "+ y "
280        elif b[2]:
281            s += "+ %sy "%a[2]
282        s += "= x^3 "
283        if a[1] == '-1':
284            s += "- x^2 "
285        elif a[1] == '1':
286            s += "+ x^2 "
287        elif b[1]:
288            s += "+ %sx^2 "%a[1]
289        if a[3] == '-1':
290            s += "- x "
291        elif a[3] == '1':
292            s += "+ x "
293        elif b[3]:
294            s += "+ %sx "%a[3]
295        if a[4] == '-1':
296            s += "- 1 "
297        elif a[4] == '1':
298            s += "+ 1 "
299        elif b[4]:
300            s += "+ %s "%a[4]
301        s = s.replace("+ -","- ")
302        return s
303
304    def _pari_init_(self):
305        """
306        Internal function. Returns a string to initialize this elliptic
307        curve in the pari system.
308
309        EXAMPLES::
310
311            sage: E=EllipticCurve(QQ,[1,1])
312            sage: E._pari_init_()
313            'ellinit([0/1,0/1,0/1,1/1,1/1])'
314        """
315        return 'ellinit([%s])'%(','.join([x._pari_init_() for x in self.ainvs()]))
316
317    def _magma_init_(self, magma):
318        """
319        Internal function. Returns a string to initialize this elliptic
320        curve in the Magma subsystem.
321
322        EXAMPLES::
323
324            sage: E = EllipticCurve(QQ,[1,1])
325            sage: E._magma_init_(magma)                          # optional - magma
326            'EllipticCurve([_sage_ref...|0,0,0,1,1])'
327            sage: E =  EllipticCurve(GF(41),[2,5])               # optional - magma
328            sage: E._magma_init_(magma)                          # optional - magma
329            'EllipticCurve([_sage_ref...|GF(41)!0,GF(41)!0,GF(41)!0,GF(41)!2,GF(41)!5])'
330            sage: E = EllipticCurve(GF(25,'a'), [0,0,1,4,0])
331            sage: magma(E)                                       # optional - magma
332            Elliptic Curve defined by y^2 + y = x^3 + 4*x over GF(5^2)
333            sage: magma(EllipticCurve([1/2,2/3,-4/5,6/7,8/9]))   # optional - magma
334            Elliptic Curve defined by y^2 + 1/2*x*y - 4/5*y = x^3 + 2/3*x^2 + 6/7*x + 8/9 over Rational Field
335            sage: R.<x> = Frac(QQ['x'])
336            sage: magma(EllipticCurve([x,1+x]))                  # optional - magma
337            Elliptic Curve defined by y^2 = x^3 + x*x + (x + 1) over Univariate rational function field over Rational Field
338        """
339        kmn = magma(self.base_ring())._ref()
340        return 'EllipticCurve([%s|%s])'%(kmn,','.join([x._magma_init_(magma) for x in self.ainvs()]))
341
342
343    def _symbolic_(self, SR):
344        r"""
345        Many elliptic curves can be converted into a symbolic expression
346        using the symbolic_expression command.
347
348        EXAMPLES: We find a torsion point on 11a.
349
350        ::
351
352            sage: E = EllipticCurve('11a')
353            sage: E._symbolic_(SR)
354            y^2 + y == x^3 - x^2 - 10*x - 20
355            sage: E.torsion_subgroup().gens()
356            ((5 : 5 : 1),)
357
358        We find the corresponding symbolic equality::
359
360            sage: eqn = symbolic_expression(E); eqn
361            y^2 + y == x^3 - x^2 - 10*x - 20
362
363        We verify that the given point is on the curve::
364
365            sage: eqn(x=5,y=5)
366            30 == 30
367            sage: bool(eqn(x=5,y=5))
368            True
369
370        We create a single expression::
371
372            sage: F = eqn.lhs() - eqn.rhs(); F
373            -x^3 + x^2 + y^2 + 10*x + y + 20
374            sage: y = var('y')
375            sage: F.solve(y)
376            [y == -1/2*sqrt(4*x^3 - 4*x^2 - 40*x - 79) - 1/2,
377             y == 1/2*sqrt(4*x^3 - 4*x^2 - 40*x - 79) - 1/2]
378
379        You can also solve for x in terms of y, but the result is
380        horrendous. Continuing with the above example, we can explicitly
381        find points over random fields by substituting in values for x::
382
383            sage: v = F.solve(y)[0].rhs(); v
384            -1/2*sqrt(4*x^3 - 4*x^2 - 40*x - 79) - 1/2
385            sage: v = v.function(x)
386            sage: v(3)
387            -1/2*sqrt(-127) - 1/2
388            sage: v(7)
389            -1/2*sqrt(817) - 1/2
390            sage: v(-7)
391            -1/2*sqrt(-1367) - 1/2
392            sage: v(sqrt(2))
393            -1/2*sqrt(-32*sqrt(2) - 87) - 1/2
394
395        We can even do arithmetic with them, as follows::
396
397            sage: E2 = E.change_ring(SR); E2
398            Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Symbolic Ring
399            sage: P = E2.point((3, v(3), 1), check=False) # the check=False option doesn't verify that y^2 = f(x)
400            sage: P
401            (3 : -1/2*sqrt(-127) - 1/2 : 1)
402            sage: P + P
403            (-756/127 : 41143/32258*sqrt(-127) - 1/2 : 1)
404
405        We can even throw in a transcendental::
406
407            sage: w = E2.point((pi,v(pi),1), check=False); w
408            (pi : -1/2*sqrt(-40*pi + 4*pi^3 - 4*pi^2 - 79) - 1/2 : 1)
409            sage: x, y, z = w; ((y^2 + y) - (x^3 - x^2 - 10*x - 20)).expand()
410            0
411
412            sage: 2*w
413            (-2*pi + (2*pi - 3*pi^2 + 10)^2/(-40*pi + 4*pi^3 - 4*pi^2 - 79) + 1 : (2*pi - 3*pi^2 + 10)*(3*pi - (2*pi - 3*pi^2 + 10)^2/(-40*pi + 4*pi^3 - 4*pi^2 - 79) - 1)/sqrt(-40*pi + 4*pi^3 - 4*pi^2 - 79) + 1/2*sqrt(-40*pi + 4*pi^3 - 4*pi^2 - 79) - 1/2 : 1)
414
415            sage: x, y, z = 2*w; temp = ((y^2 + y) - (x^3 - x^2 - 10*x - 20))
416
417        This is a point on the curve::
418
419            sage: bool(temp == 0)
420            True
421        """
422        a = [SR(x) for x in self.a_invariants()]
423        x, y = SR.var('x, y')
424        return y**2 + a[0]*x*y + a[2]*y == x**3 + a[1]*x**2 + a[3]*x + a[4]
425
426    def __cmp__(self, other):
427        """
428        Standard comparison function for elliptic curves, to allow sorting
429        and equality testing.
430
431        EXAMPLES::
432
433            sage: E=EllipticCurve(QQ,[1,1])
434            sage: F=EllipticCurve(QQ,[0,0,0,1,1])
435            sage: E==F
436            True
437        """
438        if not isinstance(other, EllipticCurve_generic):
439            return -1
440        t = cmp(self.base_ring(), other.base_ring())
441        if t:
442            return t
443        return cmp(self.ainvs(), other.ainvs())
444
445    def __contains__(self, P):
446        """
447        Returns True if and only if P is a point on the elliptic curve. P
448        just has to be something that can be coerced to a point.
449
450        EXAMPLES::
451
452            sage: E = EllipticCurve([0, 0, 1, -1, 0])
453            sage: (0,0) in E
454            True
455            sage: (1,3) in E
456            False
457            sage: E = EllipticCurve([GF(7)(0), 1])
458            sage: [0,0] in E
459            False
460            sage: [0,8] in E
461            True
462            sage: P = E(0,8)
463            sage: P
464            (0 : 1 : 1)
465            sage: P in E
466            True
467        """
468        if not isinstance(P, ell_point.EllipticCurvePoint):
469            try:
470                P = self(P)
471            except TypeError:
472                return False
473        if P.curve() == self:
474            return True
475        x, y, a = P[0], P[1], self.ainvs()
476        return y**2 + a[0]*x*y + a[2]*y == x**3 + a[1]*x**2 + a[3]*x + a[4]
477
478    def __call__(self, *args, **kwds):
479        """
480        EXAMPLES::
481
482            sage: E = EllipticCurve([0, 0, 1, -1, 0])
483
484        The point at infinity, which is the 0 element of the group::
485
486            sage: E(0)
487            (0 : 1 : 0)
488
489        The origin is a point on our curve::
490
491            sage: P = E([0,0])
492            sage: P
493            (0 : 0 : 1)
494
495        The curve associated to a point::
496
497            sage: P.curve()
498            Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
499
500        Points can be specified by given a 2-tuple or 3-tuple
501
502        ::
503
504            sage: E([0,0])
505            (0 : 0 : 1)
506            sage: E([0,1,0])
507            (0 : 1 : 0)
508
509        Over a field, points are normalized so the 3rd entry (if non-zero)
510        is 1::
511
512            sage: E(105, -69, 125)
513            (21/25 : -69/125 : 1)
514
515        We create points on an elliptic curve over a prime finite field.
516
517        ::
518
519            sage: E = EllipticCurve([GF(7)(0), 1])
520            sage: E([2,3])
521            (2 : 3 : 1)
522            sage: E([0,0])
523            Traceback (most recent call last):
524            ...
525            TypeError: Coordinates [0, 0, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7
526
527        We create a point on an elliptic curve over a number field.
528
529        ::
530
531            sage: x = polygen(RationalField())
532            sage: K = NumberField(x**3 + x + 1, 'a'); a = K.gen()
533            sage: E = EllipticCurve([a,a])
534            sage: E
535            Elliptic Curve defined by y^2  = x^3 + a*x + a over Number Field in a with defining polynomial x^3 + x + 1
536            sage: E = EllipticCurve([K(1),1])
537            sage: E
538            Elliptic Curve defined by y^2 = x^3 + x + 1 over Number Field in a with defining polynomial x^3 + x + 1
539            sage: P = E([a,0,1])
540            sage: P
541            (a : 0 : 1)
542            sage: P+P
543            (0 : 1 : 0)
544
545        Another example involving p-adics::
546
547            sage: E = EllipticCurve('37a1')
548            sage: P = E([0,0]); P
549            (0 : 0 : 1)
550            sage: R = pAdicField(3,20)
551            sage: Ep = E.base_extend(R); Ep
552            Elliptic Curve defined by y^2 + (1+O(3^20))*y = x^3 + (2+2*3+2*3^2+2*3^3+2*3^4+2*3^5+2*3^6+2*3^7+2*3^8+2*3^9+2*3^10+2*3^11+2*3^12+2*3^13+2*3^14+2*3^15+2*3^16+2*3^17+2*3^18+2*3^19+O(3^20))*x over 3-adic Field with capped relative precision 20
553            sage: Ep(P)
554            (0 : 0 : 1 + O(3^20))
555
556        Constructing points from the torsion subgroup (which is an abstract
557        abelian group)::
558
559            sage: E = EllipticCurve('14a1')
560            sage: T = E.torsion_subgroup()
561            sage: [E(t) for t in T]
562            [(0 : 1 : 0),
563            (9 : 23 : 1),
564            (2 : 2 : 1),
565            (1 : -1 : 1),
566            (2 : -5 : 1),
567            (9 : -33 : 1)]
568
569        ::
570
571            sage: E = EllipticCurve([0,0,0,-49,0])
572            sage: T = E.torsion_subgroup()
573            sage: [E(t) for t in T]
574            [(0 : 1 : 0), (0 : 0 : 1), (7 : 0 : 1), (-7 : 0 : 1)]
575
576        ::
577
578            sage: E = EllipticCurve('37a1')
579            sage: T = E.torsion_subgroup()
580            sage: [E(t) for t in T]
581            [(0 : 1 : 0)]
582        """
583        if len(args) == 1 and args[0] == 0:
584            R = self.base_ring()
585            return self.point([R(0),R(1),R(0)], check=False)
586        P = args[0]
587        if isinstance(P,groups.abelian_group_element.AbelianGroupElement) and isinstance(P.parent(),ell_torsion.EllipticCurveTorsionSubgroup):
588            T = P.parent()
589            return sum([zi*Ti for zi,Ti in zip(P.list(),T.gens())],T.curve()(0))
590        if isinstance(args[0],
591              (ell_point.EllipticCurvePoint_field, \
592               ell_point.EllipticCurvePoint_number_field, \
593               ell_point.EllipticCurvePoint)):
594            # check if denominator of the point contains a factor of the
595            # characteristic of the base ring. if so, coerce the point to
596            # infinity.
597            characteristic = self.base_ring().characteristic()
598            if characteristic != 0 and isinstance(args[0][0], rings.Rational) and isinstance(args[0][1], rings.Rational):
599                if rings.mod(args[0][0].denominator(),characteristic) == 0 or rings.mod(args[0][1].denominator(),characteristic) == 0:
600                    args = self._reduce_point(args[0], characteristic)
601                    args = tuple(args)
602            else:
603                args = tuple(args[0])
604
605        return plane_curve.ProjectiveCurve_generic.__call__(self, *args, **kwds)
606
607    def _reduce_point(self, R, p):
608        r"""
609        Reduces a point R on an ellipitc curve to the corresponding point on
610        the elliptic curve reduced modulo p. Used to coerce points between
611        curves when p is a factor of the denominator of one of the
612        coordinates.
613
614        This functionality is used internally in the \code{call} method for
615        elliptic curves.
616
617        INPUT:
618            R -- a point on an elliptic curve
619            p -- a prime
620
621        OUTPUT:
622            S -- the corresponding point of the elliptic curve containing R, but
623                 reduced modulo p
624
625        EXAMPLES:
626        Suppose we have a point with large height on a rational elliptic curve
627        whose denominator contains a factor of 11:
628            sage: E = EllipticCurve([1,-1,0,94,9])
629            sage: R = E([0,3]) + 5*E([8,31])
630            sage: factor(R.xy()[0].denominator())
631            2^2 * 11^2 * 1457253032371^2
632
633        Since 11 is a factor of the denominator, this point corresponds to the
634        point at infinity on the same curve but reduced modulo 11. The reduce
635        function tells us this:
636            sage: E11 = E.change_ring(GF(11))
637            sage: S = E11._reduce_point(R, 11)
638            sage: E11(S)
639            (0 : 1 : 0)
640
641        The 0 point reduces as expected:
642            sage: E11._reduce_point(E(0), 11)
643            (0 : 1 : 0)
644
645        Note that one need not explicitly call
646        \code{EllipticCurve._reduce_point}
647        """
648        if R.is_zero():
649            return R.curve().change_ring(rings.GF(p))(0)
650        x, y = R.xy()
651        d = arith.LCM(x.denominator(), y.denominator())
652        return R.curve().change_ring(rings.GF(p))([x*d, y*d, d])
653
654    def is_x_coord(self, x):
655        """
656        Returns True if x is the x-coordinate of a point on this curve.
657
658        .. note::
659
660           See also lift_x() to find the point(s) with a given
661           x-coordinate.  This function may be useful in cases where
662           testing an element of the base field for being a square is
663           faster than finding its square root.
664
665        EXAMPLES::
666
667            sage: E = EllipticCurve('37a'); E
668            Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
669            sage: E.is_x_coord(1)
670            True
671            sage: E.is_x_coord(2)
672            True
673
674        There are no rational points with x-coordinate 3::
675
676            sage: E.is_x_coord(3)
677            False
678
679        However, there are such points in E(\RR)::
680
681            sage: E.change_ring(RR).is_x_coord(3)
682            True
683
684        And of course it always works in E(\CC)::
685
686            sage: E.change_ring(RR).is_x_coord(-3)
687            False
688            sage: E.change_ring(CC).is_x_coord(-3)
689            True
690
691        AUTHORS:
692
693        - John Cremona (2008-08-07): adapted from lift_x()
694
695        TEST::
696
697            sage: E=EllipticCurve('5077a1')
698            sage: [x for x in srange(-10,10) if E.is_x_coord (x)]
699            [-3, -2, -1, 0, 1, 2, 3, 4, 8]
700
701        ::
702
703            sage: F=GF(32,'a')
704            sage: E=EllipticCurve(F,[1,0,0,0,1])
705            sage: set([P[0] for P in E.points() if P!=E(0)]) == set([x for x in F if E.is_x_coord(x)])
706            True
707        """
708        K = self.base_ring()
709        try:
710            x = K(x)
711        except TypeError:
712            raise TypeError, 'x must be coercible into the base ring of the curve'
713        a1, a2, a3, a4, a6 = self.ainvs()
714        fx = ((x + a2) * x + a4) * x + a6
715        if a1.is_zero() and a3.is_zero():
716            return fx.is_square()
717        b = (a1*x + a3)
718        if K.characteristic() == 2:
719            R = PolynomialRing(K, 'y')
720            F = R([-fx,b,1])
721            return len(F.roots())>0
722        D = b*b + 4*fx
723        return D.is_square()
724
725    def lift_x(self, x, all=False):
726        r"""
727        Returns one or all points with given x-coordinate.
728
729        INPUT:
730
731        - x -- an element of the base ring of the curve.
732
733        - all (bool, default False) -- if True, return a (possibly
734          empty) list of all points; if False, return just one point,
735          or raise a ValueError if there are none.
736
737        .. note::
738
739           See also is_x_coord().
740
741        EXAMPLES::
742
743            sage: E = EllipticCurve('37a'); E
744            Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
745            sage: E.lift_x(1)
746            (1 : 0 : 1)
747            sage: E.lift_x(2)
748            (2 : 2 : 1)
749            sage: E.lift_x(1/4, all=True)
750            [(1/4 : -3/8 : 1), (1/4 : -5/8 : 1)]
751
752        There are no rational points with x-coordinate 3::
753
754            sage: E.lift_x(3)
755            Traceback (most recent call last):
756            ...
757            ValueError: No point with x-coordinate 3 on Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
758
759        However, there are two such points in E(\RR)::
760
761            sage: E.change_ring(RR).lift_x(3, all=True)
762            [(3.00000000000000 : 4.42442890089805 : 1.00000000000000), (3.00000000000000 : -5.42442890089805 : 1.00000000000000)]
763
764        And of course it always works in E(\CC)::
765
766            sage: E.change_ring(RR).lift_x(.5, all=True)
767            []
768            sage: E.change_ring(CC).lift_x(.5)
769            (0.500000000000000 : -0.500000000000000 + 0.353553390593274*I : 1.00000000000000)
770
771        We can perform these operations over finite fields too::
772
773            sage: E = E.change_ring(GF(17)); E
774            Elliptic Curve defined by y^2 + y = x^3 + 16*x over Finite Field of size 17
775            sage: E.lift_x(7)
776            (7 : 11 : 1)
777            sage: E.lift_x(3)
778            Traceback (most recent call last):
779            ...
780            ValueError: No point with x-coordinate 3 on Elliptic Curve defined by y^2 + y = x^3 + 16*x over Finite Field of size 17
781
782        Note that there is only one lift with x-coordinate 10 in
783        E(\GF{17})::
784
785            sage: E.lift_x(10, all=True)
786            [(10 : 8 : 1)]
787
788        We can lift over more exotic rings too::
789
790            sage: E = EllipticCurve('37a');
791            sage: E.lift_x(pAdicField(17, 5)(6))
792            (6 + O(17^5) : 2 + 16*17 + 16*17^2 + 16*17^3 + 16*17^4 + O(17^5) : 1 + O(17^5))
793            sage: K.<t> = PowerSeriesRing(QQ, 't', 5)
794            sage: E.lift_x(1+t)
795            (1 + t : 2*t - t^2 + 5*t^3 - 21*t^4 + O(t^5) : 1)
796            sage: K.<a> = GF(16)
797            sage: E = E.change_ring(K)
798            sage: E.lift_x(a^3)
799            (a^3 : a^3 + a : 1)
800
801        AUTHOR:
802
803        - Robert Bradshaw (2007-04-24)
804
805        TEST::
806
807            sage: E = EllipticCurve('37a').short_weierstrass_model().change_ring(GF(17))
808            sage: E.lift_x(3, all=True)
809            []
810            sage: E.lift_x(7, all=True)
811            [(7 : 3 : 1), (7 : 14 : 1)]
812        """
813        a1, a2, a3, a4, a6 = self.ainvs()
814        f = ((x + a2) * x + a4) * x + a6
815        K = self.base_ring()
816        x += K(0)
817        one = x.parent()(1)
818        if a1.is_zero() and a3.is_zero():
819            if f.is_square():
820                if all:
821                    ys = f.sqrt(all=True)
822                    return [self.point([x, y, one], check=False) for y in ys]
823                else:
824                    return self.point([x, f.sqrt(), one], check=False)
825        else:
826            b = (a1*x + a3)
827            D = b*b + 4*f
828            if K.characteristic() == 2:
829                R = PolynomialRing(K, 'y')
830                F = R([-f,b,1])
831                ys = F.roots(multiplicities=False)
832                if all:
833                    return [self.point([x, y, one], check=False) for y in ys]
834                elif len(ys) > 0:
835                    return self.point([x, ys[0], one], check=False)
836            elif D.is_square():
837                if all:
838                    return [self.point([x, (-b+d)/2, one], check=False) for d in D.sqrt(all=True)]
839                else:
840                    return self.point([x, (-b+D.sqrt())/2, one], check=False)
841        if all:
842            return []
843        else:
844            raise ValueError, "No point with x-coordinate %s on %s"%(x, self)
845
846    def _homset_class(self, *args, **kwds):
847        """
848        Internal function. Returns the (abstract) group of points on this
849        elliptic curve over a ring.
850
851        EXAMPLES::
852
853            sage: E=EllipticCurve(GF(5),[1,1])
854            sage: E._homset_class(GF(5^10,'a'),GF(5))
855            Abelian group of points on Finite Field in a of size 5^10
856        """
857        return homset.SchemeHomsetModule_abelian_variety_coordinates_field(*args, **kwds)
858
859    def __getitem__(self, n):
860        """
861        Placeholder for standard indexing function.
862
863        EXAMPLES::
864
865            sage: E=EllipticCurve(QQ,[1,1])
866            sage: E[2]
867            Traceback (most recent call last):
868            ...
869            NotImplementedError: not implemented.
870        """
871        raise NotImplementedError, "not implemented."
872
873    def __is_over_RationalField(self):
874        """
875        Internal function. Returns true iff the base ring of this elliptic
876        curve is the field of rational numbers.
877
878        EXAMPLES::
879
880            sage: E=EllipticCurve(QQ,[1,1])
881            sage: E._EllipticCurve_generic__is_over_RationalField()
882            True
883            sage: E=EllipticCurve(GF(5),[1,1])
884            sage: E._EllipticCurve_generic__is_over_RationalField()
885            False
886        """
887        return isinstance(self.base_ring(), rings.RationalField)
888
889    def is_on_curve(self, x, y):
890        """
891        Returns True if (x,y) is an affine point on this curve.
892
893        INPUT:
894
895        - x, y - elements of the base ring of the curve.
896
897        EXAMPLES::
898
899            sage: E=EllipticCurve(QQ,[1,1])
900            sage: E.is_on_curve(0,1)
901            True
902            sage: E.is_on_curve(1,1)
903            False
904        """
905        a = self.ainvs()
906        return y**2 +a[0]*x*y + a[2]*y == x**3 + a[1]*x**2 + a[3]*x + a[4]
907
908    def a_invariants(self):
909        """
910        The a-invariants of this elliptic curve, as a list.
911
912        OUTPUT:
913
914        (list) - a (new) list of the 5 a-invariants.
915
916        EXAMPLES::
917
918            sage: E = EllipticCurve([1,2,3,4,5])
919            sage: E.a_invariants()
920            [1, 2, 3, 4, 5]
921            sage: E = EllipticCurve([0,1])
922            sage: E
923            Elliptic Curve defined by y^2 = x^3 + 1 over Rational Field
924            sage: E.a_invariants()
925            [0, 0, 0, 0, 1]
926            sage: E = EllipticCurve([GF(7)(3),5])
927            sage: E.a_invariants()
928            [0, 0, 0, 3, 5]
929
930        We check that a new list is returned::
931
932            sage: E = EllipticCurve([1,0,0,0,1])
933            sage: E.a_invariants()[0] = 100000000
934            sage: E
935            Elliptic Curve defined by y^2 + x*y = x^3 + 1 over Rational Field
936        """
937        return list(self.__ainvs)
938
939    ainvs = a_invariants
940
941    def a1(self):
942        r"""
943        Returns the a_1 invariant of this elliptic curve.
944
945        EXAMPLES::
946
947            sage: E = EllipticCurve([1,2,3,4,6])
948            sage: E.a1()
949            1
950        """
951        return self.__ainvs[0]
952
953    def a2(self):
954        r"""
955        Returns the a_2 invariant of this elliptic curve.
956
957        EXAMPLES::
958
959            sage: E = EllipticCurve([1,2,3,4,6])
960            sage: E.a2()
961            2
962        """
963        return self.__ainvs[1]
964
965    def a3(self):
966        r"""
967        Returns the a_3 invariant of this elliptic curve.
968
969        EXAMPLES::
970
971            sage: E = EllipticCurve([1,2,3,4,6])
972            sage: E.a3()
973            3
974        """
975        return self.__ainvs[2]
976
977    def a4(self):
978        r"""
979        Returns the a_4 invariant of this elliptic curve.
980
981        EXAMPLES::
982
983            sage: E = EllipticCurve([1,2,3,4,6])
984            sage: E.a4()
985            4
986        """
987        return self.__ainvs[3]
988
989    def a6(self):
990        r"""
991        Returns the a_6 invariant of this elliptic curve.
992
993        EXAMPLES::
994
995            sage: E = EllipticCurve([1,2,3,4,6])
996            sage: E.a6()
997            6
998        """
999        return self.__ainvs[4]
1000
1001    def b_invariants(self):
1002        """
1003        Returns the b-invariants of this elliptic curve, as a tuple.
1004
1005        OUTPUT:
1006
1007        (tuple) - a 4-tuple of the b-invariants of this elliptic curve.
1008
1009        EXAMPLES::
1010
1011            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1012            sage: E.b_invariants()
1013            (-4, -20, -79, -21)
1014            sage: E = EllipticCurve([-4,0])
1015            sage: E.b_invariants()
1016            (0, -8, 0, -16)
1017
1018        ::
1019
1020            sage: E = EllipticCurve([1,2,3,4,5])
1021            sage: E.b_invariants()
1022            (9, 11, 29, 35)
1023            sage: E.b2()
1024            9
1025            sage: E.b4()
1026            11
1027            sage: E.b6()
1028            29
1029            sage: E.b8()
1030            35
1031
1032        ALGORITHM:
1033
1034        These are simple functions of the a-invariants.
1035
1036        AUTHORS:
1037
1038        - William Stein (2005-04-25)
1039        """
1040        try:
1041            return self.__b_invariants
1042        except AttributeError:
1043            a1,a2,a3,a4,a6 = tuple(self.ainvs())
1044            self.__b_invariants = a1*a1 + 4*a2, \
1045                                  a1*a3 + 2*a4, \
1046                                  a3**2 + 4*a6, \
1047                                  a1**2 * a6 + 4*a2*a6 - a1*a3*a4 + a2*a3**2 - a4**2
1048            return self.__b_invariants
1049
1050    def b2(self):
1051        r"""
1052        Returns the b_2 invariant of this elliptic curve.
1053
1054        EXAMPLES::
1055
1056            sage: E = EllipticCurve([1,2,3,4,5])
1057            sage: E.b2()
1058            9
1059        """
1060        try:
1061            return self.__b_invariants[0]
1062        except AttributeError:
1063            return self.b_invariants()[0]
1064
1065    def b4(self):
1066        r"""
1067        Returns the b_4 invariant of this elliptic curve.
1068
1069        EXAMPLES::
1070
1071            sage: E = EllipticCurve([1,2,3,4,5])
1072            sage: E.b4()
1073            11
1074        """
1075        try:
1076            return self.__b_invariants[1]
1077        except AttributeError:
1078            return self.b_invariants()[1]
1079
1080    def b6(self):
1081        r"""
1082        Returns the b_6 invariant of this elliptic curve.
1083
1084        EXAMPLES::
1085
1086            sage: E = EllipticCurve([1,2,3,4,5])
1087            sage: E.b6()
1088            29
1089        """
1090        try:
1091            return self.__b_invariants[2]
1092        except AttributeError:
1093            return self.b_invariants()[2]
1094
1095    def b8(self):
1096        r"""
1097        Returns the b_8 invariant of this elliptic curve.
1098
1099        EXAMPLES::
1100
1101            sage: E = EllipticCurve([1,2,3,4,5])
1102            sage: E.b8()
1103            35
1104        """
1105        try:
1106            return self.__b_invariants[3]
1107        except AttributeError:
1108            return self.b_invariants()[3]
1109
1110    def c_invariants(self):
1111        r"""
1112        Returns the c-invariants of this elliptic curve, as a tuple.
1113
1114        OUTPUT:
1115
1116        (tuple) - a 2-tuple of the c-invariants of the elliptic curve.
1117
1118        EXAMPLES::
1119
1120            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1121            sage: E.c_invariants()
1122            (496, 20008)
1123            sage: E = EllipticCurve([-4,0])
1124            sage: E.c_invariants()
1125            (192, 0)
1126
1127        ALGORITHM:
1128
1129        These are simple functions of the a-invariants.
1130
1131        AUTHORS:
1132
1133        - William Stein (2005-04-25)
1134        """
1135        try:
1136            return self.__c_invariants
1137        except AttributeError:
1138            b2,b4,b6,b8 = self.b_invariants()
1139            self.__c_invariants = b2**2 - 24*b4,\
1140                                  -b2**3 + 36*b2*b4 - 216*b6    # note: c6 is wrong in Silverman, but right in Cremona
1141            return self.__c_invariants
1142
1143    def c4(self):
1144        r"""
1145        Returns the c_4 invariant of this elliptic curve.
1146
1147        EXAMPLES::
1148
1149            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1150            sage: E.c4()
1151            496
1152        """
1153        try:
1154            return self.__c_invariants[0]
1155        except AttributeError:
1156            pass
1157        return self.c_invariants()[0]
1158
1159    def c6(self):
1160        r"""
1161        Returns the c_6 invariant of this elliptic curve.
1162
1163        EXAMPLES::
1164
1165            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1166            sage: E.c6()
1167            20008
1168        """
1169        try:
1170            return self.__c_invariants[1]
1171        except AttributeError:
1172            pass
1173        return self.c_invariants()[1]
1174
1175    def discriminant(self):
1176        """
1177        Returns the discriminant of this elliptic curve.
1178
1179        EXAMPLES::
1180
1181            sage: E = EllipticCurve([0,0,1,-1,0])
1182            sage: E.discriminant()
1183            37
1184            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1185            sage: E.discriminant()
1186            -161051
1187
1188        ::
1189
1190            sage: E = EllipticCurve([GF(7)(2),1])
1191            sage: E.discriminant()
1192            1
1193        """
1194        try:
1195            return self.__discriminant
1196        except AttributeError:
1197            b2, b4, b6, b8 = self.b_invariants()
1198            self.__discriminant = -b2**2*b8 - 8*b4**3 - 27*b6**2 + 9*b2*b4*b6
1199            return self.__discriminant
1200
1201    def j_invariant(self):
1202        r"""
1203        Returns the j-invariant of this elliptic curve.
1204
1205        EXAMPLES::
1206
1207            sage: E = EllipticCurve([0,0,1,-1,0])
1208            sage: E.j_invariant()
1209            110592/37
1210            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1211            sage: E.j_invariant()
1212            -122023936/161051
1213            sage: E = EllipticCurve([-4,0])
1214            sage: E.j_invariant()
1215            1728
1216
1217        ::
1218
1219            sage: E = EllipticCurve([GF(7)(2),1])
1220            sage: E.j_invariant()
1221            1
1222        """
1223        try:
1224            return self.__j_invariant
1225        except AttributeError:
1226            c4, _ = self.c_invariants()
1227            self.__j_invariant = c4**3 / self.discriminant()
1228            return self.__j_invariant
1229
1230
1231    def base_extend(self, R):
1232        r"""
1233        Returns a new curve with the same a-invariants but defined over a new ring.
1234
1235        INPUT:
1236
1237        - R -- either a ring into which the curve's a-invariants
1238          may be coerced, or a morphism which may be applied to them.
1239
1240        OUTPUT:
1241
1242        A new elliptic curve with the same a-invariants, defined over the new ring.
1243
1244        EXAMPLES::
1245
1246            sage: E=EllipticCurve(GF(5),[1,1]); E
1247            Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5
1248            sage: E1=E.base_extend(GF(125,'a')); E1
1249            Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in a of size 5^3
1250            sage: F2=GF(5^2,'a'); a=F2.gen()
1251            sage: F4=GF(5^4,'b'); b=F4.gen()
1252            sage: h=F2.hom([a.charpoly().roots(ring=F4,multiplicities=False)[0]],F4)
1253            sage: E=EllipticCurve(F2,[1,a]); E
1254            Elliptic Curve defined by y^2 = x^3 + x + a over Finite Field in a of size 5^2
1255            sage: E.base_extend(h)
1256            Elliptic Curve defined by y^2 = x^3 + x + (4*b^3+4*b^2+4*b+3) over Finite Field in b of size 5^4
1257        """
1258        return constructor.EllipticCurve([R(a) for a in self.a_invariants()])
1259
1260    change_ring = base_extend
1261
1262    def base_ring(self):
1263        """
1264        Returns the base ring of the elliptic curve.
1265
1266        EXAMPLES::
1267
1268            sage: E = EllipticCurve(GF(49, 'a'), [3,5])
1269            sage: E.base_ring()
1270            Finite Field in a of size 7^2
1271
1272        ::
1273
1274            sage: E = EllipticCurve([1,1])
1275            sage: E.base_ring()
1276            Rational Field
1277
1278        ::
1279
1280            sage: E = EllipticCurve(ZZ, [3,5])
1281            sage: E.base_ring()
1282            Integer Ring
1283        """
1284        return self.__base_ring
1285
1286    def gens(self):
1287        """
1288        Placeholder function to return generators of an elliptic curve.
1289
1290        .. note::
1291
1292           This functionality is implemented in certain derived
1293           classes, such as EllipticCurve_rational_field.
1294
1295        EXAMPLES::
1296
1297            sage: R.<a1,a2,a3,a4,a6>=QQ[]
1298            sage: E=EllipticCurve([a1,a2,a3,a4,a6])
1299            sage: E.gens()
1300            Traceback (most recent call last):
1301            ...
1302            NotImplementedError: not implemented.
1303            sage: E=EllipticCurve(QQ,[1,1])
1304            sage: E.gens()
1305            [(0 : 1 : 1)]
1306        """
1307        raise NotImplementedError, "not implemented."
1308
1309    def gen(self, i):
1310        """
1311        Function returning the i'th generator of this elliptic curve.
1312
1313        .. note::
1314
1315           Relies on gens() being implemented.
1316
1317        EXAMPLES::
1318
1319            sage: R.<a1,a2,a3,a4,a6>=QQ[]
1320            sage: E=EllipticCurve([a1,a2,a3,a4,a6])
1321            sage: E.gen(0)
1322            Traceback (most recent call last):
1323            ...
1324            NotImplementedError: not implemented.
1325        """
1326        return self.gens()[i]
1327
1328    def rst_transform(self, r, s, t):
1329        r"""
1330        Returns the transform of the curve by (r,s,t) (with u=1).
1331
1332        INPUT:
1333
1334        - r, s, t -- three elements of the base ring.
1335
1336        OUTPUT:
1337
1338        The elliptic curve obtained from self by the standard
1339        Weierstrass transformation (u,r,s,t) with u=1.
1340
1341        .. note::
1342
1343           This is just a special case of change_weierstrass_model(), with u=1.
1344
1345        EXAMPLES::
1346
1347            sage: R.<r,s,t>=QQ[]
1348            sage: E=EllipticCurve([1,2,3,4,5])
1349            sage: E.rst_transform(r,s,t)
1350            Elliptic Curve defined by y^2 + (2*s+1)*x*y + (r+2*t+3)*y = x^3 + (-s^2+3*r-s+2)*x^2 + (3*r^2-r*s-2*s*t+4*r-3*s-t+4)*x + (r^3+2*r^2-r*t-t^2+4*r-3*t+5) over Multivariate Polynomial Ring in r, s, t over Rational Field
1351        """
1352        return self.change_weierstrass_model(1,r,s,t)
1353
1354    def scale_curve(self, u):
1355        r"""
1356        Returns the transform of the curve by scale factor u.
1357
1358        INPUT:
1359
1360        - u -- an invertible element of the base ring.
1361
1362        OUTPUT:
1363
1364        The elliptic curve obtained from self by the standard
1365        Weierstrass transformation (u,r,s,t) with r=s=t=0.
1366
1367        .. note::
1368
1369           This is just a special case of change_weierstrass_model(), with r=s=t=0.
1370
1371       EXAMPLES::
1372
1373            sage: K=Frac(PolynomialRing(QQ,'u'))
1374            sage: u=K.gen()
1375            sage: E=EllipticCurve([1,2,3,4,5])
1376            sage: E.scale_curve(u)
1377            Elliptic Curve defined by y^2 + u*x*y + 3*u^3*y = x^3 + 2*u^2*x^2 + 4*u^4*x + 5*u^6 over Fraction Field of Univariate Polynomial Ring in u over Rational Field
1378        """
1379        if isinstance(u, (int,long)):
1380            u=self.base_ring()(u)       # because otherwise 1/u would round!
1381        return self.change_weierstrass_model(1/u,0,0,0)
1382
1383    def discriminant(self):
1384        """
1385        Returns the discriminant of this elliptic curve.
1386
1387        EXAMPLES::
1388
1389            sage: E = EllipticCurve([0,0,1,-1,0])
1390            sage: E.discriminant()
1391            37
1392            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1393            sage: E.discriminant()
1394            -161051
1395
1396        ::
1397
1398            sage: E = EllipticCurve([GF(7)(2),1])
1399            sage: E.discriminant()
1400            1
1401        """
1402        try:
1403            return self.__discriminant
1404        except AttributeError:
1405            b2, b4, b6, b8 = self.b_invariants()
1406            self.__discriminant = -b2**2*b8 - 8*b4**3 - 27*b6**2 + 9*b2*b4*b6
1407            return self.__discriminant
1408
1409    def j_invariant(self):
1410        """
1411        Returns the j-invariant of this elliptic curve.
1412
1413        EXAMPLES::
1414
1415            sage: E = EllipticCurve([0,0,1,-1,0])
1416            sage: E.j_invariant()
1417            110592/37
1418            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1419            sage: E.j_invariant()
1420            -122023936/161051
1421            sage: E = EllipticCurve([-4,0])
1422            sage: E.j_invariant()
1423            1728
1424
1425        ::
1426
1427            sage: E = EllipticCurve([GF(7)(2),1])
1428            sage: E.j_invariant()
1429            1
1430        """
1431        try:
1432            return self.__j_invariant
1433        except AttributeError:
1434            c4, _ = self.c_invariants()
1435            self.__j_invariant = c4**3 / self.discriminant()
1436            return self.__j_invariant
1437
1438#############################################################
1439#
1440# Explanation of the division (also known as torsion) polynomial
1441# functions in Sage.
1442#
1443# The main user function division_polynomial() (also aliased as
1444# torsion_polynomial()) is used to compute polynomials whose roots
1445# determine the $m$-torsion points on the curve.  Three options are
1446# available, which effect the result when $m$ is even and also the
1447# parent ring of the returned value.  The function can return either a
1448# polynomial or the evaluation of that polynomial at a point,
1449# depending on the input.  Values are cached.
1450#
1451# The options are controlled by the value of the parameter
1452# two_torsion_multiplicity, which may be 0, 1 or 2.  If it is 0 or 2,
1453# then a univariate polynomial will be returned (or evaluated at the
1454# parameter x if x is not None).  This is the polynomial whose roots
1455# are the values of $x(P)$ at the nonzero points $P$ where $m*P=0$
1456# (when two_torsion_multiplicity==2), or the points where $m*P=0$ but
1457# $2*P\not=0$ (when two_torsion_multiplicity==0).
1458#
1459# If two_torsion_multiplicity==1, then a bivariate polynomial is
1460# returned, which (as a function on the curve) has a simple zero at
1461# each nonzero point $P$ such that $m*P=0$.  When $m$ is odd this is a
1462# polynomial in $x$ alone, but is still returned as an element of a
1463# polynomial ring in two variables; when $m$ is even it has a factor
1464# $2y+a_1x+a_3$.  In this case if the parameter x is not None then it
1465# should be a tuple of length 2, or a point P on the curve, and the
1466# returned value is the value of the bivariate polynomial at this
1467# point.
1468#
1469# Comparison with Magma: Magma's function DivisionPolynomial(E,m)
1470# returns a triple of univariate polynomials $f,g,h$ where $f$ is
1471# \code{E.division_polynomial(m,two_torsion_multiplicity=2)}, $g$ is
1472# \code{E.division_polynomial(m,two_torsion_multiplicity=0)} and $h$
1473# is the quotient, so that $h=1$ when $m$ is odd.
1474
1475#############################################################
1476
1477    def division_polynomial_0(self, n, x=None, cache=None):
1478         r"""
1479         Returns the n^{th} torsion (division) polynomial, without
1480         the 2-torsion factor if n is even, as a polynomial in x.
1481
1482         These are the polynomials g_n defined in Mazur/Tate
1483         ("The p-adic sigma function"), but with the sign flipped for even
1484         n, so that the leading coefficient is always positive.
1485
1486         .. note::
1487
1488            This function is intended for internal use; users should use
1489            :meth:.division_polynomial.
1490
1491         .. seealso::
1492
1493            :meth:multiple_x_numerator
1494            :meth:multiple_x_denominator
1495            :meth:division_polynomial
1496
1497         INPUT:
1498
1499
1500         -  n - positive integer, or the special values -1
1501            and -2 which mean B_6 = (2y + a_1 x + a_3)^2 and
1502            B_6^2 respectively (in the notation of Mazur/Tate).
1503
1504         -  x - optional ring element to use as the "x"
1505            variable. If x is None, then a new polynomial ring will be
1506            constructed over the base ring of the elliptic curve, and its
1507            generator will be used as x. Note that x does not need to be a
1508            generator of a polynomial ring; any ring element is ok. This
1509            permits fast calculation of the torsion polynomial *evaluated* on
1510            any element of a ring.
1511
1512         -  cache - optional dictionary, with integer keys.
1513            If the key m is in cache, then cache[m] is assumed to be the value
1514            of division_polynomial_0(m) for the supplied x. New entries will
1515            be added to the cache as they are computed.
1516
1517
1518         ALGORITHM:
1519
1520         Recursion described in Mazur/Tate. The recursive
1521         formulae are evaluated O((log n)^2) times.
1522
1523         AUTHORS:
1524
1525         - David Harvey (2006-09-24): initial version
1526
1527         - John Cremona (2008-08-26): unified division polynomial code
1528
1529         EXAMPLES::
1530
1531             sage: E = EllipticCurve("37a")
1532             sage: E.division_polynomial_0(1)
1533             1
1534             sage: E.division_polynomial_0(2)
1535             1
1536             sage: E.division_polynomial_0(3)
1537             3*x^4 - 6*x^2 + 3*x - 1
1538             sage: E.division_polynomial_0(4)
1539             2*x^6 - 10*x^4 + 10*x^3 - 10*x^2 + 2*x + 1
1540             sage: E.division_polynomial_0(5)
1541             5*x^12 - 62*x^10 + 95*x^9 - 105*x^8 - 60*x^7 + 285*x^6 - 174*x^5 - 5*x^4 - 5*x^3 + 35*x^2 - 15*x + 2
1542             sage: E.division_polynomial_0(6)
1543             3*x^16 - 72*x^14 + 168*x^13 - 364*x^12 + 1120*x^10 - 1144*x^9 + 300*x^8 - 540*x^7 + 1120*x^6 - 588*x^5 - 133*x^4 + 252*x^3 - 114*x^2 + 22*x - 1
1544             sage: E.division_polynomial_0(7)
1545             7*x^24 - 308*x^22 + 986*x^21 - 2954*x^20 + 28*x^19 + 17171*x^18 - 23142*x^17 + 511*x^16 - 5012*x^15 + 43804*x^14 - 7140*x^13 - 96950*x^12 + 111356*x^11 - 19516*x^10 - 49707*x^9 + 40054*x^8 - 124*x^7 - 18382*x^6 + 13342*x^5 - 4816*x^4 + 1099*x^3 - 210*x^2 + 35*x - 3
1546             sage: E.division_polynomial_0(8)
1547             4*x^30 - 292*x^28 + 1252*x^27 - 5436*x^26 + 2340*x^25 + 39834*x^24 - 79560*x^23 + 51432*x^22 - 142896*x^21 + 451596*x^20 - 212040*x^19 - 1005316*x^18 + 1726416*x^17 - 671160*x^16 - 954924*x^15 + 1119552*x^14 + 313308*x^13 - 1502818*x^12 + 1189908*x^11 - 160152*x^10 - 399176*x^9 + 386142*x^8 - 220128*x^7 + 99558*x^6 - 33528*x^5 + 6042*x^4 + 310*x^3 - 406*x^2 + 78*x - 5
1548
1549         ::
1550
1551             sage: E.division_polynomial_0(18) % E.division_polynomial_0(6) == 0
1552             True
1553
1554         An example to illustrate the relationship with torsion points::
1555
1556             sage: F = GF(11)
1557             sage: E = EllipticCurve(F, [0, 2]); E
1558             Elliptic Curve defined by y^2  = x^3 + 2 over Finite Field of size 11
1559             sage: f = E.division_polynomial_0(5); f
1560             5*x^12 + x^9 + 8*x^6 + 4*x^3 + 7
1561             sage: f.factor()
1562             (5) * (x^2 + 5) * (x^2 + 2*x + 5) * (x^2 + 5*x + 7) * (x^2 + 7*x + 7) * (x^2 + 9*x + 5) * (x^2 + 10*x + 7)
1563
1564         This indicates that the x-coordinates of all the 5-torsion points
1565         of E are in GF(11^2), and therefore the
1566         y-coordinates are in \GF(11^4)::
1567
1568             sage: K = GF(11^4, 'a')
1569             sage: X = E.change_ring(K)
1570             sage: f = X.division_polynomial_0(5)
1571             sage: x_coords = f.roots(multiplicities=False); x_coords
1572             [10*a^3 + 4*a^2 + 5*a + 6,
1573              9*a^3 + 8*a^2 + 10*a + 8,
1574              8*a^3 + a^2 + 4*a + 10,
1575              8*a^3 + a^2 + 4*a + 8,
1576              8*a^3 + a^2 + 4*a + 4,
1577              6*a^3 + 9*a^2 + 3*a + 4,
1578              5*a^3 + 2*a^2 + 8*a + 7,
1579              3*a^3 + 10*a^2 + 7*a + 8,
1580              3*a^3 + 10*a^2 + 7*a + 3,
1581              3*a^3 + 10*a^2 + 7*a + 1,
1582              2*a^3 + 3*a^2 + a + 7,
1583              a^3 + 7*a^2 + 6*a]
1584
1585         Now we check that these are exactly the x-coordinates of the
1586         5-torsion points of E::
1587
1588             sage: for x in x_coords:
1589             ...       assert X.lift_x(x).order() == 5
1590
1591         The roots of the polynomial are the x-coordinates of the points P
1592         such that mP=0 but 2P\not=0::
1593
1594             sage: E=EllipticCurve('14a1')
1595             sage: T=E.torsion_subgroup()
1596             sage: [n*T.0 for n in range(6)]
1597             [(0 : 1 : 0),
1598             (9 : 23 : 1),
1599             (2 : 2 : 1),
1600             (1 : -1 : 1),
1601             (2 : -5 : 1),
1602             (9 : -33 : 1)]
1603             sage: pol=E.division_polynomial_0(6)
1604             sage: xlist=pol.roots(multiplicities=False); xlist
1605             [9, 2, -1/3, -5]
1606             sage: [E.lift_x(x, all=True) for x in xlist]
1607             [[(9 : 23 : 1), (9 : -33 : 1)], [(2 : 2 : 1), (2 : -5 : 1)], [], []]
1608
1609         .. note::
1610
1611            The point of order 2 and the identity do not appear.
1612            The points with x=-1/3 and x=-5 are not rational.
1613         """
1614         if cache is None:
1615             cache = {}
1616         else:
1617             try:
1618                 return cache[n]
1619             except KeyError:
1620                 pass
1621
1622         if x is None:
1623             x = rings.PolynomialRing(self.base_ring(), 'x').gen()
1624
1625         b2, b4, b6, b8 = self.b_invariants()
1626
1627         n = int(n)
1628         if n <= 4:
1629             if n == -1:
1630                 answer = 4*x**3 + b2*x**2 + 2*b4*x + b6
1631             elif n == -2:
1632                 answer = self.division_polynomial_0(-1, x, cache) ** 2
1633             elif n == 1 or n == 2:
1634                 answer = x.parent()(1)
1635             elif n == 3:
1636                 answer = 3*x**4 + b2*x**3 + 3*b4*x**2 + 3*b6*x + b8
1637             elif n == 4:
1638                 answer = -self.division_polynomial_0(-2, x, cache) + \
1639                          (6*x**2 + b2*x + b4) * \
1640                          self.division_polynomial_0(3, x, cache)
1641             else:
1642                 raise ValueError, "n must be a positive integer (or -1 or -2)"
1643         else:
1644             if n % 2 == 0:
1645                 m = (n-2) // 2
1646                 g_mplus3 = self.division_polynomial_0(m+3, x, cache)
1647                 g_mplus2 = self.division_polynomial_0(m+2, x, cache)
1648                 g_mplus1 = self.division_polynomial_0(m+1, x, cache)
1649                 g_m      = self.division_polynomial_0(m,   x, cache)
1650                 g_mless1 = self.division_polynomial_0(m-1, x, cache)
1651                 answer = g_mplus1 * \
1652                          (g_mplus3 * g_m**2 - g_mless1 * g_mplus2**2)
1653             else:
1654                 m = (n-1) // 2
1655                 g_mplus2 = self.division_polynomial_0(m+2, x, cache)
1656                 g_mplus1 = self.division_polynomial_0(m+1, x, cache)
1657                 g_m      = self.division_polynomial_0(m,   x, cache)
1658                 g_mless1 = self.division_polynomial_0(m-1, x, cache)
1659                 B6_sqr   = self.division_polynomial_0(-2, x, cache)
1660                 if m % 2 == 0:
1661                     answer = B6_sqr * g_mplus2 * g_m**3 - \
1662                              g_mless1 * g_mplus1**3
1663                 else:
1664                     answer = g_mplus2 * g_m**3 - \
1665                              B6_sqr * g_mless1 * g_mplus1**3
1666
1667         cache[n] = answer
1668         return answer
1669
1670    def two_division_polynomial(self, x = None):
1671        r"""
1672        Returns the 2-division polynomial of this elliptic curve evaluated
1673        at x.
1674
1675        INPUT:
1676
1677        - x - optional ring element to use as the x variable. If
1678          x is None, then a new polynomial ring will be
1679          constructed over the base ring of the elliptic curve, and
1680          its generator will be used as x. Note that x does
1681          not need to be a generator of a polynomial ring; any ring
1682          element is ok. This permits fast calculation of the torsion
1683          polynomial *evaluated* on any element of a ring.
1684
1685
1686        EXAMPLES::
1687
1688            sage: E=EllipticCurve('5077a1')
1689            sage: E.two_division_polynomial()
1690            4*x^3 - 28*x + 25
1691            sage: E=EllipticCurve(GF(3^2,'a'),[1,1,1,1,1])
1692            sage: E.two_division_polynomial()
1693            x^3 + 2*x^2 + 2
1694            sage: E.two_division_polynomial().roots()
1695            [(2, 1), (2*a, 1), (a + 2, 1)]
1696        """
1697        return self.division_polynomial_0(-1,x)
1698
1699    def division_polynomial(self, m, x=None, two_torsion_multiplicity=2):
1700        r"""
1701        Returns the m^{th} division polynomial of this elliptic
1702        curve evaluated at x.
1703
1704        INPUT:
1705
1706
1707        -  m - positive integer.
1708
1709        -  x - optional ring element to use as the "x"
1710           variable. If x is None, then a new polynomial ring will be
1711           constructed over the base ring of the elliptic curve, and its
1712           generator will be used as x. Note that x does not need to be a
1713           generator of a polynomial ring; any ring element is ok. This
1714           permits fast calculation of the torsion polynomial *evaluated* on
1715           any element of a ring.
1716
1717        -  two_torsion_multiplicity - 0,1 or 2
1718
1719            If 0: for even m when x is None, a univariate polynomial
1720            over the base ring of the curve is returned, which omits
1721            factors whose roots are the x-coordinates of the
1722            2-torsion points. Similarly when x is not none, the
1723            evaluation of such a polynomial at x is returned.
1724
1725            If 2: for even m when x is None, a univariate polynomial
1726            over the base ring of the curve is returned, which includes a
1727            factor of degree 3 whose roots are the x-coordinates of
1728            the 2-torsion points. Similarly when x is not
1729            none, the evaluation of such a polynomial at x is
1730            returned.
1731
1732            If 1: when x is None, a bivariate polynomial over the base
1733            ring of the curve is returned, which includes a factor
1734            2*y+a1*x+a3 which has simple zeros at the 2-torsion
1735            points. When x is not none, it should be a tuple of
1736            length 2, and the evaluation of such a polynomial at x
1737            is returned.
1738
1739        EXAMPLES::
1740
1741            sage: E = EllipticCurve([0,0,1,-1,0])
1742            sage: E.division_polynomial(1)
1743            1
1744            sage: E.division_polynomial(2, two_torsion_multiplicity=0)
1745            1
1746            sage: E.division_polynomial(2, two_torsion_multiplicity=1)
1747            2*y + 1
1748            sage: E.division_polynomial(2, two_torsion_multiplicity=2)
1749            4*x^3 - 4*x + 1
1750            sage: E.division_polynomial(2)
1751            4*x^3 - 4*x + 1
1752            sage: [E.division_polynomial(3, two_torsion_multiplicity=i) for i in range(3)]
1753            [3*x^4 - 6*x^2 + 3*x - 1, 3*x^4 - 6*x^2 + 3*x - 1, 3*x^4 - 6*x^2 + 3*x - 1]
1754            sage: [type(E.division_polynomial(3, two_torsion_multiplicity=i)) for i in range(3)]
1755            [<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_rational_dense'>,
1756            <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'>,
1757            <class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_rational_dense'>]
1758
1759        ::
1760
1761            sage: E = EllipticCurve([0, -1, 1, -10, -20])
1762            sage: R.<z>=PolynomialRing(QQ)
1763            sage: E.division_polynomial(4,z,0)
1764            2*z^6 - 4*z^5 - 100*z^4 - 790*z^3 - 210*z^2 - 1496*z - 5821
1765            sage: E.division_polynomial(4,z)
1766            8*z^9 - 24*z^8 - 464*z^7 - 2758*z^6 + 6636*z^5 + 34356*z^4 + 53510*z^3 + 99714*z^2 + 351024*z + 459859
1767
1768        This does not work, since when two_torsion_multiplicity is 1, we
1769        compute a bivariate polynomial, and must evaluate at a tuple of
1770        length 2::
1771
1772            sage: E.division_polynomial(4,z,1)
1773            Traceback (most recent call last):
1774            ...
1775            ValueError: x should be a tuple of length 2 (or None) when two_torsion_multiplicity is 1
1776            sage: R.<z,w>=PolynomialRing(QQ,2)
1777            sage: E.division_polynomial(4,(z,w),1).factor()
1778            (2*w + 1) * (2*z^6 - 4*z^5 - 100*z^4 - 790*z^3 - 210*z^2 - 1496*z - 5821)
1779
1780        We can also evaluate this bivariate polynomial at a point::
1781
1782            sage: P = E(5,5)
1783            sage: E.division_polynomial(4,P,two_torsion_multiplicity=1)
1784            -1771561
1785        """
1786
1787        if not two_torsion_multiplicity in [0,1,2]:
1788            raise ValueError, "two_torsion_multiplicity must be 0,1 or 2"
1789
1790        # Coerce the input m to be an integer
1791        m = rings.Integer(m)
1792
1793        if two_torsion_multiplicity == 0:
1794            try:
1795                return self.__divpoly0[(m,x)]
1796            except AttributeError:
1797                self.__divpoly0 = {}
1798            except KeyError:
1799                pass
1800            f = self.division_polynomial_0(m,x)
1801            self.__divpoly0[(m,x)] = f
1802            return f
1803
1804        if two_torsion_multiplicity == 1:
1805            try:
1806                return self.__divpoly1[(m,x)]
1807            except AttributeError:
1808                self.__divpoly1 = {}
1809            except KeyError:
1810                pass
1811            xy = x
1812            R, (x,y) = PolynomialRing(self.base_ring(), 2, 'x,y').objgens()
1813            a1,a2,a3,a4,a6 = self.a_invariants()
1814            f = self.division_polynomial_0(m,x)
1815            if m % 2 == 0:
1816                f *= (2*y+a1*x+a3)
1817            if xy is None:
1818                self.__divpoly1[(m,(x,y))] = f
1819                return f
1820            else:
1821                if isinstance(xy,tuple) and len(xy)==2 or isinstance(xy, ell_point.EllipticCurvePoint_field):
1822                    fxy = f(xy[0],xy[1])
1823                    self.__divpoly1[(m,xy)] = fxy
1824                    return fxy
1825                else:
1826                    raise ValueError, "x should be a tuple of length 2 (or None) when two_torsion_multiplicity is 1"
1827
1828        if two_torsion_multiplicity == 2:
1829            try:
1830                return self.__divpoly2[(m,x)]
1831            except AttributeError:
1832                self.__divpoly2 = {}
1833            except KeyError:
1834                pass
1835            f = self.division_polynomial_0(m,x)
1836            if m%2 == 0:
1837                f *= self.division_polynomial_0(-1,x)
1838            self.__divpoly2[(m,x)] = f
1839            return f
1840
1841    torsion_polynomial = division_polynomial
1842
1843    def _multiple_x_numerator(self, n, x=None, cache=None):
1844         r"""
1845         Returns the numerator of the x-coordinate of the n\th multiple of a
1846         point, using torsion polynomials (division polynomials).
1847
1848         INPUT:
1849
1850         -  n, x, cache --  as described in division_polynomial_0().
1851
1852         The result is cached.  This is so that on calling
1853         P.division_points(n) for the same n and different
1854         points P (on the same curve), we do not have to recompute
1855         the polynomials.
1856
1857         .. warning::
1858
1859            There may of course be cancellation between the numerator
1860            and the denominator (_multiple_x_denominator()). Be
1861            careful. E.g. if a point on an elliptic curve with
1862            coefficients in ZZ reduces to a singular point modulo a
1863            prime, then there will be cancellation, otherwise not, see
1864            Chris Wuthrich' p-adic heights in families of elliptic
1865            curves'.
1866
1867         .. seealso::
1868
1869            :meth:_multiple_x_denominator
1870
1871         AUTHORS:
1872
1873         - David Harvey (2006-09-24)
1874
1875         EXAMPLES::
1876
1877             sage: E = EllipticCurve("37a")
1878             sage: P = E.gens()[0]
1879             sage: x = P[0]
1880
1881         ::
1882
1883             sage: (35*P)[0]
1884             -804287518035141565236193151/1063198259901027900600665796
1885             sage: E._multiple_x_numerator(35, x)
1886             -804287518035141565236193151
1887             sage: E._multiple_x_denominator(35, x)
1888             1063198259901027900600665796
1889
1890         ::
1891
1892             sage: (36*P)[0]
1893             54202648602164057575419038802/15402543997324146892198790401
1894             sage: E._multiple_x_numerator(36, x)
1895             54202648602164057575419038802
1896             sage: E._multiple_x_denominator(36, x)
1897             15402543997324146892198790401
1898
1899         An example where cancellation occurs::
1900
1901             sage: E = EllipticCurve("88a1")
1902             sage: P = E([2,2])   # fixed choice of generator
1903             sage: n = E._multiple_x_numerator(11, P[0]); n
1904             442446784738847563128068650529343492278651453440
1905             sage: d = E._multiple_x_denominator(11, P[0]); d
1906             1427247692705959881058285969449495136382746624
1907             sage: n/d
1908             310
1909             sage: 11*P
1910             (310 : -5458 : 1)
1911         """
1912         try:
1913             return self._mul_x_num_cache[n]
1914         except AttributeError:
1915             self._mul_x_num_cache = {}
1916         except KeyError:
1917             pass
1918
1919         if cache is None:
1920             cache = {}
1921
1922         if x is None:
1923             x = rings.PolynomialRing(self.base_ring(), 'x').gen()
1924
1925         n = int(n)
1926         if n < 2:
1927             print "n must be at least 2"
1928
1929         self.division_polynomial_0( -2, x, cache)
1930         self.division_polynomial_0(n-1, x, cache)
1931         self.division_polynomial_0(, x, cache)
1932         self.division_polynomial_0(n+1, x, cache)
1933
1934         if n % 2 == 0:
1935             self._mul_x_num_cache[n] = x * cache[-1] * cache[n]**2 - cache[n-1] * cache[n+1]
1936         else:
1937             self._mul_x_num_cache[n] = x * cache[n]**2 - cache[-1] * cache[n-1] * cache[n+1]
1938         return self._mul_x_num_cache[n]
1939
1940
1941    def _multiple_x_denominator(self, n, x=None, cache=None):
1942         r"""
1943         Returns the denominator of the x-coordinate of the nth multiple of
1944         a point, using torsion polynomials (division polynomials).
1945
1946         INPUT:
1947
1948         -  n, x, cache --  as described in division_polynomial_0().
1949
1950         The result is cached.  This is so that calling
1951         P.division_points(n) for the same n and different points P
1952         (on the same curve) does not have to recompute the
1953         polynomials.
1954
1955         .. seealso::
1956
1957            :meth:multiple_x_numerator
1958
1959         TODO: the numerator and denominator versions share a calculation,
1960         namely squaring \psi_n. Maybe would be good to offer a
1961         combined version to make this more efficient.
1962
1963         EXAMPLES::
1964
1965             sage: E = EllipticCurve("43a")
1966             sage: P = E.gens()[0]
1967             sage: x = P[0]
1968             sage: (31*P)[0]
1969             -33058398375463796474831580/154693637754223970056975321
1970             sage: E._multiple_x_numerator(31, x)
1971             -33058398375463796474831580
1972             sage: E._multiple_x_denominator(31, x)
1973             154693637754223970056975321
1974
1975         AUTHORS:
1976
1977         - David Harvey (2006-09-24)
1978         """
1979         try:
1980             return self._mul_x_den_cache[n]
1981         except AttributeError:
1982             self._mul_x_den_cache = {}
1983         except KeyError:
1984             pass
1985
1986         if cache is None:
1987             cache = {}
1988
1989         if x is None:
1990             x = rings.PolynomialRing(self.base_ring(), 'x').gen()
1991
1992         n = int(n)
1993         if n < 2:
1994             print "n must be at least 2"
1995
1996         self.division_polynomial_0(-2, x, cache)
1997         self.division_polynomial_0(n , x, cache)
1998
1999         if n % 2 == 0:
2000             self._mul_x_den_cache[n] = cache[-1] * cache[n]**2
2001         else:
2002             self._mul_x_den_cache[n] = cache[n]**2
2003         return self._mul_x_den_cache[n]
2004
2005
2006    def multiplication_by_m(self, m, x_only=False):
2007        r"""
2008        Return the multiplication-by-m map from self to self as a pair of
2009        rational functions in two variables x,y.
2010
2011        INPUT:
2012
2013        -  m - a nonzero integer
2014
2015        -  x_only - bool (default: False) if True, return
2016           only the x-coordinate of the map.
2017
2018
2019        OUTPUT:
2020
2021        (2-tuple) (f(x), g(x,y)), where f and g are rational
2022        functions with the degree of y in g(x,y) exactly 1.
2023
2024
2025        .. note:
2026
2027           The result is not cached.
2028
2029           m is allowed to be negative (but not 0).
2030
2031        EXAMPLES::
2032
2033            sage: E = EllipticCurve([-1,3])
2034
2035        We verify that multiplication by 1 is just the identity::
2036
2037            sage: E.multiplication_by_m(1)
2038            (x, y)
2039
2040        Multiplication by 2 is more complicated::
2041
2042            sage: f = E.multiplication_by_m(2)
2043            sage: f
2044            ((x^4 + 2*x^2 - 24*x + 1)/(4*x^3 - 4*x + 12), (8*x^6*y - 40*x^4*y + 480*x^3*y - 40*x^2*y + 96*x*y - 568*y)/(64*x^6 - 128*x^4 + 384*x^3 + 64*x^2 - 384*x + 576))
2045
2046        Grab only the x-coordinate (less work)::
2047
2048            sage: E.multiplication_by_m(2, x_only=True)
2049            (x^4 + 2*x^2 - 24*x + 1)/(4*x^3 - 4*x + 12)
2050
2051        We check that it works on a point::
2052
2053            sage: P = E([2,3])
2054            sage: eval = lambda f,P: [fi(P[0],P[1]) for fi in f]
2055            sage: assert E(eval(f,P)) == 2*P
2056
2057        We do the same but with multiplication by 3::
2058
2059            sage: f = E.multiplication_by_m(3)
2060            sage: assert E(eval(f,P)) == 3*P
2061
2062        And the same with multiplication by 4::
2063
2064            sage: f = E.multiplication_by_m(4)
2065            sage: assert E(eval(f,P)) == 4*P
2066
2067        And the same with multiplication by -1,-2,-3,-4::
2068
2069            sage: for m in [-1,-2,-3,-4]:
2070            ...       f = E.multiplication_by_m(m)
2071            ...       assert E(eval(f,P)) == m*P
2072
2073        TESTS:
2074
2075        Verify for this fairly random looking curve and point that
2076        multiplication by m returns the right result for the first 10
2077        integers::
2078
2079            sage: E = EllipticCurve([23,-105])
2080            sage: P = E([129/4, 1479/8])
2081            sage: for n in [1..10]:
2082            ...       f = E.multiplication_by_m(n)
2083            ...       Q = n*P
2084            ...       assert Q == E(eval(f,P))
2085            ...       f = E.multiplication_by_m(-n)
2086            ...       Q = -n*P
2087            ...       assert Q == E(eval(f,P))
2088
2089        The following test shows that \#4364 is indeed fixed::
2090
2091            sage: p = next_prime(2^30-41)
2092            sage: a = GF(p)(1)
2093            sage: b = GF(p)(1)
2094            sage: E = EllipticCurve([a, b])
2095            sage: P = E.random_point()
2096            sage: my_eval = lambda f,P: [fi(P[0],P[1]) for fi in f]
2097            sage: f = E.multiplication_by_m(2)
2098            sage: assert(E(eval(f,P)) == 2*P)
2099        """
2100        # Coerce the input m to be an integer
2101        m = rings.Integer(m)
2102
2103        if m==0:
2104            raise ValueError, "m must be a non-zero integer"
2105
2106        R = PolynomialRing(self.base_ring(), 2, 'x,y')
2107
2108        # Kxy is the function field, containing the full division polynomial.
2109        Kxy = R.fraction_field()
2110        x,y = Kxy.gens()
2111
2112        # Special case of multiplication by 1 is easy.
2113        if m == 1:
2114            return (x, y)
2115
2116        # Grab curve invariants
2117        a1,a2,a3,a4,a6 = self.a_invariants()
2118
2119        if m == -1:
2120            return (x, -y-a1*x-a3)
2121
2122        # the x-coordonate does not depend on the sign of m.  The work
2123        # here is done by functions defined earlier:
2124
2125        mx = self._multiple_x_numerator(m.abs(),x) / self._multiple_x_denominator(m.abs(),x)
2126
2127        if x_only:
2128            # Return it if the optional parameter x_only is set.
2129            return mx
2130
2131        #  Consideration of the invariant differential
2132        #  w=dx/(2*y+a1*x+a3) shows that m*w = d(mx)/(2*my+a1*mx+a3)
2133        #  and hence 2*my+a1*mx+a3 = (1/m)*(2*y+a1*x+a3)*d(mx)/dx
2134
2135        my = ((2*y+a1*x+a3)*mx.derivative(x)/m - a1*mx-a3)/2
2136
2137        return mx, my
2138
2139    def isomorphism_to(self, other):
2140        """
2141        Given another weierstrass model other of self, return an
2142        isomorphism from self to other.
2143
2144        INPUT:
2145
2146        - other -- an elliptic curve isomorphic to self.
2147
2148        OUTPUT:
2149
2150        (Weierstrassmorphism) An isomorphism from self to other.
2151
2152        .. note::
2153
2154           If the curves in question are not isomorphic, a ValueError is raised.
2155
2156        EXAMPLES::
2157
2158            sage: E = EllipticCurve('37a')
2159            sage: F = E.short_weierstrass_model()
2160            sage: w = E.isomorphism_to(F); w
2161            Generic morphism:
2162            From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
2163            To:   Abelian group of points on Elliptic Curve defined by y^2  = x^3 - 16*x + 16 over Rational Field
2164            Via:  (u,r,s,t) = (1/2, 0, 0, -1/2)
2165            sage: P = E(0,-1,1)
2166            sage: w(P)
2167            (0 : -4 : 1)
2168            sage: w(5*P)
2169            (1 : 1 : 1)
2170            sage: 5*w(P)
2171            (1 : 1 : 1)
2172            sage: 120*w(P) == w(120*P)
2173            True
2174
2175        We can also handle injections to different base rings::
2176
2177            sage: K.<a> = NumberField(x^3-7)
2178            sage: E.isomorphism_to(E.change_ring(K))
2179            Generic morphism:
2180              From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
2181              To:   Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 + (-1)*x over Number Field in a with defining polynomial x^3 - 7
2182              Via:  (u,r,s,t) = (1, 0, 0, 0)
2183        """
2184        return wm.WeierstrassIsomorphism(self, None, other)
2185
2186    def automorphisms(self, field=None):
2187        """
2188        Return the set of isomorphisms from self to itself (as a list).
2189
2190        INPUT:
2191
2192        - field (default None) -- a field into which the
2193          coefficients of the curve may be coerced (by default, uses
2194          the base field of the curve).
2195
2196        OUTPUT:
2197
2198        (list) A list of WeierstrassIsomorphism objects
2199        consisting of all the isomorphisms from the curve self to
2200        itself defined over field.
2201
2202        EXAMPLES::
2203
2204            sage: E = EllipticCurve_from_j(QQ(0)) # a curve with j=0 over QQ
2205            sage: E.automorphisms();
2206            [Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Rational Field
2207            Via:  (u,r,s,t) = (-1, 0, 0, -1), Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Rational Field
2208            Via:  (u,r,s,t) = (1, 0, 0, 0)]
2209
2210        We can also find automorphisms defined over extension fields::
2211
2212            sage: K.<a> = NumberField(x^2+3) # adjoin roots of unity
2213            sage: E.automorphisms(K)
2214            [Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^2 + 3
2215            Via:  (u,r,s,t) = (1, 0, 0, 0),
2216            ...
2217            Generic endomorphism of Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Number Field in a with defining polynomial x^2 + 3
2218            Via:  (u,r,s,t) = (-1/2*a - 1/2, 0, 0, 0)]
2219
2220        ::
2221
2222            sage: [ len(EllipticCurve_from_j(GF(q,'a')(0)).automorphisms()) for q in [2,4,3,9,5,25,7,49]]
2223            [2, 24, 2, 12, 2, 6, 6, 6]
2224        """
2225        if field==None:
2226            return [wm.WeierstrassIsomorphism(self, urst, self)
2227                    for urst in wm.isomorphisms(self,self)]
2228        E=self.change_ring(field)
2229        return [wm.WeierstrassIsomorphism(E, urst, E)
2230                for urst in wm.isomorphisms(E,E)]
2231
2232    def isomorphisms(self, other, field=None):
2233        """
2234        Return the set of isomorphisms from self to other (as a list).
2235
2236        INPUT:
2237
2238        - other -- another elliptic curve.
2239
2240        - field (default None) -- a field into which the
2241          coefficients of the curves may be coerced (by default, uses
2242          the base field of the curves).
2243
2244        OUTPUT:
2245
2246        (list) A list of WeierstrassIsomorphism objects consisting of all
2247        the isomorphisms from the curve self to the curve
2248        other defined over field.
2249
2250        EXAMPLES::
2251
2252            sage: E = EllipticCurve_from_j(QQ(0)) # a curve with j=0 over QQ
2253            sage: F = EllipticCurve('27a3') # should be the same one
2254            sage: E.isomorphisms(F);
2255            [Generic morphism:
2256            From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Rational Field
2257            To:   Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Rational Field
2258            Via:  (u,r,s,t) = (-1, 0, 0, -1), Generic morphism:
2259            From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Rational Field
2260            To:   Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 over Rational Field
2261            Via:  (u,r,s,t) = (1, 0, 0, 0)]
2262
2263        We can also find istomorphisms defined over extension fields::
2264
2265            sage: E=EllipticCurve(GF(7),[0,0,0,1,1])
2266            sage: F=EllipticCurve(GF(7),[0,0,0,1,-1])
2267            sage: E.isomorphisms(F)
2268            []
2269            sage: E.isomorphisms(F,GF(49,'a'))
2270            [Generic morphism:
2271            From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in a of size 7^2
2272            To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 6 over Finite Field in a of size 7^2
2273            Via:  (u,r,s,t) = (a + 3, 0, 0, 0), Generic morphism:
2274            From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in a of size 7^2
2275            To:   Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 6 over Finite Field in a of size 7^2
2276            Via:  (u,r,s,t) = (6*a + 4, 0, 0, 0)]
2277        """
2278        if field==None:
2279            return [wm.WeierstrassIsomorphism(self, urst, other)
2280                    for urst in wm.isomorphisms(self,other)]
2281        E=self.change_ring(field)
2282        F=other.change_ring(field)
2283        return [wm.WeierstrassIsomorphism(E, urst, F)
2284                for urst in wm.isomorphisms(E,F)]
2285
2286    def is_isomorphic(self, other, field=None):
2287        """
2288        Returns whether or not self is isomorphic to other.
2289
2290        INPUT:
2291
2292        - other -- another elliptic curve.
2293
2294        - field (default None) -- a field into which the
2295          coefficients of the curves may be coerced (by default, uses
2296          the base field of the curves).
2297
2298        OUTPUT:
2299
2300        (bool) True if there is an isomorphism from curve self to
2301        curve other defined over field.
2302
2303        EXAMPLES::
2304
2305            sage: E = EllipticCurve('389a')
2306            sage: F = E.change_weierstrass_model([2,3,4,5]); F
2307            Elliptic Curve defined by y^2 + 4*x*y + 11/8*y = x^3 - 3/2*x^2 - 13/16*x over Rational Field
2308            sage: E.is_isomorphic(F)
2309            True
2310            sage: E.is_isomorphic(F.change_ring(CC))
2311            False
2312        """
2313        if not is_EllipticCurve(other):
2314            return False
2315        if field==None:
2316            if self.base_ring() != other.base_ring():
2317                return False
2318            elif self.j_invariant() != other.j_invariant():  # easy check
2319                return False
2320            else:
2321                return wm.isomorphisms(self,other,True) != None
2322        else:
2323            E=self.base_extend(field)
2324            F=other.base_extend(field)
2325            if E.j_invariant() != F.j_invariant():  # easy check
2326                return False
2327            else:
2328                return wm.isomorphisms(E,other,F) != None
2329
2330    def change_weierstrass_model(self, *urst):
2331        r"""
2332        Return a new Weierstrass model of self under the standard transformation (u,r,s,,t)
2333
2334        .. math::
2335
2336             (x,y) \mapsto (x',y') = (u^2xr , u^3y + su^2x' + t).
2337
2338
2339        EXAMPLES::
2340
2341            sage: E = EllipticCurve('15a')
2342            sage: F1 = E.change_weierstrass_model([1/2,0,0,0]); F1
2343            Elliptic Curve defined by y^2 + 2*x*y + 8*y = x^3 + 4*x^2 - 160*x - 640 over Rational Field
2344            sage: F2 = E.change_weierstrass_model([7,2,1/3,5]); F2
2345            Elliptic Curve defined by y^2 + 5/21*x*y + 13/343*y = x^3 + 59/441*x^2 - 10/7203*x - 58/117649 over Rational Field
2346            sage: F1.is_isomorphic(F2)
2347            True
2348        """
2349        if isinstance(urst[0], (tuple, list)):
2350            urst = urst[0]
2351        return constructor.EllipticCurve((wm.baseWI(*urst))(self.ainvs()))
2352
2353    def short_weierstrass_model(self, complete_cube=True):
2354        """
2355        Returns a short Weierstrass model for self.
2356
2357        INPUT:
2358
2359        -  complete_cube - bool (default: True); for
2360           meaning, see below.
2361
2362        OUTPUT:
2363
2364        An elliptic curve.
2365
2366        If complete_cube=True: Return a model of the form
2367        y^2 = x^3 + a*x + b for this curve. The characteristic
2368        must not be 2; in characteristic 3, it is only possible if b_2=0.
2369
2370        If complete_cube=False: Return a model of the form
2371        y^2 = x^3 + ax^2 + bx + c for this curve. The
2372        characteristic must not be 2.
2373
2374        EXAMPLES::
2375
2376            sage: E = EllipticCurve([1,2,3,4,5])
2377            sage: print E
2378            Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Rational Field
2379            sage: F = E.short_weierstrass_model()
2380            sage: print F
2381            Elliptic Curve defined by y^2  = x^3 + 4941*x + 185166 over Rational Field
2382            sage: E.is_isomorphic(F)
2383            True
2384            sage: F = E.short_weierstrass_model(complete_cube=False)
2385            sage: print F
2386            Elliptic Curve defined by y^2  = x^3 + 9*x^2 + 88*x + 464 over Rational Field
2387            sage: print E.is_isomorphic(F)
2388            True
2389
2390        ::
2391
2392            sage: E = EllipticCurve(GF(3),[1,2,3,4,5])
2393            sage: E.short_weierstrass_model(complete_cube=False)
2394            Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 3
2395
2396        This used to be different see trac #3973::
2397
2398            sage: E.short_weierstrass_model()
2399            Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 3
2400
2401        More tests in characteristic 3::
2402
2403            sage: E = EllipticCurve(GF(3),[0,2,1,2,1])
2404            sage: E.short_weierstrass_model()
2405            Traceback (most recent call last):
2406            ...
2407            ValueError: short_weierstrass_model(): no short model for Elliptic Curve defined by y^2 + y = x^3 + 2*x^2 + 2*x + 1 over Finite Field of size 3 (characteristic is 3)
2408            sage: E.short_weierstrass_model(complete_cube=False)
2409            Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 2*x + 2 over Finite Field of size 3
2410            sage: E.short_weierstrass_model(complete_cube=False).is_isomorphic(E)
2411            True
2412        """
2413        import constructor
2414        K = self.base_ring()
2415
2416        # any curve of the form y^2 = x^3 +.. is singular in characteristic 2
2417        if K.characteristic() == 2:
2418            raise ValueError, "short_weierstrass_model(): no short model for %s (characteristic is %s)"%(self,K.characteristic())
2419
2420        # in characteristic 3 we can complete the square but we can only complete the cube if b2 is 0
2421        if K.characteristic() == 3:
2422            b2,b4,b6,_ = self.b_invariants()
2423            if complete_cube and b2 != 0:
2424                raise ValueError, "short_weierstrass_model(): no short model for %s (characteristic is %s)"%(self,K.characteristic())
2425            else:
2426                return constructor.EllipticCurve([0,b2,0,8*b4,16*b6])
2427
2428        a1,a2,a3,_,_ = self.a_invariants()
2429        if complete_cube:
2430            if a1==0 and a2==0 and a3==0:
2431                return self
2432            else:
2433                b2,b4,b6,_ = self.b_invariants()
2434                if b2==0:
2435                    return constructor.EllipticCurve([0,0,0,8*b4,16*b6])
2436                else:
2437                    c4, c6 = self.c_invariants()
2438                    return constructor.EllipticCurve([0,0,0,-27*c4, -54*c6])
2439        else:
2440            if a1==0 and a3==0:
2441                return self
2442            else:
2443                b2,b4,b6,_ = self.b_invariants()
2444                return constructor.EllipticCurve([0,b2,0,8*b4,16*b6])
2445
2446
2447
2448    # Plotting
2449
2450
2451    def plot(self, xmin=None, xmax=None, **args):
2452        """
2453        Draw a graph of this elliptic curve.
2454
2455        INPUT:
2456
2457        -  xmin, xmax - (optional) points will be computed at
2458           least within this range, but possibly farther.
2459
2460        -  **args - all other options are passed to the
2461           line graphing primitive.
2462
2463
2464        EXAMPLES::
2465
2466            sage: E = EllipticCurve([0,-1])
2467            sage: plot(E, rgbcolor=hue(0.7))
2468            sage: E = EllipticCurve('37a')
2469            sage: plot(E)
2470            sage: plot(E, xmin=25,xmax=25)
2471        """
2472        RR = rings.RealField()
2473        K = self.base_ring()
2474        try:
2475            RR._coerce_(K(1))
2476        except TypeError:
2477            raise NotImplementedError, "Plotting of curves over %s not implemented yet"%K
2478        a1, a2, a3, a4, a6 = self.ainvs()
2479        R = rings.PolynomialRing(rings.RealField(), 'x')
2480        x = R.gen()
2481        d = 4*x**3 + (a1**2 + 4*a2)*x**2 + (2*a3*a1 + 4*a4)*x + (a3**2 + 4*a6)
2482        # Internal function for plotting first branch of the curve
2483        f1 = lambda z: (-(a1*z + a3) + sqrt(abs(d(z))))/2
2484        # Internal function for plotting second branch of the curve
2485        f2 = lambda z: (-(a1*z + a3) - sqrt(abs(d(z))))/2
2486        r = d.roots(multiplicities=False)
2487        r.sort()
2488        if xmax is None:
2489            xmax = r[-1] + 2
2490        xmax = max(xmax, r[-1]+2)
2491        if xmin is None:
2492            xmin = r[0]  - 2
2493        xmin = min(xmin, r[0]-2)
2494        if len(r) == 1:
2495            # one real root; 1 component
2496            I = [(r[0],xmax)]
2497        else:
2498            # three real roots; 2 components
2499            I = [(r[0],r[1]), (r[2],xmax)]
2500        I = [(max(a,xmin),min(b,xmax)) for a,b in I]
2501
2502        g = plot.Graphics()
2503        try:
2504            plot_points = int(args['plot_points'])
2505            del args['plot_points']
2506        except KeyError:
2507            plot_points = 100
2508
2509        for j in range(len(I)):
2510            a,b = I[j]
2511            delta = (b-a)/float(plot_points)
2512            v = []
2513            w = []
2514            for i in range(plot_points):
2515                x = a + delta*i
2516                v.append((x, f1(x)))
2517                w.append((x, f2(x)))
2518            v.append((b,f1(b)))
2519            w.append((b,f2(b)))
2520            if len(I) == 2 and j == 0:  # two components -- the oh.
2521                g += plot.line(v + list(reversed(w)) + [v[0]], **args)
2522            else:
2523                g += plot.line(list(reversed(v)) + w, **args)
2524        return g
2525
2526    def formal_group(self):
2527        r"""
2528        The formal group associated to this elliptic curve.
2529
2530        EXAMPLES::
2531
2532            sage: E = EllipticCurve("37a")
2533            sage: E.formal_group()
2534            Formal Group associated to the Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
2535        """
2536        try:
2537            return self.__formal_group
2538        except AttributeError:
2539            self.__formal_group = formal_group.EllipticCurveFormalGroup(self)
2540            return self.__formal_group
2541
2542    formal = formal_group
2543
2544    def _p_primary_torsion_basis(self,p,m=None):
2545        r"""
2546        Find a basis for the p-primary part of the torsion
2547        subgroup of this elliptic curve.
2548
2549        INPUT:
2550
2551        - p (integer) -- a prime number.
2552
2553        - m (integer or None) -- if not None, the $p$-primary torsion will be assumed to have order at most $p^m$.
2554
2555        OUTPUT:
2556
2557        A list of 0, 1 or 2 pairs [T,k] where T is a generator of
2558        order p^k. That is, either [] or [[T_1,k_1]] or
2559        [[T_1,k_1],[T_2,k_2]] with [], [T_1], or [T_1,T_2] a
2560        basis and p^{k_1} \ge p^{k_2} \ge 1 their orders.
2561
2562        .. warning::
2563
2564           1. Do not call this on a curve whose group is
2565              p-divisible (i.e., whose p-primary part
2566              is infinite)!
2567
2568           2. The code uses division polynomials and will be slow for
2569              large p.
2570
2571        EXAMPLES::
2572
2573            sage: E=EllipticCurve('11a1')
2574            sage: E._p_primary_torsion_basis(5)
2575            [[(5 : -6 : 1), 1]]
2576            sage: K.<t>=NumberField(x^4 + x^3 + 11*x^2 + 41*x + 101)
2577            sage: EK=E.base_extend(K)
2578            sage: EK._p_primary_torsion_basis(5)
2579            [[(16 : 60 : 1), 1], [(t : 1/11*t^3 + 6/11*t^2 + 19/11*t + 48/11 : 1), 1]]
2580            sage: EF=E.change_ring(GF(101))
2581            sage: EF._p_primary_torsion_basis(5)
2582            [[(0 : 13 : 1), 1], [(5 : 5 : 1), 1]]
2583
2584            This shows that the bug at trac \#4937 is fixed::
2585
2586            sage: a=804515977734860566494239770982282063895480484302363715494873
2587            sage: b=584772221603632866665682322899297141793188252000674256662071
2588            sage: [t[1] for t in EllipticCurve(GF(10^60+3201),[0,a,0,b,0])._p_primary_torsion_basis(2)]
2589            [16, 1]
2590
2591            sage: F.<z> = CyclotomicField(21)
2592            sage: E = EllipticCurve([2,-z^7,-z^7,0,0])
2593            sage: E._p_primary_torsion_basis(7,2)
2594            [[(0 : z^7 : 1), 1],
2595            [(z^7 - z^6 + z^4 - z^3 + z^2 - 1 : z^8 - 2*z^7 + z^6 + 2*z^5 - 3*z^4 + 2*z^3 - 2*z + 2 : 1),
2596            1]]
2597        """
2598        p = rings.Integer(p)
2599        if not p.is_prime():
2600            raise ValueError, "p (=%s) should be prime"%p
2601
2602        if m is None:
2603            from sage.rings.infinity import Infinity
2604            m = Infinity
2605
2606        if m == 0:
2607            return []
2608
2609        # First find the p-torsion:
2610        Ep = self(0).division_points(p)
2611        p_rank = rings.Integer(len(Ep)).exact_log(p)
2612        assert p_rank in [0,1,2]
2613
2614        if p_rank == 0:
2615            return []
2616
2617        assert p_rank in [1,2]
2618
2619        if p_rank == 1:
2620            P = Ep[0]
2621            if P.is_zero(): P=Ep[1]
2622            k = 1
2623            if m==1:
2624                return [[P,k]]
2625            pts = P.division_points(p) # length 0 or p
2626            while len(pts)>0:
2627                k += 1
2628                P = pts[0]
2629                if m<=k:
2630                    return [[P,k]]
2631                pts = P.division_points(p)
2632            # now P generates the p-power-torsion and has order p^k
2633            return [[P,k]]
2634
2635        assert p_rank == 2
2636
2637        Epi = iter(Ep) # used to iterate through Ep
2638        # Find P1,P2 which generate the p-torsion:
2639        P1 = Epi.next()
2640        while P1.is_zero(): P1 = Epi.next()
2641        P2 = Epi.next()
2642        while generic.linear_relation(P1,P2,'+')[0] != 0: P2 = Epi.next()
2643
2644        k = 1
2645        log_order = 2
2646        if m<=log_order:
2647            return [[P1,1],[P2,1]]
2648
2649        pts1 = P1.division_points(p)
2650        pts2 = P2.division_points(p)
2651        while len(pts1)>0 and len(pts2)>0:
2652            k += 1
2653            P1 = pts1[0]
2654            P2 = pts2[0]
2655            log_order += 2
2656            if m<=log_order:
2657                return [[P1,k],[P2,k]]
2658            pts1 = P1.division_points(p)
2659            pts2 = P2.division_points(p)
2660
2661        # Now P1,P2 are a basis for the p^k torsion, which is
2662        # isomorphic to (Z/p^k)^2, and k is the maximal integer for
2663        # which this is the case.
2664
2665        # We now determine whether a combination (P2 or P1+a*P2 for
2666        # some a) can be further divided for some a mod p; if so,
2667        # replace P1 by that combination, set pts to be the list of
2668        # solutions Q to p*Q=P1.  If no combination can be divided,
2669        # then the structure is (p^k,p^k) and we can stop.
2670
2671        if len(pts1) > 0:
2672            pts = pts1
2673        elif len(pts2) > 0:
2674            P1, P2 = P2, P1
2675            pts = pts2
2676        else:
2677            for Q in generic.multiples(P2,p-1,P1+P2,operation='+'):
2678                # Q runs through P1+a*P2 for a=1,2,...,p-1
2679                pts = Q.division_points(p)
2680                if len(pts) > 0:
2681                    P1 = Q
2682                    break
2683
2684        if len(pts)==0:
2685            return [[P1,k],[P2,k]]
2686
2687        # Now the structure is (p^n,p^k) for some n>k.  We need to
2688        # replace P1 by an element of maximal order p^n.  So far we
2689        # have pts = list of Q satisfying p*Q=P1, and all such Q have
2690        # order p^{k+1}.
2691
2692        # We keep trying to divide P1 by p.  At each step, if we
2693        # succeed, replace P1 by any of the results and increment n.
2694        # If we fails try again with P1+a*P2 for a in [1..p-1]. If any
2695        # succeed, replace P1 by one of the resulting divided points.
2696        # If all fail, the structure is (p^n,p^k) and P1,P2 are
2697        # generators.
2698
2699        n=k
2700        while True:
2701            P1=pts[0]
2702            n += 1
2703            log_order += 1
2704            if m<=log_order:
2705                return [[P1,n],[P2,k]]
2706            pts = P1.division_points(p)
2707            if len(pts)==0:
2708                for Q in generic.multiples(P2,p-1,P1+P2,operation='+'):
2709                    # Q runs through P1+a*P2 for a=1,2,...,p-1
2710                    pts = Q.division_points(p)
2711                    if len(pts)>0:
2712                        break
2713                if len(pts)==0:
2714                    return [[P1,n],[P2,k]]
2715
2716
2717    def hyperelliptic_polynomials(self):
2718        r"""
2719        Returns a pair of polynomials g(x), h(x) such that this elliptic
2720        curve can be defined by the standard hyperelliptic equation
2721
2722        .. math::
2723
2724            y^2 + h(x)y = g(x).
2725
2726        EXAMPLES::
2727
2728            sage: R.<a1,a2,a3,a4,a6>=QQ[]
2729            sage: E=EllipticCurve([a1,a2,a3,a4,a6])
2730            sage: E.hyperelliptic_polynomials()
2731            (x^3 + a2*x^2 + a4*x + a6, a1*x + a3)
2732        """
2733        K = self.base_ring()
2734        R = PolynomialRing(K, 'x')
2735        x = R.gen(0)
2736        a1, a2, a3, a4, a6 = self.ainvs()
2737        return R([a6, a4, a2, 1]), R([a3, a1])
2738
2739    def pari_curve(self, prec=53):
2740        """
2741        Return the PARI curve corresponding to this elliptic curve.
2742
2743        .. note::
2744
2745           The result is cached; on subsequent calls the cached value
2746           is returned provided that it has sufficient precision,
2747           otherwise pari is called again with the new precision.
2748
2749        EXAMPLES::
2750
2751            sage: E = EllipticCurve([RR(0), RR(0), RR(1), RR(-1), RR(0)])
2752            sage: e = E.pari_curve()
2753            sage: type(e)
2754            <type 'sage.libs.pari.gen.gen'>
2755            sage: e.type()
2756            't_VEC'
2757            sage: e.disc()
2758            37.0000000000000
2759        """
2760        try:
2761            return self._pari_curve
2762        except AttributeError:
2763            pass
2764
2765        from sage.libs.pari.all import pari
2766        self._pari_curve = pari(self.a_invariants()).ellinit(precision=prec)
2767        return self._pari_curve
Note: See TracBrowser for help on using the repository browser.