Paper 2012/599

On the coefficients of the polynomial in the number field sieve

Min Yang, Qingshu Meng, Zhangyi Wang, Li Li, and Huanguo Zhang

Abstract

Polynomial selection is very important in number field sieve. If the yield of a pair of polynomials is closely correlated with the coefficients of the polynomials, we can select polynomials by checking the coefficients first. This can speed up the selection of good polynomials. In this paper, we aim to study the correlation between the polynomial coefficients and the yield of the polynomials. By theoretical analysis and experiments, we find that a polynomial with the ending coefficient containing more small primes is usually better in yield than the one whose ending coefficient contains less. One advantage of the ending coefficient over the leading coefficient is that the ending coefficient is bigger and can contain more small primes in root optimizing stage. Using the complete discrimination system, we also analyze the condition on coefficients to obtain more real roots.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. no
Keywords
integer factorizationnumber field sievepolynomial selectioncoefficients
Contact author(s)
mqseagle @ sohu com
History
2013-01-24: last of 5 revisions
2012-10-25: received
See all versions
Short URL
https://ia.cr/2012/599
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/599,
      author = {Min Yang and Qingshu Meng and Zhangyi Wang and Li Li and Huanguo Zhang},
      title = {On the coefficients of the polynomial in the number field sieve},
      howpublished = {Cryptology ePrint Archive, Paper 2012/599},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/599}},
      url = {https://eprint.iacr.org/2012/599}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.