Opened 9 years ago

Closed 9 years ago

#10590 closed defect (fixed)

Saturation of elliptic curve points can cause an infinite loop

Reported by: cremona Owned by: cremona
Priority: major Milestone: sage-4.6.2
Component: elliptic curves Keywords: saturation
Cc: rlm, was Merged in: sage-4.6.2.alpha2
Authors: John Cremona Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:


Possibly related to #9247.

The method saturation() for sets of points on elliptic curves over Q calls eclib in a loop which is optimistically headed "while True:". Unfortunately this really can cause infinite looping. Here's an example (the curve has conductor 130017):

E = EllipticCurve([1, 0, 1, -977842, -372252745])
P = E([-192128125858676194585718821667542660822323528626273/336995568430319276695106602174283479617040716649, 70208213492933395764907328787228427430477177498927549075405076353624188436/195630373799784831667835900062564586429333568841391304129067339731164107, 1])
E.saturation([P]) ## OK, saturated
E.saturation([2*P]) ## loops!

The problem is that there are various different ways in which the saturation inside the loop (line 2097 of can fail, and one -- probably the one here -- is due to a lack of precision. I will look into how to increase the precision used in eclib from Sage. (In this example, after mwrank_set_precision(200) it works fine, but not with 150.)

Attachments (1)

trac_10590-precision.patch (8.2 KB) - added by cremona 9 years ago.
Applies to 4.6.2.alpha0

Download all attachments as: .zip

Change History (12)

comment:1 Changed 9 years ago by cremona

  • Cc was added
  • Status changed from new to needs_review

Problem fixed.

I added a function mwrank_get_precision() (by wrapping eclib's existing decimal_precision() function). Testing revealed that mwrank_set_precision(mwrank_get_precision()) had the effect of reducing the precision by at least 1 (exactly on for precision<803, the getting worse) on account or rounding errors in the conversion to/from base 2/base 10. That is fixed by adding some code to the wrapper function for set_precision().

This new functionality is used in the saturation() function to catch failures due to lack of precision and gradually increase the precision until success is gained. At the end the precision is put back to what it was.

In all the above, "precision" only refers to the floating point precision used by the NTL library withing eclib, not to anything else in Sage.

Patch has been tested on a 64-bit machine on the whole library (including long tests).

comment:2 Changed 9 years ago by rlm

  • Authors set to John Cremona
  • Milestone set to sage-4.6.2
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

This looks good to me! Passes tests on sage-4.6.1.rc0.

Changed 9 years ago by cremona

Applies to 4.6.2.alpha0

comment:3 Changed 9 years ago by cremona

  • Status changed from positive_review to needs_work

The new patch only differs from the first one in (new) lines 2115-2118 of, in the saturation() method: before, if the current precision was > 100 then the initial working precision was actually reduced to 100, which is silly. Now, if the user has "manually" increased precision already, that is used as the starting point.

I discovered this with an example where precision of 300 was needed (250 was too small).

I am switching this to "needs work" and then right away back to "needs review".

comment:4 Changed 9 years ago by cremona

  • Status changed from needs_work to needs_review

comment:5 Changed 9 years ago by rlm

Perhaps the two commented lines which print information about precision changes should be put into verbose commentary. This patch passes the usual testing process, and the code all looks good. John, can you suggest a more thorough way of reviewing this patch?

comment:6 Changed 9 years ago by cremona

It's a very good idea to have verbose=True cause output of precision changes.

Testing hints: it's no good giving input which is already saturated since eclib will prove saturation without using any floating point arithmetic at all. You need to give unsaturated input, and there is no need to have rank>1 to exercise the precision code, so loop through the (extended) database, pick rank one curves E with generator P and run E.saturate([k*P]) for small k>1.

OK, so I should do this.

comment:7 follow-up: Changed 9 years ago by rlm

I ran a loop as you suggested, and it seems that the new code never hangs (at least on the swath I tested). However, when I tried a keyboard interrupt to stop the loop, it just hanged. Maybe there should be a separate ticket to ensure that interrupts are handled properly.

comment:8 Changed 9 years ago by cremona

Good point about interrupts. I don't have the expertise to know what to do though, sorry.

If it's to be in a separate ticket can you make this one "positive review"? And I hope you will, since the pre-patched code is no better regarding interrupts; if anything it is worse (see ticket title!)

comment:9 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

comment:10 in reply to: ↑ 7 Changed 9 years ago by jdemeyer

Replying to rlm:

Maybe there should be a separate ticket to ensure that interrupts are handled properly.

I've been working a lot on interrupts in Sage. If you create that ticket, be sure to cc me.

comment:11 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.