We present the results of many factorization runs with the single and double large prime variations (PMPQS, and PPMPQS, respectively) of the quadratic sieve factorization method on SGI workstations, and on a Cray C90 vectorcomputer. Experiments with 71--, 87--, and 99--digit numbers show that for our Cray C90 implementations PPMPQS beats PMPQS for numbers of more than 80 digits, and this cross--over point goes down with the amount of available central memory. For PMPQS a known theoretical formula is worked out and tested that helps to predict the total running time on the basis of a short test run. The accuracy of the prediction is within 10 of the actual running time. For PPMPQS such a prediction formula is not known and the determination of an optimal choice of the parameters for a given number would require many full runs with that given number, and the use of an inadmissible amount of CPU--time. In order yet to provide measurements that can help to determine a good choice of the parameters in PPMPQS, we have factored <b>many</b> numbers in the 66 -- 88 decimal digits range, where each number was run once with a specific choice of the parameters. In addition, an experimental prediction formula is given that has a restricted scope in the sense that it only applies to numbers of a given size, for a fixed choice of the parameters of PPMPQS. So such a formula may be useful if one wishes to factor many different large numbers of about the same size with PPMPQS.

Numerical Algorithms and Problems (acm F.2.1)
Factorization; primality (msc 11A51), Factorization (msc 11Y05)
CWI
Department of Numerical Mathematics [NM]
Large-scale computing

Boender, H, & te Riele, H.J.J. (1995). Factoring integers with large prime variations of the quadratic sieve. Department of Numerical Mathematics [NM]. CWI.