Rational sieve

In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the general number field sieve. While it is less efficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.

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 $a i$ and $b i$ ,

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 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.

\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 2 \equiv b 2 (mod n)$ , which can be turned into a factorization of $n = gcd(a + b, n) \times gcd(a - b, n)$ . This factorization might turn out to be trivial (i.e. $n = n \times 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.

Example

We will factor the integer $n = 187$ using the rational sieve. We will arbitrarily try the value $B = 7$ , giving the factor base $P =$ . 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):

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

()×(): 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 $24 \equiv 3 8 (mod n)$ . The resulting factorization is $187 = gcd(3 4 + 2 2, 187) \times gcd(3 4 - 2 2, 187) = 11 \times 17$ .

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

(): This says $32 \equiv 14 2 (mod n)$ , which gives the factorization $187 = gcd(14 + 3, 187) \times gcd(14 - 3, 187) = 11 \times 17$ .

Limitations of the algorithm

Like the general number field sieve, the rational sieve cannot factor numbers of the form $p m$ , where p is a prime and m is an integer. This is not a huge problem, though—such numbers are statistically rare, and moreover there is a simple and fast process to check whether a given number is of this form. Probably the most elegant method is to check whether $b = n$ holds for any $1 < b \leq log 2 (n)$ using an integer version of Newton's method for the root extraction.^[2]

The biggest problem is finding a sufficient number of z such that both z and $z + n$ are B-smooth. For any given B, the proportion of numbers that are B-smooth decreases rapidly with the size of the number. So if n is large (say, a hundred digits), it will be difficult or impossible to find enough z for the algorithm to work. The advantage of the general number field sieve is that one only needs to search for smooth numbers of order $exp(C (log(n)) 2/3 (log(log(n))) 1/3)$ for some $C > 0$ , rather than of order n as required here.^[3]

References

A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349. Available at [1].
A. K. Lenstra, H. W. Lenstra, Jr. (eds.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, New York, 1993.

Footnotes

^ Note that common factors cannot in general be canceled in a congruence, but they can in this case, since the primes of the factor base are all required to be coprime to n, as mentioned above. See modular multiplicative inverse.
^ R. Crandall and J. Papadopoulos, On the implementation of AKS-class primality tests, available at [2]
^ A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), p. 328