Cryptology ePrint Archive: Report 2012/599

On the coefficients of the polynomial in the number field sieve

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

Category / Keywords: public-key cryptography / integer factorization, number field sieve, polynomial selection, coefficients

Publication Info: no

Date: received 24 Oct 2012, last revised 24 Jan 2013

Contact author: mqseagle at sohu com

Available format(s): PDF | BibTeX Citation

Version: 20130124:090037 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]