Program mwrank: uses 2-descent (via 2-isogeny if possible) to
determine the rank of an elliptic curve E over Q, obtain a set of
points which generate E(Q) modulo 2E(Q), and finally "saturate" to a
full Z-basis for E(Q).  For details of (some) algorithms see the
author's book.  Please acknowledge use of this program in published
work, and send problems (and preprints!) to
John.Cremona@nottingham.ac.uk.

For changes since first distribution the file mwrank.changes.
For command line options, see the file mwrank.options.

	MWRANK vs. MRANK

There used to be two separate programs called mwrank and mrank; they
both did the same 2-descent, but mwrank also went on to enlarge the
subgroup of rank r found to give the full Mordell-Weil group by
searching for rational points on E up to a certain naive height.  This
latter procedure was not very efficient, and to avoid reports of known
problems at this stage I put a ceiling on this search at 15
(=logarithmic naive height).  This means that in many cases the points
finally output were NOT guaranteed to be a basis for E(Q) (but the
output should say this).

As of Jan 2005, the saturation stage is done much more efficiently
using the "saturation sieve" method.

Now there is only one program mwrank.  Saturation is done unless the
generating points are not going to be output (e.g. with command-line
flags -v 0 and neither -l nor -o).


A	HOW TO USE MWRANK

1. Options

All options and parameter adjustments are now made via command line
options: see the file mwrank.options for details, or run 
	mwrank -h
which displays the options briefly and exit.

2. Curve input

The input consists of one or more curves, in the format
	a1 a2 a3 a4 a6
(separated by whitespace), or
	[a1,a2,a3,a4,a6]
These can of course be from a file, as in
	mwrank < curves.in
To end the input either use a "null curve" [0,0,0,0,0] or EOF
(e.g. Control-d at the terminal).

The input coefficients MUST be integers:  attempting to input
non-integral rationals including the '/' symbol will cause an error
message to be output and the program will abort.

The curves are prompted for, unless verbosity is set to 0.

For example, given the input file r5.in containing

0 0 1 -79 342
0 0 1 -169 930
0 1 1 -30 390
0 0 1 -301 2052
0 0 1 -457 3786

the command
	mwrank -q -v 0 < r5.in
produces the output (the first line and time format may be different)
===

Curve [0,0,1,-79,342] :  Rank = 5
Curve [0,0,1,-169,930] :  Rank = 5
Curve [0,1,1,-30,390] :  Rank = 5
Curve [0,0,1,-301,2052] :  Rank = 5
Curve [0,0,1,-457,3786] :  Rank = 5
===
adding "-l" to the parameters will cause the generators and regulator
to be output; 
adding "-o" results in an abbreviated form of output to be output also
for post-processing by Pari; for the first curve above it gives
[[5],[[3,11],[43,276],[45,296],[62,483],[92,878]]]

3. There are two types of point search carried out by mwrank.

(a) On the homogeneous spaces which represent elements of the
appropriate Selmer group, called "quartics" in the program (they have
equations y^2=g(x) where g is quartic).  Here existence of rational
points is necessary for the homogeneous space to come from a point on
the curve rather than an element of the Tate-Shafarevitch group.  The
bound used is a bound on the logarithmic height.  If
(x,y)=(u/w,v/w^2) it is a bound on max(log|u|,log|w|).  

The default value is 10; to change the default to (say) 12 use
command-line option "-b 12".  Warning: increasing this bound even by 1
can increase the running time considerably when there really are
homogeneous spaces with no rational point (but with points everywhere
locally, of course).  I would not recommend setting this to more than
15: even if you are "sure" that the quartic has a rational point,
other methods such as higher descents are probably better to find such
large points.

For entirely logical reasons it can also happen that reducing the
value of this parameter can increase the running time -- and vice
versa.  So while 10 is the default it is sometimes worth running with
a smaller value.  (In the above examples, -b 1 works just as well, in
the same time).

If the curve has rational 2-torsion, then the search on the first
descent curves has a bound of at most 6 (less if you set it using -b),
and then a second descent is used if necessary, where the full bound
is used.

NB During the second descent, part of the quartic reduction process
works much better using multi-precision floating point arithmetic, but
the distributed (executable) version of the program does not have
this.  The reason: my programs currently either use multi-fp for ALL
fp arithmetic, or for NONE; and turning it on (which is a simple
compiler switch) slows down other parts of the program a lot, so for
most curves it is better to have it off.  Ask me for a multi-fp
version if you want one, or build your own from the sources, using
LiDIA.

