Discussion related to cado-nfs

[Shi Bai <shih.bai@gmail.com>]

Dear Robert,

Thanks for reporting it.

First, for the output,

"I note that when polyselect_ropt is run with -v, the following is printed:
# Info: s1param->nbest_sl: 368 (= size_total_sublattices*ropteffort)
"
You are right. The output information is flawed: the nbest_sl should
be independent of ropteffort. It does affect other parameters however.


"For example, if polyselect_ropt is run on the attached polynomial,
with -area 429496729600000000 -Bf 34359738368 -Bg 17179869184, the
Murphy-E score of the resulting polynomial is as follows:
-ropteffort 1: 2.026e-09
-ropteffort 10: 1.972e-09
"

I think this is not totally unexpected. The quick answer is the
candidate polynomial got discarded during the test root sieve
procedure. For convenience, I will denote the polynomial generated
from "-ropteffort 1: 2.026e-09" as the "BestPoly".

The ropt code starts with generating many sublattices of linear
rotation of the form (a, b) (mod M) where M is a product of small
prime powers. They denote f + (a*x + b)*g. The best sublattices are
recorded in a global queue using the rough E-score (this is lognorm +
alpha). Then it starts some short test root sieve on these (a, b) (mod
M) to filter out some good (a, b) (mod M) in terms of MurphyE-score.
Note there will be some discrepancies between the E-score and
MurphyE-score, e.g. good polynomials with E-score may have worse
MurphyE-score during the test root sieve.

The BestPoly was generated by a rotation of (-159023*x -
1150894624933)*g(x) + f(x) from the original polynomial f(x), g(x),
together with some minor size-optimization in the end. For such
rotation, it sits on the sublattice:

# Info: tune [ 363], E: 55.36, lat (0, 506257, 523547) (mod 665280)

This sublattice is found in both cases (ropt = 1 and/or 10). However,
when ropt = 10, there are many sublattice candidates whose MurphyE
score is better than this BestPoly (during the test root sieve). Thus
the sublattice for this BestPoly was discarded (before entering the
actual root sieve) when ropt = 10.

Cheers,
Shi

On Tue, Dec 14, 2021 at 4:48 AM Robert Balfour <rhb11931@gmail.com> wrote:
>
> Dear all,
>
> Mersenneforum user Gimarel has reported that using a higher ropteffort 
> value can sometimes produce a lower scoring polynomial.
>
> For example, if polyselect_ropt is run on the attached polynomial, with 
> -area 429496729600000000 -Bf 34359738368 -Bg 17179869184, the Murphy-E 
> score of the resulting polynomial is as follows:
>
> -ropteffort 1: 2.026e-09
> -ropteffort 10: 1.972e-09
> -ropteffort 100: 1.965e-09
>
> Maybe this is just an unlucky consequence of the way the priority queues 
> are managed, but I'm concerned that perhaps at some stage a queue is either 
> being cut too short or not being sorted properly.
>
> I note that when polyselect_ropt is run with -v, the following is printed:
>
> # Info: s1param->nbest_sl: 368 (= size_total_sublattices*ropteffort)
>
> ...and despite what this would suggest, the value 368 does not change when 
> ropteffort is increased!
>
> Best regards,
> Robert