Factoring integers with large prime variations of the quadratic sieve

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 many 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