We report the factorization of a 135-digit integer by the triple-large-prime variation of the multiple polynomial quadratic sieve. Previous workers  had suggested that using more than two large primes would be counterproductive, because of the greatly increased number of false reports from the sievers. We provide evidence that, for this number and our implementation, using three large primes is approximately 1.7 times as fast as using only two. The gain in efficiency comes from a sudden growth in the number of cycles arising from relations which contain three large primes. This effect, which more than compensates for the false reports, was not anticipated by the authors of   but has become quite familiar from factorizations obtained using the number field sieve. We characterize the various types of cycles present, and give a semi-quantitative description of their rather mysterious behaviour.
|Title of host publication||Proceedings ANTS-V (Sydney, Australia, July 7-12, 2002)|
|Editors||C. Fieker, D.R. Kohel|
|Place of Publication||Berlin|
|Publication status||Published - 2002|
|Name||Lecture Notes in Computer Science|