Opened 12 years ago

Closed 11 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)

sage-3111.patch (5.8 KB) - added by cremona 12 years ago.
sage-3111-extra.patch (1.6 KB) - added by cremona 12 years ago.
Additional tp sage-3111.patch
sage-3111-extra2.patch (1.3 KB) - added by cremona 12 years ago.
Apply after previous two
sage-3111-extra3.patch (1022 bytes) - added by cremona 12 years ago.
apply after all previous

Download all attachments as: .zip

Change History (24)

comment:1 Changed 12 years ago by was

  • Priority changed from major to critical

Under OS X (10.5.1 intel core2 duo with 2GB RAM) I also get a repeatable massive memory overflow that completely crashes Sage:

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$ 

Running this under gdb yields nothing useful:

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.

comment:2 Changed 12 years ago by was

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 12 years ago by mabshoff

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 12 years ago by cremona

  • 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 12 years ago by cremona

  • 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 for GF(p^k) up to 10^3 for k=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 12 years ago by craigcitro

Hmm ... there doesn't seem to be a patch attached, despite the title saying "with patch." :)

Changed 12 years ago by cremona

comment:7 Changed 12 years ago by cremona

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 12 years ago by broune

  • 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 12 years ago by craigcitro

I think that we should also add at least one doctest showing that this behavior is fixed.

Changed 12 years ago by cremona

Additional tp sage-3111.patch

comment:10 follow-up: Changed 12 years ago by 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.

comment:11 follow-up: Changed 12 years ago by 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?

comment:12 in reply to: ↑ 10 Changed 12 years ago by mabshoff

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 12 years ago by mabshoff

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

Changed 12 years ago by cremona

Apply after previous two

comment:14 Changed 12 years ago by cremona

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 12 years ago by cremona

If you still want the long test (all primes to 10000) I can add it tomorrow -- my bedtime now.

comment:16 Changed 12 years ago by broune

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.

Changed 12 years ago by cremona

apply after all previous

comment:17 Changed 12 years ago by cremona

  • 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 12 years ago by cremona

  • 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 11 years ago by craigcitro

  • 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 11 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from assigned to closed

Finally! Merged all four patches in Sage 3.0.3.alpha1

Note: See TracTickets for help on using tickets.