Rational Sieve - Example

Example

We will factor the integer n = 187 using the rational sieve. We'll 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. The four suitable values of z give four multiplicative relations (mod 187):

• 21305070 = 2 ≡ 189 = 20335071.............(1)

• 20305170 = 5 ≡ 192 = 26315070.............(2)

• 20325070 = 9 ≡ 196 = 22305072.............(3)

• 23305071 = 56 ≡ 243 = 20355070.............(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), this reduces to 24 ≡ 38, or 42 ≡ 812. The resulting factorization is 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17.

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

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