update eclib and improve interface for elliptic curve saturation

[JohnCremona]

I recently made a new version of eclib, which will only affect the saturation of points on elliptic curves over Q. The interface for this (in the saturation() method for elliptic curves over Q) has some problems. Mainly, it does not do a good job of choosing the real precision which mwrank should work at, and also (due to shortcomings in eclib which are now improved) (1) when saturation at one prime fails owing to precision being too low, Sage has no way to do something sensible such as raise an error, or put the call into a loop in which the precision is increased; (2) there is no way to saturate at a single prime, or a range of primes, only at all primes or all primes except 2 or all primes up to some bound. The new eclib version allows for a first and last prime at which saturation should be done. The rationale here is that if you have saturated points on one curve and map them to another using an isogeny, then the image points will automatically be saturated at all primes dividing the isogeny degree.

I don't see a sensible way to deal with this in two parts, so I'll make a new eclib spkg (if that is what they are still called) and make the code changes to saturation at the same time.

Incidentally, Sage has its own implementation of the same underlying algorithm for elliptic curves over number fields, as as well as all the above, there should be a parameter called 'implementation' which could be either 'sage' or 'eclib' (or 'pari' before long).

New eclib source tarball at https://github.com/JohnCremona/eclib/releases/download/20210625/eclib-20210625.tar.bz2

Upstream: Fixed upstream, in a later stable release.

CC: @slel @collares @orlitzky @isuruf @kiwifb @antonio-rojas

Component: packages: standard

Keywords: eclib elliptic curve saturation

Author: John Cremona, Dima Pasechnik

Branch: 789550c

Reviewer: Dima Pasechnik, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/31443

[slel]

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
-I recently made a new version of eclib, which will only affect the saturation of points on elliptic curves over Q.  The interface for this (in the saturation() method for elliptic curves over Q) has some problems.  Mainly, it does not do a good job of choosing the real precision which mwrank should work at, and also (due to shortcomings in eclib which are now improved) (1) when saturation at one prime fails owing to precision being to low, Sage has no way to do something sensible such as raise an error, or put the call into a loop in which the precision is increased; (2) there is no way to saturate at a single prime, or a range of primes, only at all primes or all primes except 2 or all primes up to some bound.  The new eclib version allows for a first and last prime at which saturation should be done.  The rationale here is that if you have saturated points on one curve and map them to another using an isogeny, then the image points will autimatically be saturated at all primes dividing the isogeny degree.
+I recently made a new version of eclib, which will only affect the saturation of points on elliptic curves over Q.  The interface for this (in the `saturation()` method for elliptic curves over Q) has some problems.  Mainly, it does not do a good job of choosing the real precision which mwrank should work at, and also (due to shortcomings in eclib which are now improved) (1) when saturation at one prime fails owing to precision being too low, Sage has no way to do something sensible such as raise an error, or put the call into a loop in which the precision is increased; (2) there is no way to saturate at a single prime, or a range of primes, only at all primes or all primes except 2 or all primes up to some bound.  The new eclib version allows for a first and last prime at which saturation should be done.  The rationale here is that if you have saturated points on one curve and map them to another using an isogeny, then the image points will automatically be saturated at all primes dividing the isogeny degree.

-I don't see a sensible wway to dedeal with this in two parts, so I'll make a new eclib spkg (if that is what they are still called) and make the code changes to saturation at the same time.
+I don't see a sensible way to deal with this in two parts, so I'll make a new eclib spkg (if that is what they are still called) and make the code changes to saturation at the same time.

 Incidentally, Sage has its own implementation of the same underlying algorithm for elliptic curves over number fields, as as well as all the above, there should be a parameter called 'implementation' which could be either 'sage' or 'eclib' (or 'pari' before long).

[JohnCremona]

Commit: 69c3195

[JohnCremona]

Description changed:

--- 
+++ 
@@ -3,3 +3,5 @@
 I don't see a sensible way to deal with this in two parts, so I'll make a new eclib spkg (if that is what they are still called) and make the code changes to saturation at the same time.

 Incidentally, Sage has its own implementation of the same underlying algorithm for elliptic curves over number fields, as as well as all the above, there should be a parameter called 'implementation' which could be either 'sage' or 'eclib' (or 'pari' before long).
