Séminaire de Cryptographie

Accueil     Présentation     Archives

Shi Bai

Algorithms for polynomial selection in the number field sieve

The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The running-time of the number field sieve depends on the quality of the chosen polynomials. The quality of the chosen polynomials can be modeled in terms of size and root properties. In this talk, we will describe some better algorithms to select polynomials with good size and root properties. The talk will be based on papers, Shi Bai, Cyril Bouvier, Alexander Kruppa and Paul Zimmermann. Better polynomials for GNFS. Math. Comp, 2015. Shi Bai, Richard Brent and Emmanuel Thomé. Root optimization of polynomials in the number field sieve. Math. Comp, 2015.