#9409: Bug in elliptic curves method .count_points() over finite fields
-------------------------------+--------------------------------------------
Reporter: adam | Owner: cremona
Type: defect | Status: new
Priority: major | Milestone:
Component: elliptic curves | Keywords: Elliptic Curves .count_points()
finite fields
Author: Adam Sorkin | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by adam):
* keywords: Elliptic Curves .count_points() => Elliptic Curves
.count_points() finite fields
Old description:
> There is some bug in the method .count_points() which belongs to elliptic
> curves defined over finite fields. This might be specific to EC defined
> over number fields - I only get this error when I take an EC over a
> number field, reduce at a good prime and then count points. In fact, I
> get the correct answer the first time, but if I define a second EC over a
> possibly different number field and count points at a good reduction,
> then the method .count_points() fails. I suspect this has to do with the
> cacheing...
>
> If you want to reproduce the behavior, try the following code:
>
> ### this just runs through the method outlined above:
>
> def test(curve, bound):
> for i in primes(bound):
> print "Checking primes over %d: "%i
> factors = curve.base_field().ideal(i).factor()
> for j in range(len(factors)):
> if curve.has_good_reduction(factors[j][0]):
> if factors[j][0].divides(curve.discriminant()):
> print "Curve has good reduction, but this isn't not a
> minimal model",
> print "at %s with %d points in the reduced
> curve"%(factors[j][0],
> curve.local_minimal_model(factors[j][0]).reduction(factors[j][0]).count_points()
> )
> else:
> print "Curve has good reduction and is a minimal
> model"
> print "at %s with %d points in the reduced
> curve"%(factors[j][0], curve.reduction(factors[j][0]).count_points() )
> else:
> print "Curve has bad reduction over %s"%factors[j][0]
> return
>
> ### sample 1
> K.<t> = NumberField(x^2 + 1); E = EllipticCurve(K, [0, 1, 0, -2*t - 2,
> 2*t]); E
> ### sample 2
> L.<u> = NumberField(x^2 - 2); F = EllipticCurve(L, [0,2,0, 2*u +4, 2*u +
> 3]); F
>
> test(E, 100)
>
> ## now the error will happen
> test(F, 100)
New description:
There is some bug in the method .count_points() which belongs to elliptic
curves defined over finite fields. This might be specific to EC defined
over number fields - I only get this error when I take an EC over a number
field, reduce at a good prime and then count points. In fact, I get the
correct answer the first time, but if I define a second EC over a possibly
different number field and count points at a good reduction, then the
method .count_points() fails. I suspect this has to do with the
cacheing...
If you want to reproduce the behavior, try the following code:
### this just runs through the method outlined above:
def test(curve, bound):
for i in primes(bound):
print "Checking primes over %d: "%i
factors = curve.base_field().ideal(i).factor()
for j in range(len(factors)):
if curve.has_good_reduction(factors[j][0]):
if factors[j][0].divides(curve.discriminant()):
print "Curve has good reduction, but this isn't not a
minimal model",
print "at %s with %d points in the reduced
curve"%(factors[j][0],
curve.local_minimal_model(factors[j][0]).reduction(factors[j][0]).count_points()
)
else:
print "Curve has good reduction and is a minimal
model"
print "at %s with %d points in the reduced
curve"%(factors[j][0], curve.reduction(factors[j][0]).count_points() )
else:
print "Curve has bad reduction over %s"%factors[j][0]
return
### sample 1
K.<t> = NumberField(x^2 + 1); E = EllipticCurve(K, [0, 1, 0, -2*t - 2,
2*t]); E
### sample 2
L.<u> = NumberField(x^2 - 2); F = EllipticCurve(L, [0,2,0, 2*u +4, 2*u +
3]); F
test(E, 100)
## now the error will happen
test(F, 100)
You will get the correct output for the first few primes, but the error
message, which in the above case occurs above the prime ideal (67), is
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "_sage_input_8.py", line 10, in <module>
exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8
-*-\\n" +
_support_.preparse_worksheet_cell(base64.b64decode("dGVzdChGLCAxMDAp"),globals())+"\\n");
execfile(os.path.abspath("___code___.py"))
File "", line 1, in <module>
File "/tmp/tmpVYbgxh/___code___.py", line 3, in <module>
exec compile(u'test(F, _sage_const_100 )
File "", line 1, in <module>
File "/tmp/tmptawaYw/___code___.py", line 14, in test
print "at %s with %d points in the reduced
curve"%(factors[j][_sage_const_0 ],
curve.reduction(factors[j][_sage_const_0 ]).count_points() )
File "/usr/local/sage2/local/lib/python2.6/site-
packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 322, in
count_points
return self.cardinality()
File "/usr/local/sage2/local/lib/python2.6/site-
packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 951, in
cardinality
self._order = self.cardinality_bsgs()
File "/usr/local/sage2/local/lib/python2.6/site-
packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 1220, in
cardinality_bsgs
N1 = ZZ(2)**sum([e for P,e in E1._p_primary_torsion_basis(2)])
File "/usr/local/sage2/local/lib/python2.6/site-
packages/sage/schemes/elliptic_curves/ell_generic.py", line 2660, in
_p_primary_torsion_basis
Ep = self(0).division_points(p)
File "/usr/local/sage2/local/lib/python2.6/site-
packages/sage/schemes/elliptic_curves/ell_point.py", line 879, in
division_points
Q = E.lift_x(x)
File "/usr/local/sage2/local/lib/python2.6/site-
packages/sage/schemes/elliptic_curves/ell_generic.py", line 855, in lift_x
raise ValueError, "No point with x-coordinate %s on %s"%(x, self)
ValueError: No point with x-coordinate 39*tbar + 11 on Elliptic Curve
defined by y^2 = x^3 + 2*x^2 + (2*ubar+4)*x + (2*ubar+3) over Residue
field in ubar of Fractional ideal (67)
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9409#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
