The Polymial Selection For The Number Field Sieve

Integer factorization is an old problem which can be described as: With a givenpositive integer, try to write it as a product of several primes. There are a lot ofalgorithms to solve integer factorization problem. Among those algorithms, thenumber field sieve is the asymptotically fastest algorithm. But the number field sievethere still exist many problems, which affects the efficiency of the algorithm,especially the polynomial selection step. Therefore, it is necessary to research thepolynomial selection.The general number field sieve mainly includes polynomial selection, sieving,matrix step and find square root step. Each step has a difficult problem to solve.Polynomial selection is the first step of the number field sieve. Whether we can selecta good polynomial, directly affects the efficiency of the whole algorithm. Now thereare three linear methods widely used which are base-m method、Murphy method andKleinjung method. There are two aspects influencing the choice of polynomials. Oneis size of the coefficients, another is the root property. In this paper, we compare thesize property and root property of the polynomials which selected from the threemethods. We get the conclusion that Kleinjung method is the best one.Kleinjung method doesn’t give a concrete method to choose a good leadingcoefficient in its first step. A good leading coefficient is that the leading coefficienthas some small prime divisors. Therefore, instead of considering every leadingcoefficient we can only consider those good ones. Based on this, we can choose thesebetter leading coefficient first and store them in a set Ad, then take the set Ad as ainput. Through the pretreatment we can get better polynomials, while reducing theunnecessary attempt, thereby increasing the efficiency of polynomial selection.We implemented the pretreatment system. First we make an overall design of thepretreatment system. Then according to the detailed design, we program. Finally wemake analysis and comparison of the experimental data. In our experiment we willdiscuss two cases. The first is different upper bounds of the experime ntal; second isdifferent granularity. Through experiments, we demonstrate the correctness andfeasibility of the pretreatment system.