sieve theory

Sieve theory is a type of mathematics that deals with methods of factoring numbers, by finding their factors using different methods of eliminating certain possibilites. Sieve theory is used primarily in cracking encryption and finding large primes.

Sieve methods were created to attack the well-known Goldbach and twin primes problems. It turns out that there are excellent reasons why sieve methods alone cannot solve these problems, but they give partial information on these and many other problems where the `deeper' methods of analytic number theory, such as exponential sums, will not work. For example pairs of consecutive odd numbers which are either prime or very hard to factorise do keep on occurring.

Sieve methods can be purely combinatorial like the sieve of Eratosthenes, or more complex. The (Multiple Polynomial) Quadratic Seive is the most famous example of recent Sieve Theory, and works, essentially, in three steps:

1. Find a factor base and solve the congruences x 2º n (mod p) for each prime p in the factor base.
2. Perform the sieving operation to find sufficient f(r)’s which can be completely factored over the factor base.
3. Use Gaussian elimination to find a product of the f(r)’s which is a perfect square.

More complex methods, especially the number field sieve, are faster for larger numbers (more than 100 or so digits.) Although the specifics of the method are beyond me, the abstract for the original paper introducing the sieve reads as follows:

The number field seive is an algorithm to factor integers of the form r^e ± s for small positive r and s... This leads to a general purpose factoring algorithm that is asymptotically substantially faster than the fastest factoring algorithms known so far, such as the multiple polynomial quadratic seive... The algorithm has proved quite practical: it took us only a few weeks to factor numbers that would have taken several years, had we used the multiple polynomial quadratic seive.