Opened 11 years ago
Closed 7 years ago
#9322 closed defect (fixed)
long time in simon_two_descent for elliptic curves
Reported by:  cremona  Owned by:  AlexGhitza 

Priority:  major  Milestone:  sage6.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: 
Description (last modified by )
[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^2x232) sage: E = EllipticCurve([2w,18+3*w,209+9*w,2581+175*w,85255*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
comment:2 Changed 11 years ago by
 Cc jeremywest added
 Component changed from algebra to elliptic curves
 Milestone set to sage4.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 10 years ago by
 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^2x232) sage: E = EllipticCurve([2w,18+3*w,209+9*w,2581+175*w,85255*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 standalone gp and report upstream.
comment:4 Changed 10 years ago by
 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 gp2ccompiled version. So it is *not* an upstream problem,and one which should be solvable within Sage.
comment:5 Changed 9 years ago by
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 followup: ↓ 7 Changed 9 years ago by
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 9 years ago by
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 gpsimon.py creates its own gp instance without using the logfile option. In the short term, edit line 38 of sage/sage/schemes/elliptic_curves/gpsimon.py to add the logfile option. A better longterm solution would be to have a logfile parameter to the twodescent 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 9 years ago by
 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 Sagegp interface? What should we do with that ticket?
Paul
comment:9 Changed 9 years ago by
 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 9 years ago by
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
 Milestone changed from sage5.11 to sage5.12
comment:12 Changed 7 years ago by
 Keywords simon_two_descent added; Simon removed
comment:13 Changed 7 years ago by
 Description modified (diff)
comment:14 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:15 Changed 7 years ago by
 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^2x232) sage: E = EllipticCurve([2w,18+3*w,209+9*w,2581+175*w,85255*w]) sage: E.local_data() [] sage: E.simon_two_descent() Traceback (most recent call last): ... RuntimeError: *** at toplevel: 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 2descent program
With the fix I just made at #15483, it again gives the correct result, but after a long time.
comment:16 Changed 7 years ago by
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 followup: ↓ 18 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
 Branch set to u/mmasdeu/9322defaultsfortwodescent
 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 infiniteorder 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:
1dcdf8d  Allow for relative number fields to be passed to two_descent function.

78bb894  Fixed a doctest.

2085e0c  Added some comments.

6a54aa4  Fixed indentation problem in doctest.

522aa2f  Found an example for the doctest that takes much less to terminate (about 4s).

b2b66c5  Fixed calls to simon's two descent to use his own defaults (by default).

comment:20 Changed 7 years ago by
 Branch changed from u/mmasdeu/9322defaultsfortwodescent to u/pbruin/9322simon_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 nontrivial (reported rank changing from 1 to 0).
comment:21 Changed 7 years ago by
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^21/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, []]
.
comment:22 Changed 7 years ago by
 Commit changed from 594de7b4cabd1359de0c33748e17dc9209f4b61b to 4bdb5389e8b1a41ebfcf00a5c2561f0841113854
Branch pushed to git repo; I updated commit sha1. New commits:
db79035  Merge branch 'develop' into gp_simon_relative

a92a80e  Changed the doctest to make it independent of variable output.

275e4be  fix a bug in Denis Simon's 2descent program

8bceb36  Merge branch 'u/pbruin/16022simon_two_descent_bug' of trac.sagemath.org:sage into gp_simon_relative

962d338  Merge branch 'ticket/16009gp_simon_relative' into ticket/9322simon_two_descent_defaults

4bdb538  fix doctests in ell_number_field.py

comment:23 Changed 7 years ago by
 Reviewers set to Peter Bruin
 Status changed from needs_work to positive_review
comment:24 Changed 7 years ago by
comment:25 Changed 7 years ago by
 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:
41cbcdf  use default limtriv=3 for simon_two_descent over Q

comment:26 Changed 7 years ago by
 Commit changed from 41cbcdf3dddb39aa3093812faaea3062b2da9752 to ecd28b4f5ba2bff231807a512170a6e02e2a32aa
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ecd28b4  use default limtriv=3 for simon_two_descent over Q

comment:27 Changed 7 years ago by
 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 7 years ago by
 Branch changed from u/pbruin/9322simon_two_descent_defaults to ecd28b4f5ba2bff231807a512170a6e02e2a32aa
 Resolution set to fixed
 Status changed from positive_review to closed