Opened 12 years ago

Closed 8 years ago

# long time in simon_two_descent for elliptic curves

Reported by: Owned by: cremona AlexGhitza major sage-6.2 elliptic curves simon_two_descent ecc2011 wuthrich, jeremywest Marc Masdeu Peter Bruin N/A ecd28b4 ecd28b4f5ba2bff231807a512170a6e02e2a32aa #11005, #15483, #16009, #16011

[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.

### comment:1 Changed 12 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 12 years ago by jeremywest

• 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

• 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 11 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: ↓ 7 Changed 11 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 11 years ago by cremona

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

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 11 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 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:12 Changed 9 years ago by chapoton

• Keywords simon_two_descent added; Simon removed

### comment:13 Changed 9 years ago by cremona

• Description modified (diff)

### comment:14 Changed 9 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:15 Changed 9 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 9 years ago by pbruin (previous) (diff)

### comment:16 Changed 9 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: ↓ 18 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

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:

 ​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 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:

 ​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 2-descent program` ​8bceb36 `Merge branch 'u/pbruin/16022-simon_two_descent_bug' of trac.sagemath.org:sage into gp_simon_relative` ​962d338 `Merge branch 'ticket/16009-gp_simon_relative' into ticket/9322-simon_two_descent_defaults` ​4bdb538 `fix 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:

 ​41cbcdf `use 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:

 ​ecd28b4 `use 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.