Rational sieve

Template:Short description 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 Template:Mvar. We choose a bound Template:Mvar, and identify the factor base (which we will call Template:Mvar), the set of all primes less than or equal to Template:Mvar. Next, we search for positive integers Template:Mvar such that both Template:Mvar and z + n are Template:Mvar-smooth — i.e. all of their prime factors are in Template:Mvar. We can therefore write, for suitable exponents a_i and b_i,

$z=\prod _{p_i\in P}{p}_i^{a_i}\text{and}z+n=\prod _{p_i\in P}{p}_i^{b_i}.$

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

$\prod _{p_i\in P}{p}_i^{a_i}\equiv \prod _{p_i\in P}{p}_i^{b_i}(\mathrm{mod}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 Template:Mvar), 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 Template:Mvar, 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 = Template:Mset. The first step is to test Template:Mvar for divisibility by each of the members of Template:Mvar; clearly if Template:Mvar 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 Template:Mvar; the first few are 2, 5, 9, and 56. These four suitable values of Template:Mvar give four multiplicative relations (mod 187):

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 Template:Mvar, has already been determined to be coprime with Template:Mvar), 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.

Limitations of the algorithm

Like the general number field sieve, the rational sieve cannot factor numbers of the form p^m, where Template:Mvar is a prime and Template:Mvar 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 ⌊n^1/b⌋^b = n holds for any 1 < b ≤ log₂(n) using an integer version of Newton's method for the root extraction.

The biggest problem is finding a sufficient number of Template:Mvar such that both Template:Mvar and z + n are Template:Mvar-smooth. For any given Template:Mvar, the proportion of numbers that are Template:Mvar-smooth decreases rapidly with the size of the number. So if Template:Mvar is large (say, a hundred digits), it will be difficult or impossible to find enough Template:Mvar 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 Template:Mvar as required here.

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 [2].
• 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.