Polynomial selection for the number field sieve

Abstract

The number field sieve is asymptotically the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The running time of subsequent steps depends on the quality of the chosen polynomials. In the thesis, we discuss the current state of the art in polynomial selection. Polynomial selection can be divided into three stages: polynomial generation, size optimization and root optimization. We give some analysis of polynomial generation algorithms. We then describe some improvements for polynomial size optimization and root optimization. The size optimization is based on determining a translation and then locally optimizing the polynomial. The root optimization is based on Hensel's lifting lemma and a root sieve on congruences classes modulo small prime powers. The improvements described here have been implemented and used to obtain some good polynomials in practice. We also discuss some recent progress on polynomial selection using lattice reduction.