Opened 11 years ago

Closed 8 years ago

#9322 closed defect (fixed)

long time in simon_two_descent for elliptic curves

Reported by: cremona Owned by: AlexGhitza
Priority: major Milestone: sage-6.2
Component: elliptic curves Keywords: simon_two_descent ecc2011
Cc: wuthrich, jeremywest Merged in:
Authors: Marc Masdeu Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: ecd28b4 (Commits, GitHub, GitLab) Commit: ecd28b4f5ba2bff231807a512170a6e02e2a32aa
Dependencies: #11005, #15483, #16009, #16011 Stopgaps:

Status badges

Description (last modified by cremona)

[See #15608 for a list of open simon_two_descent tickets]

[NB This is a different problem from the one on #5153]

Chris Wuthrich reports:

sage: K.<w> = NumberField(x^2-x-232)
sage: E = EllipticCurve([2-w,18+3*w,209+9*w,2581+175*w,852-55*w])
sage: E.local_data()
[]
sage: E.simon_two_descent(verbose=2)

This takes about 2.5 minutes with Sage 4.7.1 on a 1.6Ghz Core 2 Duo.

The same example runs fine in gp using the same version of the script ell.gp that Sage has (in version 4.4.4) and the same version of gp.

Change History (28)

comment:1 Changed 11 years ago by cremona

john@ubuntu%sage -gp
                  GP/PARI CALCULATOR Version 2.3.5 (released)
...

? bnf=bnfinit(y^2-y-232);
? w=Mod(y,y^2-y-232)
%8 = Mod(y, y^2 - y - 232)
? e=ellinit([2-w,18+3*w,209+9*w,2581+175*w,852-55*w]);
? bnfellrank(bnf,e)
courbe elliptique : Y^2 = x^3 + Mod(9*y + 308, y^2 - y - 232)*x^2 + Mod(1200*y + 27936, y^2 - y - 232)*x + Mod(57968*y + 1054096, y^2 - y - 232)
points triviaux sur la courbe = [[1, 1, 0]]
#S(E/K)[2]    = 4
#E(K)/2E(K)  >= 1
#III(E/K)[2] <= 4
rang(E/K)    >= 0
listpointsmwr = []
%10 = [0, 2, []]

comment:2 Changed 11 years ago by jeremywest

  • Cc jeremywest added
  • Component changed from algebra to elliptic curves
  • Milestone set to sage-4.5
  • Status changed from new to needs_work

I also noticed this same problem, although it seems to be nearly ubiquitous for number fields. I found it for several quadratic and cubic extensions as well as for a degree seven extension. For one I got an index out of bounds error which I believe originates because gp does not hand back the results expected by the sage script. For the rest I found that the sage script was attempting to coerce a point from one curve to another and it reports that the point does not lie on the curve.

Unfortunately, I don't currently have access to sage so I am unable to report line numbers. The problem occurs in sage/schemes/elliptic_curves/gp_simon.py near the bottom of the only function defined.

comment:3 Changed 11 years ago by cremona

  • Keywords Simon added
  • Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
  • Status changed from needs_work to needs_info

With 4.7.alpha1 this works fine:

sage: K.<w> = NumberField(x^2-x-232)                                   
sage: E = EllipticCurve([2-w,18+3*w,209+9*w,2581+175*w,852-55*w])      
sage: E.local_data()                                                   
[]
sage: E.simon_two_descent()                                      
(0, 2, [])

but after #11005 (which updates to a newer version of Simon's GP scripts) we run into an infinite loop:

 **** Warning: doubling the real precision in nfsign_s **** 76
 **** Warning: doubling the real precision in nfsign_s **** 152
 **** Warning: doubling the real precision in nfsign_s **** 76
 **** Warning: doubling the real precision in nfsign_s **** 152
 **** Warning: doubling the real precision in nfsign_s **** 76

which I will test on a stand-alone gp and report upstream.

comment:4 Changed 11 years ago by cremona

  • Report Upstream changed from Not yet reported upstream; Will do shortly. to N/A
  • Status changed from needs_info to needs_work

Running under gp directly:

? K = bnfinit(y^2 - y - 232);
? a = Mod(y,K.pol);
? bnfellrank(K, [-a + 2,3*a + 18,9*a + 209,175*a + 2581,-55*a + 852])
courbe elliptique : Y^2 = x^3 + Mod(9*y + 308, y^2 - y - 232)*x^2 + Mod(1200*y + 27936, y^2 - y - 232)*x + Mod(57968*y + 1054096, y^2 - y - 232)
points triviaux sur la courbe = [[1, 1, 0]]
#S(E/K)[2]    = 4
#E(K)/2E(K)  >= 2
#III(E/K)[2] <= 2
rang(E/K)    >= 1
 III devrait etre un carre, donc 
#E(K)/2E(K)  = 4
#III(E/K)[2] = 1
rang(E/K)    = 2
listpointsmwr = [[Mod(-35/4*y - 186, y^2 - y - 232), Mod(-21/8*y - 37, y^2 - y - 232)]]
%71 = [2, 2, [[Mod(-35/16*y - 93/2, y^2 - y - 232), Mod(-1727/64*y - 2531/8, y^2 - y - 232)]]]

we get instant success. Also with the gp2c-compiled version. So it is *not* an upstream problem,and one which should be solvable within Sage.

comment:5 Changed 10 years ago by zimmerma

I've been struggling with that bug for a few hours, and have made only little progress. With Sage 4.7.1 and Pari 2.4.3 (development), I've noticed that Pari 2.4.3 and the version of Pari within Sage differ at bbnf = bnfinit(rnfeq[1],1) in ell.gp, where rnfep[1] = x^6 + 625*x^5 + 135916*x^4 + 14984560*x^3 + 914453072*x^2 + 29502178560*x + 392635160576.

Pari 2.4.3 returns bbnf: [Mat(2), Mat([0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, ... whereas Pari within Sage returns bbnf: [Mat(2), Mat([0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, ...

However I don't know if bnfinit should be deterministic...

Paul

comment:6 follow-up: Changed 10 years ago by zimmerma

is there a way to get the output of the print commands from the ell.gp script when it is called from within Sage? Even with a large value of DEBUGLEVEL_ell, the output of those print statements does not appear in the Sage session, thus it is difficult to debug.

Paul

comment:7 in reply to: ↑ 6 Changed 10 years ago by cremona

Replying to zimmerma:

is there a way to get the output of the print commands from the ell.gp script when it is called from within Sage? Even with a large value of DEBUGLEVEL_ell, the output of those print statements does not appear in the Sage session, thus it is difficult to debug.

Paul

You can get a whole gp session logged to a file by setting gp=Gp(logfile=foobar.txt'). But the code in gp-simon.py creates its own gp instance without using the logfile option. In the short term, edit line 38 of sage/sage/schemes/elliptic_curves/gp-simon.py to add the logfile option. A better long-term solution would be to have a logfile parameter to the two-descent function itself and pass that on.

By the way, there are new version of Simon's scripts which in Sage Days in March (6 months ago!) I got working in a better way, using gp2c to convert to C code. There was some reason which I now cannot remember why there was a delay in getting this merged, and after 6 months I fear that the patches we made then would no longer work. Damn. Anyway, I strongly suggest if you have problem cases that you run the curves directly through ell.gp (outside Sage) using the newest version of ell.gp from Simon's web page, since you may be seeing a problem which has already been fixed.

comment:8 Changed 10 years ago by zimmerma

  • Description modified (diff)
  • Status changed from needs_work to needs_info
  • Summary changed from bug in simon_two_descent for elliptic curves to long time in simon_two_descent for elliptic curves

thank you John for your advice. After trying it, I figured out that with Sage 4.7.1 on my laptop in fact the example in the description actually works, but takes about 2.5 minutes, during which top reports that the gp process takes 100% of the cpu time, while evaluating the command

ans=bnfellrank(K, [-a + 2,3*a + 18,9*a + 209,175*a + 2581,-55*a + 852]);;

Can someone else confirm? Maybe a problem in the Sage-gp interface? What should we do with that ticket?

Paul

comment:9 Changed 10 years ago by zimmerma

  • Keywords ecc2011 added

ok, I found where the problem comes from. In the file ellQ.gp which is also loaded by the gp_simon.py file, the global constants LIM1, LIM3, LIMTRIV have different values than in ell.gp, respectively 5, 50, 50 instead of 2, 4, 2.

The slow behaviour can be reproduced with sage -gp if one reads both ell.gp *and* ellQ.gp. If one only reads ell.gp, it is fast. Apparently ellQ.gp is not needed for this computation.

Moreover the default values in Sage are again different: 5, 50, 10.

With 5, 5, 10 it takes only 1.45s (wall clock time) on my laptop. With 5, 10, 10 it takes 2.19s. With 5, 20, 10 it takes 11.63s.

Note that those values should be modified both in ell_number_field.py and in gp_simon.py (the former function is critical in this example).

One should also share the default values for lim1, lim3, limtriv between the simon_two_descent functions in ell_number_field.py and gp_simon.py.

Paul

comment:10 Changed 10 years ago by cremona

In the other ticket on this we changed Simon's scripts so that the use of these "environment variables" for passing configuration parameters was replaced by actual parameters to the functions (with default values). So this problem should go away then. We also persuaded Simon not to have the same function name for different functions in his various script files (he even had the same name for two different an incompatible versions of functions to do the same thing!).

comment:11 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:12 Changed 8 years ago by chapoton

  • Keywords simon_two_descent added; Simon removed

comment:13 Changed 8 years ago by cremona

  • Description modified (diff)

comment:14 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:15 Changed 8 years ago by pbruin

  • Dependencies set to #11005, #15483

After applying #11005 (upgrade Simon's script to the latest version), rather than running for a long time, this example now gives an error similar to #15483:

sage: K.<w> = NumberField(x^2-x-232)
sage: E = EllipticCurve([2-w,18+3*w,209+9*w,2581+175*w,852-55*w])
sage: E.local_data()
[]
sage: E.simon_two_descent()
Traceback (most recent call last):
...
RuntimeError: 
  ***   at top-level: ans=bnfellrank(K,[-a+2,3
  ***                     ^--------------------
  ***   in function bnfellrank: ...eqtheta,rnfeq,bbnf];rang=
  ***   bnfell2descent_gen(b
  ***   ^--------------------
  ***   in function bnfell2descent_gen: ...und,r=nfsqrt(nf,norm(zc))
  ***   [1];if(DEBUGLEVEL_el
  ***   ^--------------------
  ***   array index (1) out of allowed range [none].
An error occurred while running Simon's 2-descent program

With the fix I just made at #15483, it again gives the correct result, but after a long time.

Last edited 8 years ago by pbruin (previous) (diff)

comment:16 Changed 8 years ago by pbruin

In principle it is not a bug if Sage uses different default values than Simon's script for the various parameters (lim1, lim3, limtriv and the more technical maxprob and limbigprime). The defaults should be sensible, of course. I guess we should find out if there is a good reason to use different defaults, and if so, what settings would be reasonable.

comment:17 follow-up: Changed 8 years ago by mmasdeu

Is there a good reason to not use the default values that pari is using? What is troubling is that an example that runs fast in pari does take forever in Sage. So I would put the defaults to None, and then pass different defaults when the curve is over QQ or over a number field (according to DS's scripts).

One exception to this: the parameter limbigprime should be set to 0, to avoid the use of probabilistic (and thus not provably true) prime testing.

comment:18 in reply to: ↑ 17 Changed 8 years ago by pbruin

Replying to mmasdeu:

So I would put the defaults to None, and then pass different defaults when the curve is over QQ or over a number field (according to DS's scripts).

One exception to this: the parameter limbigprime should be set to 0, to avoid the use of probabilistic (and thus not provably true) prime testing.

Agree with all of this.

comment:19 Changed 8 years ago by mmasdeu

  • Branch set to u/mmasdeu/9322-defaults-for-two-descent
  • Commit set to b2b66c54b8fd220e976c9d5ddcaeb6eec8ba7ff8
  • Status changed from needs_info to needs_review

I have implemented the above suggestions. However, it seems that the using limbigprime=0 raises errors (I found them when using gp directly) and so I have currently set it to 30 (DS's default).

When simon_two_descent() is called with default arguments, the infinite-order points change (this is expected). I have checked that the answer is still correct (in particular, the rank bounds are the same), and changed the doctests (which affected four files in total).

Now the doctests pass for everything in the schemes/elliptic_curves folder, but I haven't run all the others.


New commits:

1dcdf8dAllow for relative number fields to be passed to two_descent function.
78bb894Fixed a doctest.
2085e0cAdded some comments.
6a54aa4Fixed indentation problem in doctest.
522aa2fFound an example for the doctest that takes much less to terminate (about 4s).
b2b66c5Fixed calls to simon's two descent to use his own defaults (by default).

comment:20 Changed 8 years ago by pbruin

  • Branch changed from u/mmasdeu/9322-defaults-for-two-descent to u/pbruin/9322-simon_two_descent_defaults
  • Commit changed from b2b66c54b8fd220e976c9d5ddcaeb6eec8ba7ff8 to 594de7b4cabd1359de0c33748e17dc9209f4b61b
  • Dependencies changed from #11005, #15483 to #11005, #15483, #16009, #16011
  • Status changed from needs_review to needs_work

Merged with development branch. There are some doctest failures, one of which seems to be non-trivial (reported rank changing from 1 to 0).

comment:21 Changed 8 years ago by pbruin

The failing example is the new doctest from #16009 in gp_simon.py; it now returns (0, 0, []).

sage: F.<a> = QuadraticField(29)
sage: x = QQ['x'].gen()
sage: K.<b> = F.extension(x^2-1/2*a+1/2)
sage: E = EllipticCurve(K,[1, 0, 5/2*a + 27/2, 0, 0])
sage: E.simon_two_descent(lim1=2, limtriv=3)
(1, 1, [((-369/50*a - 1987/50)*b + 539/50*a + 2897/50 : (-27193/250*a - 146439/250)*b + 39683/250*a + 213709/250 : 1)])

This is reproducible inside gp (2.5.x) with the current version of Simon's script (as included in Sage since #11005):

K = bnfinit(y^4 + y^2 - 7);
a = Mod(y, K.pol);
E = [1, 0, 5*a^2 + 16, 0, 0];
LIM1 = 2;
LIMTRIV = 3;
bnfellrank(K, E)

This returns [0, 0, []].

Last edited 8 years ago by pbruin (previous) (diff)

comment:22 Changed 8 years ago by git

  • Commit changed from 594de7b4cabd1359de0c33748e17dc9209f4b61b to 4bdb5389e8b1a41ebfcf00a5c2561f0841113854

Branch pushed to git repo; I updated commit sha1. New commits:

db79035Merge branch 'develop' into gp_simon_relative
a92a80eChanged the doctest to make it independent of variable output.
275e4befix a bug in Denis Simon's 2-descent program
8bceb36Merge branch 'u/pbruin/16022-simon_two_descent_bug' of trac.sagemath.org:sage into gp_simon_relative
962d338Merge branch 'ticket/16009-gp_simon_relative' into ticket/9322-simon_two_descent_defaults
4bdb538fix doctests in ell_number_field.py

comment:23 Changed 8 years ago by pbruin

  • Reviewers set to Peter Bruin
  • Status changed from needs_work to positive_review

Merged #16009 and indirectly #16022, and fixed the two remaining doctest failures. No other unexpected things, so I think this can safely be regarded as a reviewer patch.

comment:24 Changed 8 years ago by pbruin

  • Authors set to Marc Masdeu

comment:25 Changed 8 years ago by git

  • Commit changed from 4bdb5389e8b1a41ebfcf00a5c2561f0841113854 to 41cbcdf3dddb39aa3093812faaea3062b2da9752
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

41cbcdfuse default limtriv=3 for simon_two_descent over Q

comment:26 Changed 8 years ago by git

  • Commit changed from 41cbcdf3dddb39aa3093812faaea3062b2da9752 to ecd28b4f5ba2bff231807a512170a6e02e2a32aa

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ecd28b4use default limtriv=3 for simon_two_descent over Q

comment:27 Changed 8 years ago by pbruin

  • Status changed from needs_review to positive_review

While looking at #10745 I noticed that the default limtriv over Q in Simon's script ellQ.gp changed from 50 to 3 in the latest version, so I changed the default setting in ell_rational_field.py and gp_simon.py accordingly. Still qualifies as a reviewer patch, I guess.

comment:28 Changed 8 years ago by vbraun

  • Branch changed from u/pbruin/9322-simon_two_descent_defaults to ecd28b4f5ba2bff231807a512170a6e02e2a32aa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.