(b) [OBSOLETE since Jan 2005: the -c flag has no effect as saturation
is now done differently.] if the parameter -c is set to a nonzero
value, then after the 2-descent when we (should) have points covering
the cosets of 2E(Q) in E(Q) a further search is done, on the curve
itself, up to a certain bound on the logarithmic height.  The program
computes a suitable bound such that if it searches that far you are
guaranteed to have the full Mordell-Weil group.  You can use this
value by entering "-c -1", BUT for many curves it will not be
practical to search that far.  So I have put a ceiling on this of 20
(this can be changed: see the source file mwrank.cc, macro
MAX_HEIGHT).  You can put your chosen bound on it with the
command-line option -c, for example "mwrank -c 5 ...".

OLD WARNING USED TO SAY: this is currently one of the weakest parts of
the program.  There are more intelligent ways of expanding the
subgroup of full rank to the full M-W basis, but I have not
implemented them.  So you are recommended to give a small value for a
first run (or even 0, i.e. leave it as the default in which this step
is omitted entirely)

BUT a "more intelligent way" _has_ now been implemented!


B. WHAT IT DOES

There are two main sub-cases depending on whether the curve has a
point of order 2 or not.  If so, it uses the 2-isogeny in the
well-known way, and can list the quartics to be considered with little
trouble.  Then the only difficulty is finding rational points on them.
I have successfully run curves of rank 13, such as Fermigier's
	[0,36861504658225,0,1807580157674409809510400,0]   
and also his rank 14 curve
	[0,2429469980725060,0,275130703388172136833647756388,0]
and most recently (2001) Dujella's rank 15 curve
        [1,0,1,34318214642441646362435632562579908747,3184376895814127197244886284686214848599453811643486936756]
all of which take less than 30 seconds with default parameters on 
an 800MHz Athlon.

If there is no 2-torsion it goes back to the original
Birch-Swinnerton-Dyer method, which involves searching for the
quartics, and eliminating equivalent ones.  The search region can be
very large if the curve coefficients are large.  Also the search is
divided into between 1 and 4 sub-searches.   Recent developments make
this rather more efficient, (a) by improving the bounds, (b) by using
a quadratic sieve in the search for quartics, and (c) by using maps to
E(Qp)/2E(Qp) for certain auxiliary primes p.  

NB One effect of the last-named feature is that the program usually
finds generators for E(Q)/2E(Q) rather than a complete set of coset
representatives.   In general, it will express E(Q)/2E(Q) as a direct
sum A+B, and will give all nonzero elements of A and generators for B
(the output will explain this when it occurs).   The points in A are
those which lie in 2E(Qp) for all the auxiliary primes used.   For
curves of higher rank one can increase the number of primes used from
the default of 6 to something a little higher than the suspected rank,
using the option "-x 8" say.  This does carry a little overhead.

Example: The curve [0,0,0,-9217,300985] has rank 7 and runs very
quickly.  With the default ("-x 6") we find three nonzero points in A,
so rank(A)=2, and 5 generators of B, so rank(B)=5 and the total rank
is 2+5=7.  With "-x 9" this becomes 1+6=7, and with "-x 10" we have
A=0.  (These runs all took approx 3.8 seconds on my P90).

After this stage we know the rank (either certainly, if all the
everywhere-locally-soluble homogeneous spaces have rational points, or
conditionally, if we have decided that some of them do not but have
not proved that).  Next, from each homogeneous space with a point we
compute a point on the original curve.  This gives a set of between r
and 2^r-1 points (depending on how the rank is divided between the
groups A and B defined above) covering the non-trivial cosets of 2E in
E (when there is no 2-torsion), and a more complicated set of points
when there is 2-torsion, also covering these cosets.

[If nothing else, this gives one way of finding points on curves.  For
example the curve [0,0,0,0,-618] has rank 2, generated (up to finite
odd index) by 
	[19 : -79 : 1] of height 3.21143 and 
	[550688955674 : 2182722347909 : 31136956136] of height 19.2662.
A simple point search would take a very long time to find that second
generator!] 

The third stage is to "saturate", i.e. enlarge the group of points
found to a basis for the full Mordell-Weil group (so far we have a
subgroup of finite ODD index).  This stage (the "infinite descent") is
now much more efficient than it used to be, but might still take a
little time especially for curves of larger rank.  It is possible that
saturation might fail at some primes (i.e. at some prime p which could
divide the index) in which case a warning will be output.  The
command-line flag -S may be used to change the default saturation
behaviour:  see file mwrank.options.

