
Variations on a theme: From QS to SSSIQSColin 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 30130 digits. That said, nobody ever uses the Quadratic Sieve itself; instead, two variations, the Multiple Polynomial Quadratic Sieve (MPQS) and the SelfInitializing 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. 