Rational sieve

Suppose we are trying to factor the composite number n. We choose a bound B, and identify the factor base (which we will call P), the set of all primes less than or equal to B. Next, we search for positive integers z such that both z and z + n are B-smooth — i.e. all of their prime factors are in P. We can therefore write, for suitable exponents a_i and b_i,

${\displaystyle z=\prod _{p_{i}\in P}p_{i}^{a_{i}}\qquad {\text{and}}\qquad z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}.}$

But z and ${\displaystyle z+n}$ are congruent modulo n, and so each such integer z that we find yields a multiplicative relation (mod n) among the elements of P, i.e.

${\displaystyle \prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}{\pmod {n}}}$

(where the a_i and b_i are nonnegative integers.)

When we have generated enough of these relations (it is generally sufficient that the number of relations be a few more than the size of P), we can use the methods of linear algebra to multiply together these various relations in such a way that the exponents of the primes are all even. This will give us a congruence of squares of the form a² ≡ b² (mod n), which can be turned into a factorization of n = gcd(a + b, n) × gcd(a − b, n). This factorization might turn out to be trivial (i.e. n = n × 1), in which case we have to try again with a different combination of relations, but with luck we will get a nontrivial pair of factors of n, and the algorithm will terminate.

We will factor the integer n = 187 using the rational sieve. We will arbitrarily try the value B = 7, giving the factor base P = {2,3,5,7}. The first step is to test n for divisibility by each of the members of P; clearly if n is divisible by one of these primes, then we are finished already. However, 187 is not divisible by 2, 3, 5, or 7. Next, we search for suitable values of z; the first few are 2, 5, 9, and 56. These four suitable values of z give four multiplicative relations (mod 187):

${\displaystyle 2^{1}3^{0}5^{0}7^{0}=2\equiv 189=2^{0}3^{3}5^{0}7^{1}}$

1

${\displaystyle 2^{0}3^{0}5^{1}7^{0}=5\equiv 192=2^{6}3^{1}5^{0}7^{0}}$

2

${\displaystyle 2^{0}3^{2}5^{0}7^{0}=9\equiv 196=2^{2}3^{0}5^{0}7^{2}}$

3

${\displaystyle 2^{3}3^{0}5^{0}7^{1}=56\equiv 243=2^{0}3^{5}5^{0}7^{0}}$

4

There are now several essentially different ways to combine these and end up with even exponents. For example,

• (1)×(4): After multiplying these and canceling out the common factor of 7 (which we can do since 7, being a member of P, has already been determined to be coprime with n^[1]), this reduces to 2⁴ ≡ 3⁸ (mod n). The resulting factorization is 187 = gcd(3⁴ + 2², 187) × gcd(3⁴ − 2², 187) = 11 × 17.

Alternatively, equation (3) is in the proper form already:

• (3): This says 3² ≡ 14² (mod n), which gives the factorization 187 = gcd(14 + 3, 187) × gcd(14 − 3, 187) = 11 × 17.