Discussion related to cado-nfs

[Jayson King <jk@jaysonking.com>]

Hi. I found what I believe is a bug in polyselect2l.c, or at least in
the way parameters are chosen for it.

We have the leading rational coefficient l = p_1*p_2*q. p_1 and p_2 are
chosen from a set of primes in [P,2*P] where P is given as a parameter.
q is chosen as the product of some small primes in [2,251], the number
of which is given as a parameter. Two elements per p,proot progression
nearest to m0 on each q,qroot progression are considered.

When determining a value for P, it is taken that a larger value should
yield better polynomials overall, by forcing the third-highest algebraic
coefficient A_{d-2} to have a smaller maximum size due to the formula
|A_{d-2}_max| ~= m0/P^2. However, this is only part of it. The size of l
also influences the size of A_{d-2} in the expansion of the polynomial,
as described in Lemma 2.1 of Kleinjung 2006 "On polynomial selection for
the general number field sieve".

Effectively, |A_{d-2}_max| is increased by l, regardless of the choice
of P. This means potentially a lot of time is spent finding collisions
among large elements which are unlikely to yield a polynomial with as
small A_{d-2} as might be wished for.

I worked through an example using N = rsa155 challenge number.

params.c155 gives d=5, P=1e6, lq=4 (num factors in q) and norm_max of
exp(50). Using the initial A_d of 30030, we get:

m0 = (N/A_d)^(1/d) ~= 8.17e29
q <= q_1*q_2*...*q_lq = 251*241*239*233 ~= 3.37e9
l <= (2*P)^2*q ~= 1.35e22
norm_max ~= 5.18e21

m0/P^2 ~= 8.17e17, which is the limit on |A_{d-2}| implied by the value
of P. But, because l is much larger than 8.17e17, the size of |A_{d-2}|
is about l instead. Thus, too much work is done to find such
polynomials. We could find polynomials of similar quality with less work
by using smaller P.

Another thing to notice: compare the size of l to norm_max. For d>=5,
|A_{d-2}| should be much smaller than norm_max, or else we will be
forced to throw away the polynomials. Kleinjung's paper gives a method
for computing a bound on |A_{d-2}|.

>From Kleinjung's paper, we compute a minimum skewness:

skewness_min = (m0/norm_max)^(2/(d-2)) ~= 2.92e5, this assumes A_1 will
be of size m.

And we compute a bound on |A_{d-2}|

|A_{d-2}| <= norm_max*skewness_min^(d/2-(d-2)) ~= 9.60e18, which is
still much smaller than the l used.

Possible improvements:

- Compute a bound on q so that l will be a fraction of the bound
required for |A_{d-2}|. Or,

- Abort if the parameters don't make sense and force the parameters to
be fixed instead (not as nice).

I hope this report will be useful and I apologize for its verbosity.

Jayson King