Variations on a theme: From QS to SSSIQS
Colin Percival, MITACS, SFU
Abstract: The Quadratic Sieve method of integer factorization is, as a general approach, the fastest available for factoring general integers (those not of a special form or known to have small factors) of 30--130 digits. That said, nobody ever uses the Quadratic Sieve itself; instead, two variations, the Multiple Polynomial Quadratic Sieve (MPQS) and the Self-Initializing Quadratic Sieve (SIQS, also known as HMPQS) are used, usually together with one large prime (P-) or two large primes (PP-). After giving a quick overview of the Quadratic Sieve, I will describe the progression of improvements -- each providing a twofold speedup -- from QS to MPQS, on to SIQS, and finally to my own contribution, SSSIQS.