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
-
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},
url = {https://eprint.iacr.org/2012/599}
}
