MPQS with three large primes

P. Leyland, A.K. Lenstra, B. Dodson, A. Muffett, S. Wagstaff

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)


We report the factorization of a 135-digit integer by the triple-large-prime variation of the multiple polynomial quadratic sieve. Previous workers [6][10] 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 [6] [10] 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.
Original languageEnglish
Title of host publicationProceedings ANTS-V (Sydney, Australia, July 7-12, 2002)
EditorsC. Fieker, D.R. Kohel
Place of PublicationBerlin
ISBN (Print)3-540-43863-7
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'MPQS with three large primes'. Together they form a unique fingerprint.

Cite this