The three-large-primes variant of the number field sieve
The Number Field Sieve (NFS) is the asymptotically fastest known factoringalgorithm for large integers.This method was proposed by John Pollard in 1988. Sincethen several variants have been implemented with the objective of improving thesiever 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 thetwo-large-primes variant led to substantial improvements.In this paperwe investigate whether the three-large-primes variant may lead to any furtherimprovement. We present theoretical expectations and experimental results.We assume the reader to be familiar with the NFS.As a side-result, we improved some formulae for Taylor coefficients ofDickman's $ ho$ function given by Patterson and Rumsey andMarsaglia, Zaman and Marsaglia.
|Numerical Algorithms and Problems (acm F.2.1)|
|Factorization (msc 11Y05), Factorization; primality (msc 11A51)|
|Modelling, Analysis and Simulation [MAS]|
Cavallar, S.H. (2002). The three-large-primes variant of the number field sieve. Modelling, Analysis and Simulation [MAS]. CWI.