Paper 2013/583

Polynomial Selection for the Number Field Sieve in an Elementary Geometric View

Min Yang, Qingshu Meng, Zhangyi Wang, Lina Wang, and Huanguo Zhang

Abstract

Polynomial selection is one important step in the number field sieve. A good polynomial can reduce the factorization time. In this paper, we propose a new model for the polynomial selection in an elementary geometric view. With this model, many existing requirements on polynomial selection can be taken into consideration simultaneously. With this model, the criterion for a polynomial to be ideal is that its leading coefficient should be as small as possible, all coefficients be skewed uniformly, the signs of even degree coefficients should alternate, and the signs of odd degree coefficients should alternate too. From the ideal criterion, two practical criteria are drawn. The first is that the leading coefficient should be as small as possible. The second is that the signs of coefficients of degree $d-2$ for polynomials of degree $d$ should be negative. These two criteria are confirmed by lots of experiments and adopted by Cado-NFS project.