[Cado-nfs-discuss] new polynomial selection strategy

paul zimmermann Paul.Zimmermann at inria.fr
Fri Apr 29 17:38:55 CEST 2016


I've put in the git version a new polynomial selection strategy which appears
to give better results than cado-nfs 2.2.0 on a few sample numbers. Some
technical details can be found below. I would appreciate some feedback on
your favorite numbers, including the Murphy-E value found and the total
polynomial selection time, both for 2.2.0 and the git version. Especially
regressions (in terms of Murphy-E value) are welcome.

Technical details: the new strategy takes into account in the first phase
not only the norm of the algebraic polynomial (aka lognorm), but also the
projective alpha value, and the expected gain due to rotation (which depends
on the estimated rotation space). The new stage 1 indicator (still named
"lognorm") is thus more precise, and usually the best polynomial is among
the ten best after the first phase, thus it suffices to keep about 100
polynomials (nrkeep=100). In addition we use a new iteration on top of the
LLL-algorithm to better optimize the norm of the algebraic polynomial.

Paul Zimmermann

More information about the Cado-nfs-discuss mailing list