Note that if the 2-descent has not been entirely conclusive
(e.g. non-trivial III[2]) then the subgroup of points found will be
saturated within the MW group, but saturation will never increase the
rank.

There are two ingredients in the saturation process: (1) determine an
upper bound for the "saturation index", i.e. the index of (subgroup
generated by) the known points in its saturation, and (2) for each
prime p up to this bound, either prove that the points are already
p-saturated, or enlarge by index p (repeatedly if necessary) until
p-saturated.  For some curves (notably those of high rank, such as the
rank 15 curve in the test data) the index bound computed by the
program is much too large for stage (2) to be practical (in that
example the bound is nearly 10^50, for example).  In this case the
program will by default issue a warning (containing the index bound
computed) and only saturate at primes up to 100.  That bound can be
increased using the command-line option -S.  Alternatively, saturation
can be turned off entirely using "-S 0".  Also, if no points are to be
output (i.e. with option -v 0 and neither -l nor -o) then no
saturation is done as there is obviously no point.  For stage (2)
there is usually no problem, but if the program determines that the
points are not p-saturated then it constructs a rational point P which
is (probably) p times another rational point Q, and tries to divide P
by p using the elliptic logarithm and exponential functions.  This may
fail if the precision is not high enough (for example with the rank 15
curve, the points found are not 3-saturated and require 2 steps of
3-saturation to gain index 9; but this only works with the LiDIA
multi-precision version and at least 100 decimals (-p 100)).

Saturation was implemented during 2004 and added to mwrank in January
2005;  bug reports are of course welcome.

ARITHMETIC

mwrank and friends need to use a multi-precision integer package.  The
only ones recognised are libg++ (which has disappeared from gcc since
2.8), LiDIA and NTL.  If you compile the source code, the
configuration program will need to know where you have one of these
installed.  The binaries will tell you when they start up which
arithmetic they are using (unless you use the quiet flag "-q").  [This
feature will not appear in binaries compiled before August 2000.]

There are several versions of the linux binaries for mwrank:
mwrank_ntl (uses NTL arithmetic but no multi-precision floating
point), mwrank_n (uses NTL arithmetic and multi-precision floating
point), mwrank_li (uses LiDIA arithmetic but no multi-precision
floating point), mwrank_l (uses LiDIA arithmetic and multi-precision
floating point).  All have been compiled as static so you do not have
to have any libraries installed to run them.

It is recommended that you use the multi-precision versions for curves
with large coefficients; otherwise results may be wrong.

You can aid the factorization of large integers in several ways:

(a) If you have the PARI/GP installed (it checks for the existence of
$PATH_TO_GPgp, or /usr/local/bin/gp if the environment variable
PATH_TO_GP is not set; i.e. the default value is /usr/local/bin/ (with
the trailing /)) then factorization will be done by GP using its
factor() function.  This will cause (small) temporary files to be
created in /tmp which will be deleted after use (though not if the
program is aborted by the user).

(b) By default the programs initialise an array of primes < 10^6, so
will fail to factor some numbers > 10^12 by trial division.  This
default can be increased as follows: create a file called MAXPRIME
containing a single integer, such as 2000000 or 10000000.  Then this
will be used instead of the default.

(c) If a file called PRIMES exists in the current directory,
containing zero or more prime numbers (separated by whitespace,
e.g. one per line), then the programs read this in at the start and
use these for trial division as well as the main prime array.  No
check is made that these numbers are prime.  This is an advantage if
you make several runs with the same curve which has a discriminant
which is hard to factor, since you can avoid doing the hard work more
than once.  Any other primes found during the run are added to the
list, and the updated list is output to PRIMES at the end.
NB This will cause problems if you do not have write permission in the
current directory!

DISCLAIMER

You are welcome to use the program as is.  There have been bugs and
certainly there still are some.  The program can and will be improved.
Please report strange behaviour to me in a reasonable way (you must
say when you got your copy of the program and include an input file
which gives the problem); I do not guarantee to do anything about it
-- I am busy and this is not a commercial package! -- but I will do my
best.  I particularly reserve the right NOT to deal with problems
which are machine-dependent!


							John Cremona
							3 February 1995
						updated	12 January 1998
						updated	25 September 2000 
						updated	 5 July 2001 
						updated	12 November 2003
						updated	 5 January 2005
						updated	10 May 2005