Three-Large-Primes Variant of the Number Field Sieve. Modelling, Analysis and Simulation. (MAS)

摘要

The Number Field Sieve (NFS) is the asymptocially fastest know factoring algorithm for large integers. This method was proposed by John Pollard in 1988. Since then several variants have benn implemented with the objective of improving the siever which is the most time consuming part of this method (but fortunately, also the easiest to parallelise). Pollard's original method allowed one large prime. After that the two-large-primes variant led to substantial improvements. In the paper the authors investigate whether the three-large-primes variant may lead to any further improvement. We present theoretical expectations and experimental reguls. we assume the reader to be familiar with the NFS. As a side-result, we improved some formulae for Taylor coefficients of Dickman's rho function given by Patterson and Rumsey and Marsglai, Zaman and Marsaglia.