Context Navigation

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

Visit:

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
1	r"""
2	Elliptic curves over a general ring.
3
4	Elliptic curves are always represented by 'Weierstrass Models' with
5	five coefficients `[a_1,a_2,a_3,a_4,a_6]` in standard
6	notation. In Magma, 'Weierstrass Model' means a model with
7	a1=a2=a3=0, which is called 'Short Weierstrass Model' in Sage;
8	these only exist in characteristics other than 2 and 3.
9
10	EXAMPLES:
11
12	We 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
23	AUTHORS:
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
47	import math
48
49	from sage.rings.all import PolynomialRing, polygen
50	import sage.groups.abelian_gps as groups
51	import sage.groups.generic as generic
52	import sage.plot.all as plot
53
54	import sage.rings.arith as arith
55	import sage.rings.all as rings
56	import sage.rings.number_field as number_field
57	from sage.rings.number_field.all import is_NumberField
58	from sage.rings.all import is_Infinite
59	import sage.misc.misc as misc
60	import sage.misc.latex as latex
61	import sage.modular.modform as modform
62	import sage.functions.transcendental as transcendental
63
64	from sage.categories.morphism import IdentityMorphism
65	from sage.categories.homset import Hom
66	from sage.rings.arith import lcm
67
68	# Schemes
69	import sage.schemes.generic.projective_space as projective_space
70	import sage.schemes.generic.homset as homset
71
72	import ell_point
73	import ell_torsion
74	import constructor
75	import formal_group
76	import weierstrass_morphism as wm
77	from constructor import EllipticCurve
78
79
80	factor = arith.factor
81	sqrt = math.sqrt
82	exp = math.exp
83	mul = misc.mul
84	next_prime = arith.next_prime
85
86	oo = rings.infinity # infinity
87	O = rings.O # big oh
88
89	import sage.schemes.plane_curves.projective_curve as plane_curve
90
91	def 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
106	class 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 + xy + 3/4y = x^3 + 2x^2 + 7x + 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 + xy + 3y = x^3 + 2x^2 + 4x + 5 over Rational Field
138	sage: E = EllipticCurve(GF(7),[1,2,3,4,5]); E
139	Elliptic Curve defined by y^2 + xy + 3y = x^3 + 2x^2 + 4x + 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 + xy + 3y = x^3 + 2x^2 + 4x + 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*2z + (a1x + a3z)yz \
168	- (x*3 + a2x*2z + a4xz*2 + a6z**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 + xy + 3y = x^3 + 2x^2 + 4x + 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/3a+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 + %sxy + %sy = x^3 + %sx^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 += "+ %sxy "%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/2xy - 4/5y = x^3 + 2/3x^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/2sqrt(4x^3 - 4x^2 - 40x - 79) - 1/2,
377	y == 1/2sqrt(4x^3 - 4x^2 - 40x - 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/2sqrt(4x^3 - 4x^2 - 40x - 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/2sqrt(-32sqrt(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/2sqrt(-40pi + 4pi^3 - 4pi^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	(-2pi + (2pi - 3pi^2 + 10)^2/(-40pi + 4pi^3 - 4pi^2 - 79) + 1 : (2pi - 3pi^2 + 10)(3pi - (2pi - 3pi^2 + 10)^2/(-40pi + 4pi^3 - 4pi^2 - 79) - 1)/sqrt(-40pi + 4pi^3 - 4pi^2 - 79) + 1/2sqrt(-40pi + 4pi^3 - 4pi^2 - 79) - 1/2 : 1)
414
415	sage: x, y, z = 2w; temp = ((y^2 + y) - (x^3 - x^2 - 10x - 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]xy + 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]xy + 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+23+23^2+23^3+23^4+23^5+23^6+23^7+23^8+23^9+23^10+23^11+23^12+23^13+23^14+23^15+23^16+23^17+23^18+23^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))([xd, yd, 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 = bb + 4fx
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 + 1617 + 1617^2 + 1617^3 + 1617^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 : 2t - t^2 + 5t^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 = bb + 4f
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]xy + 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 = a1a1 + 4a2, \
1045	a1a3 + 2a4, \
1046	a3*2 + 4a6, \
1047	a1*2 a6 + 4a2a6 - a1a3a4 + a2a32 - 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 - 24b4,\
1140	-b2*3 + 36b2b4 - 216b6 # 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*2b8 - 8b43 - 27b6*2 + 9b2b4b6
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 + (4b^3+4b^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 + (2s+1)xy + (r+2t+3)y = x^3 + (-s^2+3r-s+2)x^2 + (3r^2-rs-2st+4r-3s-t+4)x + (r^3+2r^2-rt-t^2+4r-3t+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 + uxy + 3u^3y = x^3 + 2u^2x^2 + 4u^4x + 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*2b8 - 8b43 - 27b6*2 + 9b2b4b6
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	3x^4 - 6x^2 + 3*x - 1
1538	sage: E.division_polynomial_0(4)
1539	2x^6 - 10x^4 + 10x^3 - 10x^2 + 2*x + 1
1540	sage: E.division_polynomial_0(5)
1541	5x^12 - 62x^10 + 95x^9 - 105x^8 - 60x^7 + 285x^6 - 174x^5 - 5x^4 - 5x^3 + 35x^2 - 15*x + 2
1542	sage: E.division_polynomial_0(6)
1543	3x^16 - 72x^14 + 168x^13 - 364x^12 + 1120x^10 - 1144x^9 + 300x^8 - 540x^7 + 1120x^6 - 588x^5 - 133x^4 + 252x^3 - 114x^2 + 22x - 1
1544	sage: E.division_polynomial_0(7)
1545	7x^24 - 308x^22 + 986x^21 - 2954x^20 + 28x^19 + 17171x^18 - 23142x^17 + 511x^16 - 5012x^15 + 43804x^14 - 7140x^13 - 96950x^12 + 111356x^11 - 19516x^10 - 49707x^9 + 40054x^8 - 124x^7 - 18382x^6 + 13342x^5 - 4816x^4 + 1099x^3 - 210x^2 + 35*x - 3
1546	sage: E.division_polynomial_0(8)
1547	4x^30 - 292x^28 + 1252x^27 - 5436x^26 + 2340x^25 + 39834x^24 - 79560x^23 + 51432x^22 - 142896x^21 + 451596x^20 - 212040x^19 - 1005316x^18 + 1726416x^17 - 671160x^16 - 954924x^15 + 1119552x^14 + 313308x^13 - 1502818x^12 + 1189908x^11 - 160152x^10 - 399176x^9 + 386142x^8 - 220128x^7 + 99558x^6 - 33528x^5 + 6042x^4 + 310x^3 - 406x^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	5x^12 + x^9 + 8x^6 + 4*x^3 + 7
1561	sage: f.factor()
1562	(5) * (x^2 + 5) * (x^2 + 2x + 5) (x^2 + 5x + 7) (x^2 + 7x + 7) (x^2 + 9x + 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	[10a^3 + 4a^2 + 5*a + 6,
1573	9a^3 + 8a^2 + 10*a + 8,
1574	8a^3 + a^2 + 4a + 10,
1575	8a^3 + a^2 + 4a + 8,
1576	8a^3 + a^2 + 4a + 4,
1577	6a^3 + 9a^2 + 3*a + 4,
1578	5a^3 + 2a^2 + 8*a + 7,
1579	3a^3 + 10a^2 + 7*a + 8,
1580	3a^3 + 10a^2 + 7*a + 3,
1581	3a^3 + 10a^2 + 7*a + 1,
1582	2a^3 + 3a^2 + a + 7,
1583	a^3 + 7a^2 + 6a]
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 = 4x3 + b2x*2 + 2b4*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 = 3x4 + b2x*3 + 3b4x2 + 3b6*x + b8
1637	elif n == 4:
1638	answer = -self.division_polynomial_0(-2, x, cache) + \
1639	(6x2 + b2x + 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	4x^3 - 28x + 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	`2y+a1x+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	4x^3 - 4x + 1
1750	sage: E.division_polynomial(2)
1751	4x^3 - 4x + 1
1752	sage: [E.division_polynomial(3, two_torsion_multiplicity=i) for i in range(3)]
1753	[3x^4 - 6x^2 + 3x - 1, 3x^4 - 6x^2 + 3x - 1, 3x^4 - 6x^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	2z^6 - 4z^5 - 100z^4 - 790z^3 - 210z^2 - 1496z - 5821
1765	sage: E.division_polynomial(4,z)
1766	8z^9 - 24z^8 - 464z^7 - 2758z^6 + 6636z^5 + 34356z^4 + 53510z^3 + 99714z^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	(2w + 1) (2z^6 - 4z^5 - 100z^4 - 790z^3 - 210z^2 - 1496z - 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 = (2y+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(n , 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 + 2x^2 - 24x + 1)/(4x^3 - 4x + 12), (8x^6y - 40x^4y + 480x^3y - 40x^2y + 96xy - 568y)/(64x^6 - 128x^4 + 384x^3 + 64x^2 - 384x + 576))
2045
2046	Grab only the x-coordinate (less work)::
2047
2048	sage: E.multiplication_by_m(2, x_only=True)
2049	(x^4 + 2x^2 - 24x + 1)/(4x^3 - 4x + 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/(2y+a1x+a3) shows that mw = d(mx)/(2my+a1*mx+a3)
2133	# and hence 2my+a1mx+a3 = (1/m)(2y+a1x+a3)d(mx)/dx
2134
2135	my = ((2y+a1x+a3)mx.derivative(x)/m - a1mx-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: 120w(P) == w(120P)
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 + 4xy + 11/8y = x^3 - 3/2x^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 + 2xy + 8y = x^3 + 4x^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/21xy + 13/343y = x^3 + 59/441x^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 + xy + 3y = x^3 + 2x^2 + 4x + 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 + 9x^2 + 88x + 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 + 2x^2 + 2x + 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 + 2x^2 + 2x + 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,8b4,16b6])
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,8b4,16b6])
2436	else:
2437	c4, c6 = self.c_invariants()
2438	return constructor.EllipticCurve([0,0,0,-27c4, -54c6])
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,8b4,16b6])
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 = 4x3 + (a12 + 4a2)x2 + (2a3a1 + 4a4)x + (a32 + 4a6)
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 + 11x^2 + 41x + 101)
2577	sage: EK=E.base_extend(K)
2578	sage: EK._p_primary_torsion_basis(5)
2579	[[(16 : 60 : 1), 1], [(t : 1/11t^3 + 6/11t^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 - 2z^7 + z^6 + 2z^5 - 3z^4 + 2z^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 + a2x^2 + a4x + 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.

Download in other formats: