Inmathematics, therational sieve is a generalalgorithm forfactoring integers into prime factors. It is a special case of thegeneral number field sieve. While it is lessefficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.

Suppose we are trying to factor thecomposite numbern. We choose a boundB, and identify thefactor base (which we will callP), the set of all primes less than or equal toB. Next, we search for positive integersz such that bothz andz +n areB-smooth — i.e. all of their prime factors are inP. We can therefore write, for suitable exponentsa_i andb_i,

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

Butz and${\displaystyle z+n}$ are congruent modulon, and so each such integerz that we find yields a multiplicative relation(modn) among the elements ofP, i.e.

${\displaystyle \prod _{p_i\in P}{p}_i^{a_i}\equiv \prod _{p_i\in P}{p}_i^{b_i}(\mathrm{mod}n)}$

(where thea_i andb_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 ofP), we can use the methods oflinear algebra to multiply together these various relations in such a way that the exponents of the primes are all even. This will give us acongruence of squares of the forma² ≡b² (modn), which can be turned into a factorization ofn = 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 ofn, and the algorithm will terminate.

We will factor the integern = 187 using the rational sieve. We will arbitrarily try the valueB = 7, giving the factor baseP = {2,3,5,7}. The first step is to testn for divisibility by each of the members ofP; clearly ifn 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 ofz; the first few are 2, 5, 9, and 56. These four suitable values ofz 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 ofP, has already been determined to be coprime withn^[1]), this reduces to2⁴ ≡ 3⁸ (modn). The resulting factorization is187 = gcd(3⁴ + 2², 187) × gcd(3⁴ − 2², 187) = 11 × 17.

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

• (3): This says3² ≡ 14² (modn), which gives the factorization187 = gcd(14 + 3, 187) × gcd(14 − 3, 187) = 11 × 17.

Like the general number field sieve, the rational sieve cannot factor numbers of the formp^m, wherep is a prime andm 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 any1 < b ≤ log₂(n) using an integer version ofNewton's method for the root extraction.^[2]

The biggest problem is finding a sufficient number ofz such that bothz andz +n areB-smooth. For any givenB, the proportion of numbers that areB-smooth decreases rapidly with the size of the number. So ifn is large (say, a hundred digits), it will be difficult or impossible to find enoughz for the algorithm to work. The advantage of the general number field sieve is that one only needs to search for smooth numbers of orderexp(C (log(n))^2/3 (log(log(n)))^1/3) for someC > 0, rather than of ordern as required here.^[3]

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

• Integer factorization algorithms

• Articles with short description
• Short description matches Wikidata