Paper 2013/583

polynomial selection for the number field sieve in geometric view

Min yang, Qingshu Meng, Zhangyi Wang, Lina Wang, Huanguo Zhang

Abstract

Polynomial selection is the first important step in number field sieve. A good polynomial not only can produce more relations in the sieving step, but also can reduce the matrix size. In this paper, we propose to use geometric view in the polynomial selection. In geometric view, the coefficients' interaction on size and the number of real roots are simultaneously considered in polynomial selection. We get two simple criteria. The first is that the leading coefficient should not be too large or some good polynomials will be omitted. The second is that the coefficient of degree $d-2$ should be negative and it is better if the coefficients of degree $d-1$ and $d-3$ have opposite sign. These criteria tell us where to find them and how to efficiently find them. Using these new criteria, the computation can be reduced while we can get good polynomials. Many experiments on large integers show the effectiveness of our conclusion.