Sage: Ticket #3111: [with new patches, with positive review] Two bug fixes for elliptic curve abelian_group()
https://trac.sagemath.org/ticket/3111
<p>
Paste this code into a Sage session:
</p>
<pre class="wiki">E = EllipticCurve('389a')
for p in prime_range(10000):
if p != 389:
try:
G = E.change_ring(GF(p)).abelian_group()
except Exception, msg:
print "p = %s fails"%p
print msg
</pre><p>
The output varies on run and computer. Typical output looks like this:
</p>
<pre class="wiki">p = 7 fails
No solution in bsgs()
p = 1901 fails
p = 4273 fails
p = 5101 fails
p = 7177 fails
p = 7433 fails
p = 9013 fails
p = 9049 fails
p = 9749 fails
</pre><p>
The actual failures are assertion failures in the baby-step giant-step implementation.
</p>
<blockquote>
<p>
-- William
</p>
</blockquote>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/3111
Trac 1.1.6wasTue, 06 May 2008 16:10:14 GMTpriority changed
https://trac.sagemath.org/ticket/3111#comment:1
https://trac.sagemath.org/ticket/3111#comment:1
<ul>
<li><strong>priority</strong>
changed from <em>major</em> to <em>critical</em>
</li>
</ul>
<p>
Under OS X (10.5.1 intel core2 duo with 2GB RAM)
I also get a repeatable massive memory overflow that completely crashes Sage:
</p>
<pre class="wiki">sage: E = EllipticCurve('389a')
sage: for p in prime_range(10000):
....: if p != 389:
....: try:
....: G = E.change_ring(GF(p)).abelian_group()
....: except Exception, msg:
....: print "p = %s fails"%p
....: print msg
....:
p = 7 fails
No solution in bsgs()
p = 523 fails
p = 2477 fails
p = 3001 fails
p = 3449 fails
error: no more memory
System 5120k:5120k Appl 4637k/482k Malloc 4094k/1k Valloc 1024k/480k Pages 152/104 Regions 2:2
halt 14
teragon-2:sage-3.0.1 was$
</pre><p>
Running this under gdb yields nothing useful:
</p>
<pre class="wiki">
error: no more memory
System 5116k:5116k Appl 4629k/486k Malloc 4086k/5k Valloc 1024k/481k Pages 152/104 Regions 2:2
halt 14
Program exited with code 016.
(gdb) bt
No stack.
</pre>
TicketwasTue, 06 May 2008 16:11:19 GMT
https://trac.sagemath.org/ticket/3111#comment:2
https://trac.sagemath.org/ticket/3111#comment:2
<p>
NOte -- the above is not a leak between calls of abelian_group. It's that one single calculation is somehow using up all memory and crashing sage.
</p>
TicketmabshoffTue, 06 May 2008 17:14:09 GMT
https://trac.sagemath.org/ticket/3111#comment:3
https://trac.sagemath.org/ticket/3111#comment:3
<p>
With Sage 3.0.1 on sage.math this seems rather harmless:
</p>
<pre class="wiki"> PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
28670 mabshoff 20 0 455m 141m 21m S 0 0.2 0:35.02 sage-ipython
29958 mabshoff 15 0 97.7m 24m 2060 S 0 0.0 0:03.67 python
28715 mabshoff 16 0 634m 14m 2096 S 0 0.0 0:02.27 gp
</pre><p>
If for some dumb reason pari doubles the stack once more on OSX you are SOL. I tried on OSX 10.5 and I hit the same error. Now it sounds like a 64 bit OSX version of Sage would fix that issue, but .....
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketcremonaTue, 06 May 2008 21:07:45 GMTstatus changed
https://trac.sagemath.org/ticket/3111#comment:4
https://trac.sagemath.org/ticket/3111#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>assigned</em>
</li>
</ul>
<p>
I found the bug which causes this. It is not in any of the generic code at all, but in some lines I added quite late on in ell_finite_field.py to make one step (in code which happens relatively infrequently) "more efficient". I'll post a patch on Wednesday.
</p>
TicketcremonaWed, 07 May 2008 10:12:22 GMTsummary changed
https://trac.sagemath.org/ticket/3111#comment:5
https://trac.sagemath.org/ticket/3111#comment:5
<ul>
<li><strong>summary</strong>
changed from <em>sage's new baby-step giant step evidently needs additional polish</em> to <em>[with patch, needs review] Two bug fixes for elliptic curve abelian_group()</em>
</li>
</ul>
<p>
Two bugs fixed:
</p>
<ul><li>A stupid rounding error in <code>ell_generic.Hasse_bounds()</code> [NB the floor of 2*sqrt(q) is not 2*floor(sqrt(q))!]
</li></ul><ul><li>A more subtle bug in the abelian_group() function for curves over finite fields, in a bit of code added late on for "efficiency". We now still have the efficiency but without the bug (at least, not that one). The code in the original post now runs fine; I also ran it up to <code>10***5</code> and for <code>GF(p^k)</code> up to <code>10^3</code> for <code>k=2,3,4,5</code>.
</li></ul><p>
For the future: I still have some more plans for ell_finite_field in cases where j is not in the prime field. Then, at present the only way we have to compute the cardinality is via the group structure, but for the majority of cases it should be easier to compute the cardinality only using Mestre's trick. However, Mestre's trick (as stated and proved by Schoof's second JNTB paper) is usually stated over prime fields, and over non-prime fields of square size there is one situation where Mestre's trick does not work (specifically when q is a square and the Frobenius is an integer and the group order (and structure) is either <code>(sqrt(q)-1)**2</code> or <code>(sqrt(q)+1)**2</code>.)
</p>
<p>
When I have worked out how best to detect that case there will be a new patch. Until then, curves whose j is not in the prime field and which do not have cyclic groups run into the efficiency problem (fixed above but only when the cardinality is already known) where some rather large elliptic curve discrete logs may need to be computed.
</p>
TicketcraigcitroThu, 08 May 2008 21:23:04 GMT
https://trac.sagemath.org/ticket/3111#comment:6
https://trac.sagemath.org/ticket/3111#comment:6
<p>
Hmm ... there doesn't seem to be a patch attached, despite the title saying "with patch." :)
</p>
TicketcremonaThu, 08 May 2008 21:24:15 GMTattachment set
https://trac.sagemath.org/ticket/3111
https://trac.sagemath.org/ticket/3111
<ul>
<li><strong>attachment</strong>
set to <em>sage-3111.patch</em>
</li>
</ul>
TicketcremonaThu, 08 May 2008 21:26:16 GMT
https://trac.sagemath.org/ticket/3111#comment:7
https://trac.sagemath.org/ticket/3111#comment:7
<p>
Sorry about that, it is there now.
</p>
<p>
And as I looked at the patch after uploading it I saw that there are a couple of debugging print statements which need deleting, near the end (lines 1194/5) but I'll leave that until tomorrow.
</p>
TicketbrouneMon, 12 May 2008 10:37:05 GMTsummary changed
https://trac.sagemath.org/ticket/3111#comment:8
https://trac.sagemath.org/ticket/3111#comment:8
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Two bug fixes for elliptic curve abelian_group()</em> to <em>[with patch, positive review pending changes] Two bug fixes for elliptic curve abelian_group()</em>
</li>
</ul>
<p>
Doctests pass in ell_generic.py and ell_finite_field. No more printed failues when running code in ticket description (they were there before I applied the paths), though I also run out of memory on mac 10.5 with 2 GB ram. If this is not expected behavior it should be reported as a separate ticket. Positive review pending removal of debugging print statements.
</p>
TicketcraigcitroMon, 12 May 2008 16:35:25 GMT
https://trac.sagemath.org/ticket/3111#comment:9
https://trac.sagemath.org/ticket/3111#comment:9
<p>
I think that we should also add at least one doctest showing that this behavior is fixed.
</p>
TicketcremonaMon, 12 May 2008 21:24:26 GMTattachment set
https://trac.sagemath.org/ticket/3111
https://trac.sagemath.org/ticket/3111
<ul>
<li><strong>attachment</strong>
set to <em>sage-3111-extra.patch</em>
</li>
</ul>
<p>
Additional tp sage-3111.patch
</p>
TicketcremonaMon, 12 May 2008 21:29:57 GMT
https://trac.sagemath.org/ticket/3111#comment:10
https://trac.sagemath.org/ticket/3111#comment:10
<p>
sage-3111-extra.patch does the following:
</p>
<ul><li>deleted two debuggin print lines
</li><li>added doctest to show that the original post is fixed
</li><li>passes all doctests in sage/schemes/elliptic_curves
</li></ul><p>
For the doctest I check that it is OK for 10 random primes up to <code>10^4</code> rather than all of them since that takes about 18s to run.
</p>
TicketbrouneMon, 12 May 2008 21:38:59 GMT
https://trac.sagemath.org/ticket/3111#comment:11
https://trac.sagemath.org/ticket/3111#comment:11
<p>
I would prefer to use 10 specific primes, as using random primes gives unrepeatable results. Unless Sage does something like reset the random seed before each test?
</p>
TicketmabshoffMon, 12 May 2008 21:41:36 GMT
https://trac.sagemath.org/ticket/3111#comment:12
https://trac.sagemath.org/ticket/3111#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/3111#comment:10" title="Comment 10">cremona</a>:
</p>
<blockquote class="citation">
<p>
sage-3111-extra.patch does the following:
</p>
<ul><li>deleted two debuggin print lines
</li><li>added doctest to show that the original post is fixed
</li><li>passes all doctests in sage/schemes/elliptic_curves
</li></ul><p>
For the doctest I check that it is OK for 10 random primes up to <code>10^4</code> rather than all of them since that takes about 18s to run.
</p>
</blockquote>
<p>
Hi John,
</p>
<p>
you could do two tests:
</p>
<ul><li>a quick one that is run per default
</li><li>a long one marked with <code>#long</code> - 18 seconds is not a problem with long.
</li></ul><p>
Cheers,
</p>
<p>
Michael
</p>
TicketmabshoffMon, 12 May 2008 21:43:07 GMT
https://trac.sagemath.org/ticket/3111#comment:13
https://trac.sagemath.org/ticket/3111#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/3111#comment:11" title="Comment 11">broune</a>:
</p>
<blockquote class="citation">
<p>
I would prefer to use 10 specific primes, as using random primes gives unrepeatable results. Unless Sage does something like reset the random seed before each test?
</p>
</blockquote>
<p>
Sage now uses the same seed per default for randomness at the start of each doctest, so it is reproducible. Not all sources of randomness have that property yet, but for primes it should work. So no need to stick <code>#random</code> in the doctest string.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketcremonaMon, 12 May 2008 21:47:04 GMTattachment set
https://trac.sagemath.org/ticket/3111
https://trac.sagemath.org/ticket/3111
<ul>
<li><strong>attachment</strong>
set to <em>sage-3111-extra2.patch</em>
</li>
</ul>
<p>
Apply after previous two
</p>
TicketcremonaMon, 12 May 2008 21:49:53 GMT
https://trac.sagemath.org/ticket/3111#comment:14
https://trac.sagemath.org/ticket/3111#comment:14
<p>
Michael,
</p>
<p>
I have added an extra patch anyway -- my comment on it was killed by trac as you were editing at the same time )I thought trac would be cleverer than that!)
</p>
<p>
John
</p>
TicketcremonaMon, 12 May 2008 21:51:09 GMT
https://trac.sagemath.org/ticket/3111#comment:15
https://trac.sagemath.org/ticket/3111#comment:15
<p>
If you still want the long test (all primes to 10000) I can add it tomorrow -- my bedtime now.
</p>
TicketbrouneMon, 12 May 2008 21:51:36 GMT
https://trac.sagemath.org/ticket/3111#comment:16
https://trac.sagemath.org/ticket/3111#comment:16
<p>
Sorry about the misinformation on random - it is good that Sage handles this nicely.
</p>
<p>
Runnning the doctest code for the 10 primes with an unpatched Sage does not trigger the bug after I tried it a few times on my machine. Ten primes just does not seem to be enough to hit the bug with high probability. It would be better to find some primes that always trigger the bug. I get different numbers failing on each run, except that 7 seems to show up every time. So it would be nice to check p=7 every time in the doctest, in addition to the random tests.
</p>
TicketcremonaTue, 13 May 2008 08:18:56 GMTattachment set
https://trac.sagemath.org/ticket/3111
https://trac.sagemath.org/ticket/3111
<ul>
<li><strong>attachment</strong>
set to <em>sage-3111-extra3.patch</em>
</li>
</ul>
<p>
apply after all previous
</p>
TicketcremonaTue, 13 May 2008 08:22:11 GMTsummary changed
https://trac.sagemath.org/ticket/3111#comment:17
https://trac.sagemath.org/ticket/3111#comment:17
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, positive review pending changes] Two bug fixes for elliptic curve abelian_group()</em> to <em>[with new patches, needs minimal further review] Two bug fixes for elliptic curve abelian_group()</em>
</li>
</ul>
<p>
Yet another patch sage-3111-extra3.patch now tests the original full code for primes to 10000 but this longer test is marked #long as it takes around 20s.
</p>
<p>
Apologies for the succession of small cumulative patches, Michael: I only trust myself to do <code>hg_sage.export("tip")</code>.
</p>
TicketcremonaWed, 14 May 2008 21:45:49 GMTsummary changed
https://trac.sagemath.org/ticket/3111#comment:18
https://trac.sagemath.org/ticket/3111#comment:18
<ul>
<li><strong>summary</strong>
changed from <em>[with new patches, needs minimal further review] Two bug fixes for elliptic curve abelian_group()</em> to <em>[with new patches, needs review (quick)] Two bug fixes for elliptic curve abelian_group()</em>
</li>
</ul>
<p>
The phrase "needs minimal further review" resulted in this one not being listed by trac as a "needs review" ticket so I have changed that and hope that someone can oblige. The extra patches do what was wanted by the orginal reviewer.
</p>
TicketcraigcitroMon, 02 Jun 2008 07:59:18 GMTsummary changed
https://trac.sagemath.org/ticket/3111#comment:19
https://trac.sagemath.org/ticket/3111#comment:19
<ul>
<li><strong>summary</strong>
changed from <em>[with new patches, needs review (quick)] Two bug fixes for elliptic curve abelian_group()</em> to <em>[with new patches, with positive review] Two bug fixes for elliptic curve abelian_group()</em>
</li>
</ul>
<p>
This looks good. (I don't know how this slipped under the radar as long as it did.)
</p>
TicketmabshoffWed, 04 Jun 2008 18:54:32 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/3111#comment:20
https://trac.sagemath.org/ticket/3111#comment:20
<ul>
<li><strong>status</strong>
changed from <em>assigned</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Finally! Merged all four patches in Sage 3.0.3.alpha1
</p>
Ticket