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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
cryptographynumber field sievepolynomial selectionelementary geometric
Contact author(s)
qsmeng @ 126 com
2019-08-17: last of 2 revisions
2013-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Min Yang and Qingshu Meng and Zhangyi Wang and Lina Wang and Huanguo Zhang},
      title = {Polynomial Selection for the Number Field Sieve in an Elementary Geometric View},
      howpublished = {Cryptology ePrint Archive, Paper 2013/583},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.