+
+New eclib source tarball at [https://johncremona.github.io/ftp/eclib-20210310.tar.bz2](https://johncremona.github.io/ftp/eclib-20210310.tar.bz2)

[JohnCremona]

Changed keywords from none to eclib elliptic curve saturation

[JohnCremona]

comment:2

Here's the updated eclib version v20210310 (see tarball link above) together with the necessary changes to the interface in src/sage/libs/eclib, and also a much simplified (and improved) saturation() method in sage/schemes/elliptic_curves/ell_rational_field.

This was a symbiotic procedure, in the sense that as I modified the interface code and tested, I found issues which had to be fixed on the eclib side.

The main changes for eclib are: various efficiency improvements in the sieve used to p-saturation for an individual prime p; much better division of a point by p (when it is p times a smaller point), by default using division polynomials instead of floating point methods, though I did also improve the f.p. approach to set the precision appropriately (instead of just relying on the user to do so) which fixed the immediate hard cases I had; reducing the saturation index bound when the subgroup is enlarged. I also made some improvements to the construction of a newform from an elliptic curve which will avoid the normalisation problems with modular symbols (which I had already fixed on the Sage side, but this is more robust).

I will post here some elliptic curves whose saturation is now faster and/or better. There are plenty of examples in the old doctests, but the really hard cases are not very suitable for doctests as they involve hundreds (or thousands) of digits, or take 15 minutes.

---

New commits:

2215893	#31443: update eclib package metadata
2554967	#31443: update eclib package metadata again
e1dfacf	#31443: adapt eclib library interface for version v20210310
69c3195	#31443: simplify/improve saturation method for elliptic curves over Q

[JohnCremona]

Branch: u/cremona/31443-eclib-saturation

[JohnCremona]

Author: John Cremona

[JohnCremona]

comment:3

An example where the point P is 3*Q but E.saturation([P]) used to fail.

In Sage 9.2:

E = EllipticCurve([0, 1, 0, -3532341, 2671895459])
Q = E([188751344014/116704809 , 43530702836852015/1260762051627])
P = 3*Q
E.saturation([P]) # fails

even after mwrank_set_precision(2000), which is slow. But with the new version (and no precision adjustment necessary, as the new method is exact):

sage: E.saturation([P])                                                                                                                               
([(188751344014/116704809 : 43530702836852015/1260762051627 : 1)],
 3,
 22.2351273597058)

and this is instantaneous.

An example you will probably not want to run to completion:

sage: E = EllipticCurve([0,1,1,-9872,374262])                                                                                                         
sage: pts = E.gens(sat_bound=0)                                                                                                                       
sage: pts                                                                                                                                             
[(-88 : 754 : 1), (-42 : 846 : 1), (-25 : 778 : 1), (57 : -1 : 1)]
sage: %time E.saturation(pts, verbose=True)

Under 9.2 it reports that the saturation index bound is 86682 but that it will not go past 10000 -- you can override this if you want, but even going up to 10000 takes a long time. With the new code, it does not reduce the bound (since the default is supposed to be that it goes all the way up to the bound necessary to prove saturation) and takes about 15 minutes.

[JohnCremona]

comment:4

In fact the second example is even more stupid in 9.2 since after proving p-saturation at all p up to 10979, with no errors or problems at all, it adds 1000 to the bound and starts again proving p-saturation from 2 up to 11981. As each of these runs takes several minutes, it will take a long time to get up to 86682 this way. One issue (now addressed) is that eclib did not have a parameter specifying which p to start at, if you wanted to resume saturating at any point except 2 or 3 (there was only an option to skip p=2). But more seriously, the saturation was being repeated not because of any problem which has arisen, just because of the artificial lowering of the bound. The old version could do the job by setting max_prime to 86682 but that takes a lot longer than the new version.

[antonio-rojas]

comment:6

Needs rebasing

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1f0b74f	#31443: update eclib package metadata
5fce79f	#31443: update eclib package metadata again
a46b6f9	#31443: adapt eclib library interface for version v20210310
453c793	#31443: simplify/improve saturation method for elliptic curves over Q
4ba267a	#31443: fix two doctest output now that eclib no longer gives incorrect results

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 69c3195 to 4ba267a

[JohnCremona]

comment:8

I rebased, fixed a merge conflict and two doctest outputs which were there to illustrate how it used to be true that you could get wrong results from eclib by choosing a parameter too small, but now eclib adjusts itself automatically so such an illustration is not possible.

[mkoeppe]

comment:9

checksums.ini needs a new field upstream_url, as explained in https://wiki.sagemath.org/ReleaseTours/sage-9.1#For_developers-1

[JohnCremona]

comment:10

Replying to @mkoeppe:

checksums.ini needs a new field upstream_url, as explained in https://wiki.sagemath.org/ReleaseTours/sage-9.1#For_developers-1

Thanks, I will look at that tomorrow. I did re-read the packaging instructions to refresh my memory and found some new stuff, but the contents of checksums.ini is whatever was put there by whatever the instructions told me to do. (I have been updating the eclib package since about 2008...)

[mkoeppe]

comment:11

(The packaging documentation has been updated in #30895 during the 9.3 cycle; it's not in the online copy of the Sage documentation yet.)

[JohnCremona]

comment:12

I added the line (literally) upstream_url=https://github.com/JohnCremona/eclib/archive/VERSION.tar.gz to build/pkgs/eclib/checksums.ini and then did ./sage --package fix-checksum eclib though the response was Checksum of eclib (tarball eclib-20210310.tar.bz2) unchanged

I'll update the branch in a minute, but I suspect that Sage will not like the fact that the upstream tarball (which is a tar.gz file created by github) is not the same as the tarball I put into upstream/ (and in the link on this ticket) which was created using make dist-bzip2.

If they need to be identical then I'll replace the actual tarball and then the checksum really will change.

The developers guide instructions are not at all clear. For example, I had assumed that one was suppose to replace the string 'VERSION' with the actual version number. Or is it supposed to be literally the string 'VERSION' which will be replaced by the content of the file package-version.txt? If that is the case I'll need to make another adjustment.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f475261

added upstream_url to eclib's checksums.ini

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4ba267a to f475261

[JohnCremona]

comment:14

Now I also did what I thought I should have done, namely change package-version.txt to be v20210310' (before it did not have the v but github puts the v in as the relevant tag is v20210310), and change the first line of checksum.ini to tarball=eclib-VERSION.tar.gz. I put an actual download from github of the tarball into upstream/; since github calls the file just v20210310.tar.gz I added the prefix 'eclib-'. Then

./sage --package fix-checksum eclib

did change the checksums. I then did

./sage -package update eclib v20210310

and then

./sage -f eclib

but this failed quickly with

[eclib-v20210310] Package 'eclib' is currently not installed
[eclib-v20210310] No legacy uninstaller found for 'eclib'; nothing to do
[eclib-v20210310] Deleting old versions of eclib libraries, which
[eclib-v20210310] would interfere with new builds...
[eclib-v20210310] Deleting old include directory...
[eclib-v20210310] --with-flint=/home/john/sage/local
[eclib-v20210310] Configuring eclib-v20210310
[eclib-v20210310] /home/john/sage/build/bin/sage-dist-helpers: line 163: ./configure: No such file or directory
[eclib-v20210310] /home/john/sage/build/bin/sage-dist-helpers: line 165: ./configure: No such file or directory
[eclib-v20210310] ******************************************************************************************************************************************************
[eclib-v20210310] Error configuring eclib-v20210310

I know that the recent packaging changes are supposed to make the procedure easier, but it is only easy when you know how and the instructions are clearly not adequately telling me what to do. Help!

[dimpase]

comment:15

You should use a configured tarball (created by make dist, typically. It would have ./configure script then ready), not the raw GitHub tarball, in upstream_url= field of checksums.ini.

Then ./sage -f should go through.

[dimpase]

comment:16

this patch makes it work:

--- a/build/pkgs/eclib/checksums.ini
+++ b/build/pkgs/eclib/checksums.ini
@@ -1,5 +1,5 @@
-tarball=eclib-20210310.tar.bz2
+tarball=eclib-VERSION.tar.bz2
 sha1=73437ac8deae94f00e7713405b3251d9c81f95e4
 md5=4ac988bc46869866f076f7bea0fdaa6b
 cksum=2130748042
-upstream_url=https://github.com/JohnCremona/eclib/archive/VERSION.tar.gz
+upstream_url=https://johncremona.github.io/ftp/eclib-VERSION.tar.bz2

(needless to say, Sage's ./configure must be run with --enable-download-from-upstream-url for this tarball-downloading machinery to work)

[dimpase]

comment:17

Is this a non-backward compatible change in Sage's interface to eclib (many distros have versions of eclibs available, and they are used by default). If so, we also need to modify build/pkgs/eclib/spkg-configure.m4 to take this into account.

A quick fix would be to assume that pkg-config will now work with eclib, simpifying build/pkgs/eclib/spkg-configure.m4 a lot.

[JohnCremona]

comment:18

I typed a long reply to that which just got zapped before I submitted the changes...

Yes, all previous versions of eclib will NOT work after these changes. So YES, we need to provide a method to check the version. The current m4 script cannot do that (the function version() it runs dates from before eclib had versin numbers and just displays compilation date and time). I can easily provide a function to return the version (which autotools defines as the macro VERSION). Perhaps more helpful would be a function to return the triple of integers (year, month, day), and also a function to compare the current version with a given (y,m,d) triple and return true iff the current version is equal or later than it. Then the little program constructed and run by the m4 could run (say) compare_eclib_version(2021, 3, 10) which would return true if and only if the actual version was equal or later than this. How does that sound?

In any case I can see that today will see a new version released with these functions in it, probably called 'v20210317'.

[dimpase]

comment:19

pkg-config is standard, distros that don't use it consistently have only themselves to blame. With pkg-config, it's as simple as with fplll, say, see https://github.com/sagemath/sage-prod/blob/develop/build/pkgs/fplll/spkg-configure.m4

Probably the separate check for mwrank should be kept, though. Can you add --version and/or -v option to mwrank, so that mwrank -v prints its version (make it equal to the eclib version) and exits?

Theoretically, there could be a situation that versions of mwrank and eclib are not the same on the system, so mwrank -v will allow to check for this consistency.

[dimpase]

Upstream: Reported upstream. No feedback yet.

[dimpase]

comment:20

Replying to @dimpase:

Theoretically, there could be a situation that versions of mwrank and eclib are not the same on the system, so mwrank -v will allow to check for this consistency.

copied this suggestion to https://github.com/JohnCremona/eclib/issues/67

[JohnCremona]

comment:21

That makes sense -- and I had mentioned this in the posting which disappeared. But I thought I had done this last time you (Dima) suggested it.

It makes little sense to talk about mwrank versions as different from eclib versions. mwrank is just the name of one of the executables built by eclib. But it does seem reasonable to use mwrank --version as a way for a system to tell which eclib version is installed. That is something different from your pkg-config suggestion though -- and eclib does have a file eclib.pc.

Now I will also comment on your eclib issue.

[dimpase]

comment:22

Replying to @JohnCremona:

That makes sense -- and I had mentioned this in the poting which disappeared. But I thought I had done this last time you (Dima) suggested it.

It makes little sense to talk about mwrank versions as different from eclib versions.

Say, one installs mwrank using an old eclib in /usr/local/bin, and has it shadow the new one mwrank in /usr/bin. We see such fun not quite bugs creeping up once in a while.

Comparing versions of eclib and mwrank is an extra check that won't hurt. pkg-config is useful in Python, as there is a Python interface to it (already used in Sage quite a bit to simplify the dread of getting the right libraries etc).

[JohnCremona]

comment:23

OK, so my current branch allows mwrank -V and outputs (e.g.) v20210317 and exits. None of my command-line options are multi-character and I am not going to change that now; as I said, '-v' is already taken.

So now we have pkg-config which reports the version, and also mwrank -V which does too.

All this still seems to be a lot of unnecessary both to me. Sage provides an mwrank executable via 'sage -mwrank' purely as a convenience to anyone out there (if there is anyone) who wants to install mwrank, as for such people I can say "install Sage and you'll get mwrank". That has been true for a decade or more, and now I can also say "use your distro package manager to install eclib, and you'll get mwrank". For historical reasons, Sage allows access to the mwrank binary in some of the elliptic curve functions, and also allows %mwrank to get a not very friendly user interface to mwrank (with no prompts). Both of these are really unnecessary and we could save some hassle by getting rid of them.

The point of what I am saying is that it matters not at all if anyone has a version of mwrank on their system which is not the same as the one provided by the eclib which Sage is using. A lot of the sage-eclib interface (including everything relevant to this ticket) is not about mwrank as such.

Can someone now explain to me how to change the m4 file to make use of the pkg-config thing? I think it would be quite reasonable to insist that the version installed on the system is exactly the version specified, not just "this or any later version", since I have enough to worry about without having to think about backwards compatibility. I'm also fairly sure that there is no-one in the world (except me) who installs eclib except as part of Sage anyway.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f475261 to 1bac713

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1bac713

more changes to eclib build setup

[JohnCremona]

Description changed:

--- 
+++ 
@@ -4,4 +4,4 @@

 Incidentally, Sage has its own implementation of the same underlying algorithm for elliptic curves over number fields, as as well as all the above, there should be a parameter called 'implementation' which could be either 'sage' or 'eclib' (or 'pari' before long).

-New eclib source tarball at [https://johncremona.github.io/ftp/eclib-20210310.tar.bz2](https://johncremona.github.io/ftp/eclib-20210310.tar.bz2)
+New eclib source tarball at [https://johncremona.github.io/ftp/eclib-v20210317.tar.bz2](https://johncremona.github.io/ftp/eclib-v20210317.tar.bz2)

[JohnCremona]

comment:25

The latest version + updated tarball for eclib-v20210317 is closer. For me this works in that I could (re)install eclib using ./sage -f eclib (I know there is a new way to do that but this worked), where I had put a copy of the updated tarball into upstream so it did no downloading.

I made some changes to the m4 file, but I have not tested to see if that works, and it does not try to compare the version number with what mwrank -V gives out. I guess that I should at least install this eclib version on my system and then try to configure sage from scratch to see if it likes my system version. I would be very happy if someone else would like to improve the m4 file.

[dimpase]

comment:26

I'll look at the m4 file tonight.

[JohnCremona]

comment:27

The Sage configure system is mysterious to me. For example, I have flint-2.7.1 installed but the configure script outputs

flint-2.6.3:                                 no suitable system package; will be installed as an SPKG

I think it might be the case that as eclib lists ntl, flint and pari as prerequisites, it will build eclib if any of those three are also going to be built. That is why I was looking at the output for these. I was not surprised to see that it wanted to build NTL since my installed NTL was old -- I am now building ntl-11.4.4. (I am in the habit of installing eclib's dependencies by building from source.) Similarly with pari. Sage wants pari-2.11.4.p1 which I assume is 2.11.4 with some patching (why?). I have a 2.11.3 and 2.12.0.alpha but the last stable release is 2.13.1 so shoule Sage not upgrade?

[dimpase]

comment:28

Replying to @JohnCremona:

The Sage configure system is mysterious to me. For example, I have flint-2.7.1 installed but the configure script outputs

flint-2.6.3:                                 no suitable system package; will be installed as an SPKG

I think it might be the case that as eclib lists ntl, flint and pari as prerequisites, it will build eclib if any of those three are also going to be built.

this is correct. Also, Sage is still on flint 2.6.3, see https://github.com/sagemath/sage-prod/issues/31069

more details can be found in the top-level config.log

That is why I was looking at the output for these. I was not surprised to see that it wanted to build NTL since my installed NTL was old -- I am now building ntl-11.4.4. (I am in the habit of installing eclib's dependencies by building from source.)

You might be willing to install them in /usr/local, then they will be picked up by ./configure, and (hopefully) used.

Similarly with pari. Sage wants pari-2.11.4.p1 which I assume is 2.11.4 with some patching (why?). I have a 2.11.3 and 2.12.0.alpha but the last stable release is 2.13.1 so shoule Sage not upgrade?

Pari upgrade to 2.13 is not yet done, see https://github.com/sagemath/sage-prod/issues/30906 - needs review.

As to what exactly is amiss in your current Pari, it can be seen in the top-level config log. There were several bugs in Pari 2.11 - were they all fixed in 2.11.4? I don't recall right away, there was a problematic Pari 2.12 release, perhaps something from there needed to be backported...

[JohnCremona]

comment:29

Thanks for the detailed comments. I do install stuff in /usr/local, currently I have a problem with FLINT-2.7.2 whose "make check" now fails after I upgraded MPIR to 3.0.0 and MPFR to 4.0.0.

I will look at those two tickets, especially the pari one. Meanwhile I don't mind at all if Sage builds its own eclib, as in any case that will be essential now at least until there are any distros with my current version (which I have not yet tagged or released anyway).

[dimpase]

comment:30

the tarball URL is still wrong. (the one in checksums.ini)

[dimpase]

comment:31

there is also rubbish in the branch, a file named t.

[dimpase]

Changed upstream from Reported upstream. No feedback yet. to Fixed upstream, in a later stable release.

[JohnCremona]

comment:33

Sorry about that, but at least these are things I can easily fix...done, but trac is not allowing me to push the revised branch. I also updated the tarball at ​https://johncremona.github.io/ftp/eclib-v20210317.tar.bz2 (in case you had already downloaded it).

[JohnCremona]

comment:34

Looking at my config.log, working backwards, I see that it wants to install eclib since it is installing ntl, it wants to install ntl (despite a new version being in /usr/local) because it is installing gmp/mpir, and it is installing gmp because it found no suitable system package, while for mpir it did find my new install and will not try to install that. But I do have gmp installed (libgmp-dev on ubuntu, package version 2:6.2.0+dsfg-4 on ubuntu 20.04). Dare I suggest that the configure script is incorrectly determining that gmp is not available?

[dimpase]

comment:35

by the way, why do you prepend v to to the version? This is an extra hassle. If it's just a number, or something like a.b.c, with a, b, c nonneg. integers, it's more stanard.

[dimpase]

comment:36

Replying to @JohnCremona:

Looking at my config.log, working backwards, I see that it wants to install eclib since it is installing ntl, it wants to install ntl (despite a new version being in /usr/local) because it is installing gmp/mpir, and it is installing gmp because it found no suitable system package, while for mpir it did find my new install and will not try to install that. But I do have gmp installed (libgmp-dev on ubuntu, package version 2:6.2.0+dsfg-4 on ubuntu 20.04). Dare I suggest that the configure script is incorrectly determining that gmp is not available?

Hmm, if you already have mpir/gmp installed in your Sage install, then ./configure will assume you want to keep it (and thus everything that depends upon it will be built).

make gmp-clean mpir-clean 

should clean these up, so that the system GMP is picked up by ./configure

[dimpase]

Changed branch from u/cremona/31443-eclib-saturation to public/packages/eclib/31443

[dimpase]

comment:37

here are my updates, with fixed m4 etc.

---

New commits:

573bcf6

fix m4 and tar URL, remove junk

[dimpase]

Changed commit from 1bac713 to 573bcf6

[dimpase]

comment:38

I guess if the tarfile has changed then the checksums should be updated too.

[JohnCremona]

comment:39

I have nbot yet managed to push my branch, but I'll try again only after merging your fix for the mp4.

My version numbers did not use to have the v in them, I added that yesterday for some reason. I will revert that -- I think it was because my tag did have the v, so th tarball github creates has the v, an I thought I would be linking to that -- but we are not. This will require a fresh tarball, but that will not take long.

The configure tests I have been running are on a fresh download from trac, not an existing build, so nothing has been built in it yet! eclib itself detects gmp, and when I run ldd on my latest version of the shared libec library I see

libgmp.so.10 => /usr/lib/x86_64-linux-gnu/libgmp.so.10 (0x00007f23ee737000)

so I don't know why Sage's configure does not find it. I do build mpir in its gmp-compat mode, so as well as the system library as above, in /usr/local/lib I have both libmpir and libgmp both installed when I do 'make install' on mpir.