Opened 13 years ago
Closed 12 years ago
#3111 closed defect (fixed)
[with new patches, with positive review] Two bug fixes for elliptic curve abelian_group()
Reported by: | was | Owned by: | cremona |
---|---|---|---|
Priority: | critical | Milestone: | sage-3.0.3 |
Component: | number theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Paste this code into a Sage session:
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
The output varies on run and computer. Typical output looks like this:
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
The actual failures are assertion failures in the baby-step giant-step implementation.
-- William
Attachments (4)
Change History (24)
comment:1 Changed 13 years ago by
- Priority changed from major to critical
comment:2 Changed 13 years ago by
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.
comment:3 Changed 13 years ago by
With Sage 3.0.1 on sage.math this seems rather harmless:
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
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 .....
Cheers,
Michael
comment:4 Changed 13 years ago by
- Status changed from new to assigned
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.
comment:5 Changed 13 years ago by
- Summary changed from sage's new baby-step giant step evidently needs additional polish to [with patch, needs review] Two bug fixes for elliptic curve abelian_group()
Two bugs fixed:
- A stupid rounding error in
ell_generic.Hasse_bounds()
[NB the floor of 2*sqrt(q) is not 2*floor(sqrt(q))!]
- 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
10***5
and forGF(p^k)
up to10^3
fork=2,3,4,5
.
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 (sqrt(q)-1)**2
or (sqrt(q)+1)**2
.)
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.
comment:6 Changed 13 years ago by
Hmm ... there doesn't seem to be a patch attached, despite the title saying "with patch." :)
Changed 13 years ago by
comment:7 Changed 13 years ago by
Sorry about that, it is there now.
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.
comment:8 Changed 13 years ago by
- Summary changed from [with patch, needs review] Two bug fixes for elliptic curve abelian_group() to [with patch, positive review pending changes] Two bug fixes for elliptic curve abelian_group()
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.
comment:9 Changed 13 years ago by
I think that we should also add at least one doctest showing that this behavior is fixed.
comment:10 follow-up: ↓ 12 Changed 13 years ago by
sage-3111-extra.patch does the following:
- deleted two debuggin print lines
- added doctest to show that the original post is fixed
- passes all doctests in sage/schemes/elliptic_curves
For the doctest I check that it is OK for 10 random primes up to 10^4
rather than all of them since that takes about 18s to run.
comment:11 follow-up: ↓ 13 Changed 13 years ago by
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?
comment:12 in reply to: ↑ 10 Changed 13 years ago by
Replying to cremona:
sage-3111-extra.patch does the following:
- deleted two debuggin print lines
- added doctest to show that the original post is fixed
- passes all doctests in sage/schemes/elliptic_curves
For the doctest I check that it is OK for 10 random primes up to
10^4
rather than all of them since that takes about 18s to run.
Hi John,
you could do two tests:
- a quick one that is run per default
- a long one marked with
#long
- 18 seconds is not a problem with long.
Cheers,
Michael
comment:13 in reply to: ↑ 11 Changed 13 years ago by
Replying to broune:
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?
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 #random
in the doctest string.
Cheers,
Michael
comment:14 Changed 13 years ago by
Michael,
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!)
John
comment:15 Changed 13 years ago by
If you still want the long test (all primes to 10000) I can add it tomorrow -- my bedtime now.
comment:16 Changed 13 years ago by
Sorry about the misinformation on random - it is good that Sage handles this nicely.
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.
comment:17 Changed 13 years ago by
- Summary changed from [with patch, positive review pending changes] Two bug fixes for elliptic curve abelian_group() to [with new patches, needs minimal further review] Two bug fixes for elliptic curve abelian_group()
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.
Apologies for the succession of small cumulative patches, Michael: I only trust myself to do hg_sage.export("tip")
.
comment:18 Changed 13 years ago by
- Summary changed from [with new patches, needs minimal further review] Two bug fixes for elliptic curve abelian_group() to [with new patches, needs review (quick)] Two bug fixes for elliptic curve abelian_group()
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.
comment:19 Changed 13 years ago by
- Summary changed from [with new patches, needs review (quick)] Two bug fixes for elliptic curve abelian_group() to [with new patches, with positive review] Two bug fixes for elliptic curve abelian_group()
This looks good. (I don't know how this slipped under the radar as long as it did.)
comment:20 Changed 12 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Finally! Merged all four patches in Sage 3.0.3.alpha1
Under OS X (10.5.1 intel core2 duo with 2GB RAM) I also get a repeatable massive memory overflow that completely crashes Sage:
Running this under gdb yields nothing useful: