### 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptographynumber field sievepolynomial selectionelementary geometric
Contact author(s)
qsmeng @ 126 com
History
2019-08-17: last of 2 revisions
See all versions
Short URL
https://ia.cr/2013/583

CC BY

BibTeX

@misc{cryptoeprint:2013/583,
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{https://eprint.iacr.org/2013/583}},
url = {https://eprint.iacr.org/2013/583}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.