Variations on a theme: From QS to SSSIQS

Colin Percival, MITACS, SFU

Friday December 2nd, 2005 at 10:30am in K9509.

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.