Sage: Ticket #9409: Bug in elliptic curves method .count_points() over finite fields
https://trac.sagemath.org/ticket/9409
<p>
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...
</p>
<p>
If you want to reproduce the behavior, try the following code:
</p>
<pre class="wiki">### 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)
## the above works fine; the next command will cause the error.
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)
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9409
Trac 1.2John CremonaMon, 05 Jul 2010 16:51:10 GMT
https://trac.sagemath.org/ticket/9409#comment:1
https://trac.sagemath.org/ticket/9409#comment:1
<p>
You do not actually say what the error is -- can you paste in the relevant part of the output?
</p>
<p>
This is one of a number of tickets which claim to be about elliptic curves but are almost certainly about the caching of finite fields (as you suggest). the trouble is that because of this, elliptic curves people (like me) look at the ticket and do nothing, while the finite fields people who need to fix code do not look at it!
</p>
TicketAdam SorkinMon, 05 Jul 2010 19:08:05 GMTkeywords, description changed
https://trac.sagemath.org/ticket/9409#comment:2
https://trac.sagemath.org/ticket/9409#comment:2
<ul>
<li><strong>keywords</strong>
<em>finite</em> <em>fields</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9409?action=diff&version=2">diff</a>)
</li>
</ul>
TicketAdam SorkinMon, 05 Jul 2010 19:09:31 GMTdescription changed
https://trac.sagemath.org/ticket/9409#comment:3
https://trac.sagemath.org/ticket/9409#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9409?action=diff&version=3">diff</a>)
</li>
</ul>
TicketJohn CremonaSat, 14 Aug 2010 16:49:42 GMT
https://trac.sagemath.org/ticket/9409#comment:4
https://trac.sagemath.org/ticket/9409#comment:4
<p>
This should be tested after <a class="closed ticket" href="https://trac.sagemath.org/ticket/9315" title="#9315: defect: sage-4.4.3, 4.4.4: Basic pickling bug in finite fields (closed: fixed)">#9315</a> is in as that may well fix it.
</p>
TicketJohn CremonaSat, 14 Aug 2010 17:15:13 GMTattachment set
https://trac.sagemath.org/ticket/9409
https://trac.sagemath.org/ticket/9409
<ul>
<li><strong>attachment</strong>
set to <em>9409.sage</em>
</li>
</ul>
<p>
Test script
</p>
TicketJohn CremonaSat, 14 Aug 2010 17:21:07 GMT
https://trac.sagemath.org/ticket/9409#comment:5
https://trac.sagemath.org/ticket/9409#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9409#comment:4" title="Comment 4">cremona</a>:
</p>
<blockquote class="citation">
<p>
This should be tested after <a class="closed ticket" href="https://trac.sagemath.org/ticket/9315" title="#9315: defect: sage-4.4.3, 4.4.4: Basic pickling bug in finite fields (closed: fixed)">#9315</a> is in as that may well fix it.
</p>
</blockquote>
<p>
Unfortunately not. After loading the attached script, running either testE() or testF() in a fresh Sage (so no cached fields) works fine, but then running the other one fails (at p=59).
</p>
TicketJohn CremonaSun, 03 Oct 2010 16:32:03 GMTstatus changed
https://trac.sagemath.org/ticket/9409#comment:6
https://trac.sagemath.org/ticket/9409#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
This now seems to work fine (both functions testE() and testF() in the test script now run without errors) in 4.6.alpha2 (not alpha1!).
</p>
<p>
If the reviewer agrees, this can be set to fixed and the closed.
</p>
TicketDavid LoefflerSun, 03 Oct 2010 16:40:32 GMTdescription changed; milestone set
https://trac.sagemath.org/ticket/9409#comment:7
https://trac.sagemath.org/ticket/9409#comment:7
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9409?action=diff&version=7">diff</a>)
</li>
<li><strong>milestone</strong>
set to <em>sage-4.6</em>
</li>
</ul>
<p>
(Editing description because the entire ticket webpage appears stuck in a rogue <code><sup></code> tag!)
</p>
TicketDavid LoefflerSun, 03 Oct 2010 16:44:58 GMTstatus changed; author deleted
https://trac.sagemath.org/ticket/9409#comment:8
https://trac.sagemath.org/ticket/9409#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>author</strong>
<em>Adam Sorkin</em> deleted
</li>
</ul>
<p>
Looks fine to me. I'm flagging this as positive review so the release manager can close it as fixed.
</p>
TicketMitesh PatelMon, 04 Oct 2010 01:28:54 GMTstatus, milestone changed; resolution set
https://trac.sagemath.org/ticket/9409#comment:9
https://trac.sagemath.org/ticket/9409#comment:9
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>worksforme</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-4.6</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
Ticket