Using las for the descent
=========================

NOTE: there is now a general script that can compute the logarithm of a
given target. See scripts/descent.py . The documentation below now
contains just how to create a hint file.

NOTE: for the descent, las must be compiled with appropriate flags. The
las_descent binary is automatically compiled with these flags.

Writing a hint table
-------------------

The descent requires a "descent hint table" that contains information
about how to tune the parameters along the descent.

Examples of descent-hint tables are given as .hint files in the params_dl/
directory.

Each line correspond to a bit-size of a special-q for one side. For
example:
  55r 0.028 1.00 I=15 400000,47,65 400000,48,94
means (in order):
  55r   : this line is about a 55-bit special-q on the rational side
  0.028 : expected time in seconds to find a relation
  1.00  : probability of success
  I=15  : the I to use
  400000,47,65 : parameters for the rational side (0 side)
  		     lim0,lpb0,mfb0
  400000,48,94 : same for the other side (1).

There are in fact three ways to specify the parameters on both sides.
400000,47,65 : set lim, lpb, mfb
400000,47,1.2 : set lim, lpb, lambda (based on the fact the the third field is < 10)
400000,47,65,1.2 : set lim, lpb, mfb, lambda
(in the first case, lambda defaults to mfb0/lpb0+0.1 as everywhere else
in cado-nfs).

At the moment, it is *mandatory* to have the same values for lim0, lim1
on each line. This might change if we see a clear need to make them vary.
The value of I can vary, but then the value of I passed on the command
line of las_descent must not be smaller.

There must be one line for each size that can occur during the descent,
and the parameters must be so that there is a high chance to get at least
one relation.

Alternatively, the hint file may also use the syntax "55@0" instead of
"55r", to mean "bitsize 55 on size 0".

Writing a hint file can be done by hand. There is a helper script,
though, which can assist in this task. It can be used as follows (the
following information may also be used as a guide for how a hint file
should be created). First, one should start with a draft file, containing
rough guess data for the smallest large primes, at least one line for
each special-q side. For example:
    22@0 0 0 I=9 50000,22,24 100000,22,24
    22@1 0 0 I=9 50000,22,24 100000,22,24
because this is a guess, the 0 values for the average time and success
probability are normal.

Based on this, and replicating the configuration for the larger values,
the script will provide timing data as follows (we assume a bash-like
shell is used).

$ ./scripts/hintfile-helper.py --cadobindir ./build/`hostname` --datadir ~/Local/p59/ --prefix p59  --ntrials 100 --hintfile /tmp/p59.hint --qrange "$(echo {22..37}{r,a})"
22@0 0.0027 1.0000 I=9 50000,22,24 100000,22,24
22@1 0.0030 1.0000 I=9 50000,22,24 100000,22,24
23@0 0.0029 0.9900 I=9 50000,22,24 100000,22,24
23@1 0.0033 1.0000 I=9 50000,22,24 100000,22,24
24@0 0.0028 0.9700 I=9 50000,22,24 100000,22,24
24@1 0.0034 1.0000 I=9 50000,22,24 100000,22,24
25@0 0.0031 0.9500 I=9 50000,22,24 100000,22,24

Note the --qrange argument, which specifies the order in which the sizes
are tried.

You should pay attention to two things here. The success probability, and
the average time. Tinkering with parameters so as to lower the average
time is ok, as long as it leaves the success probability high. As q
grows, things get awry at some point, and you have to modify the
parameters so as to increase the success probability. In the experiment
above, success probability only 97% for 24r is unsatisfactory.

We can use the script to test alternative settings for this special-q
side:

$ ./scripts/hintfile-helper.py --cadobindir ./build/cassoulet --datadir ~/Local/p59/ --prefix p59 --ntrials 100 --hintfile /tmp/p59.hint --hintline "24r 0.0035 1.0000 I=9 50000,22,24,1.2 100000,24,45,1.5"
24@0 0.0034 1.0000 I=9 50000,22,24,1.2 100000,24,45,1.5

Another way to do the same thing is to first keep the first five lines of
the output of the first script run into our hint file, modify the fifth
(the one for 24r), and re-run. We get the following:
22@0 0.0033 1.0000 I=9 50000,22,24,1.2 100000,22,24,1.2
22@1 0.0031 1.0000 I=9 50000,22,24,1.2 100000,22,24,1.2
23@0 0.0034 0.9900 I=9 50000,22,24,1.2 100000,22,24,1.2
23@1 0.0030 1.0000 I=9 50000,22,24,1.2 100000,22,24,1.2
24@0 0.0032 1.0000 I=9 50000,23,26,1.2 100000,24,45,1.5
24@1 0.0028 1.0000 I=9 50000,22,24,1.2 100000,22,24,1.2
25@0 0.0029 0.9900 I=9 50000,23,26,1.2 100000,24,45,1.5
25@1 0.0032 1.0000 I=9 50000,22,24,1.2 100000,22,24,1.2
26@0 0.0038 0.9700 I=9 50000,23,26,1.2 100000,24,45,1.5

The process can then continue iteratively. Note that hintfile-helper.py
also accepts the --replace option, which rewrites the lines of the
hintfile you provide witht the measurements it does (which means, if you
have an editor open on this file, that you will have to explicitly reload
the file).

Here are a few hints about the influential parameters. Increasing I will
augment the time significantly, and will probably yield better success.
For special-q on the rational side, then the algebraic side parameters
need to be bumped up somewhat, because then there is a significant
unbalance in the norms. Beyond that, all parameters are bound to increase
mildly as q grows. mfb0 has to grow first, especially because lim remains
unchanged. Next lpb should grow. Setting lpb to above the current
special-q size is allowed, but might trigger loops of course (if on the
same side as the special-q).

Factor base file format:
------------------------

An entry is of the form:

q:n1,n2: r1,r2,r3

In the (frequent) case where n1,n2=1,0 this can be abridged with:

q: r1,r2,r3

Here, q is a prime or a prime power, ri are the corresponding roots and
the contribution that must be subtracted at these positions is (n1-n2)*logp
(assuming smaller powers of this prime have already be taken care of).
By position, we mean (a,b) such that a - b*ri = 0 mod q.

The roots ri must be sorted in increasing order.  If a root ri is greater
or equal to q, it means that this is a projective root: subtracting q
gives a root for the reciprocal polynomial (or equivalently, (1:(ri-q))
is the projective root).

It is allowed to have several lines with the same q, but there must be
only one line for a given (q,n1,n2) triple.

It is not assumed that the entries are sorted in increasing values of q.
For small prime and prime powers, this is clearly not the case, since we
might want to have all powers of the same prime at the same place in the
file.

Lines starting with a # are comments.


Rem:
----
For reference, the old factor base format was based on lines of the form:
p: r1,r2,r3
with no powers and no indication of the multiple of log p to be
subtracted (and no projective roots).