  The two currently fastest general-purpose integer factorization algorithms
are the Quadratic Sieve and the Number Field Sieve. Both techniques are used to
find so-called smooth values of certain polynomials, i.e., values that factor
completely over a set of small primes (the factor base). As the names of the
methods suggest, a sieving procedure is used for the task of quickly
identifying smooth values among the candidates in a certain range. While the
Number Field Sieve is asymptotically faster, the Quadratic Sieve is still
considered the most efficient factorization technique for numbers up to around
100 digits. In this paper, we challenge the Quadratic Sieve by presenting a
novel approach based on representing smoothness candidates as sums that are
always divisible by several of the primes in the factor base. The resulting
values are generally smaller than those considered in the Quadratic Sieve,
increasing the likelihood of them being smooth. Using the fastest
implementations of the Self-initializing Quadratic Sieve in Python as
benchmarks, a Python implementation of our approach runs consistently 5 to 7
times faster for numbers with 45-100 digits, and around 10 times faster for
numbers with 30-40 digits. We discuss several avenues for further improvements
and applications of the technique.
