Special-q Techniques for Number Field Sieve to Solve Integer Factorization

摘要

Number Field Sieve is one of the best exist method for integer factorization. In this method, relation collection stage is the most time-consuming part and requires a large amount of memory. This paper reports comprehensive analysis between Pollard's algorithm and FK algorithm of special-q lattice sieving in Number Field Sieve. The experiments are performed using two widely used factoring tools CADO-NFS and GGNFS on the data sets ranging between 100-120 digits; since CADO-NFS is based on FK algorithm and GGNFS is based on Pollard's algorithm. Experiments are carried out using various parameters. The results are derived and influencing factors are reported. Through the results, it is shown that even though FK algorithm for sieving which avoids the lattice reduction compared with Pollard, the selection of special-q, influences on the performance of the sieving algorithm.