Rational Sieve - Method

Method

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 ,

and likewise, for suitable, we have

.

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

(where the a_i and b_i are nonnegative integers.)

When we have generated enough of these relations (it's 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 a2≡b2 (mod n), which can be turned into a factorization of n, 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.