收录:
摘要:
The general number field sieve (GNFS) is asymptotically the fastest algorithm known for factoring large integers. One of the most important steps of GNFS is to select a good polynomial pair. Whether we can select a good polynomial pair, directly affects the efficiency of the sieving step. Now there are three linear methods widely used which base-m method, Murphy method and Kleinjung method. Base-m method is to construct polynomial based on the m-expansion of the integer, Murphy method mainly focuses on the root property of the polynomial and Kleinjung method restricts the first three coefficients size of the polynomial in a certain range. In this paper, we compare the size property and root property of the polynomials which select from the three methods. A good leading coefficient a(d) of f(1) is important. The good means that a(d) has some small prime divisors. Kleinjung method does not give a concrete method to choose a good a(d) in its first step. We choose these better a(d) first and store in a set A(d), then take the A(d) as input. Through the pretreatment we can get better polynomial and speed up the efficiency of Kleinjung method at the same time.
关键词:
通讯作者信息:
电子邮件地址: