On the coefficients of the polynomial in the number field sieve

作     者：YANG Min MENG QingShu WANG ZhangYi LI Li ZHANG HuanGuo 

作者机构：International School of Software Wuhan University Computer School Wuhan University 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2015年第58卷第11期

页      面：182-190页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by National Natural Science Foundation of China(Grant Nos.61003267,61202385,61202386,61332019,61402339) National Basic Research Program of China(973 Program)(Grant No.2014CB340600) 

主　　题：cryptography integer factorization number field sieve polynomial selection coefficients zero roots complete discrimination system 

摘      要：Polynomial selection is very important in the number field sieve. If the number of relations a pair of polynomials can generate is closely correlated with the coefficients of the polynomials, we can select polynomials by checking the coefficients first, which can speed up the selection of good polynomials. In this paper, we aim to study the correlation between polynomial coefficients and the number of relations the polynomials can generate. By analyzing the zero roots, it is found that a polynomial with the ending coefficient containing more small primes usually can generate more relations than the one whose ending coefficient contains less. As a polynomial with more real roots usually can generate more relations, using the complete discrimination system,the requirements on the coefficients of a polynomial to obtain more real roots are analyzed. For instance, a necessary condition for a polynomial of degree d to have d distinct real roots is that the coefficient of degree d- 2should be negative or small enough. The result in the case d = 3 can be used directly in selecting polynomials generated by the nonlinear method, where d = 3 is already enough for practical purpose.