International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 13 September 2013

Min yang, Qingshu Meng, Zhangyi Wang, Lina Wang, Huanguo Zhang
ePrint Report ePrint Report
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. 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.

Expand

Additional news items may be found on the IACR news page.