Cryptology ePrint Archive: Report 2013/583

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

Min Yang and Qingshu Meng and Zhangyi Wang and 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.

Category / Keywords: public-key cryptography / cryptography, number field sieve, polynomial selection,elementary geometric

Date: received 10 Sep 2013, last revised 17 Aug 2019

Contact author: qsmeng at 126 com

Available format(s): PDF | BibTeX Citation

Version: 20190817:084848 (All versions of this report)

Short URL: ia.cr/2013/583


[ Cryptology ePrint archive ]