Rational sieve

From Wikipedia, the free encyclopedia

In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler. So while it is rather useless as a practical factoring algorithm, it is a helpful first step for those trying to understand how the general number field sieve works.

Contents 1 Method 2 Example 3 Limitations of the algorithm 4 References 5 Footnotes

[edit] 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) consisting of all primes smaller than 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 less than or equal to B. We can therefore write, for suitable a_k,

and likewise, for suitable b_k, we have

.

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.

(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 a²≡b² (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 factorization of n, and the algorithm will terminate.

[edit] Example

We will factor the integer n = 35 using the rational sieve. We'll arbitrarily try the value B=19, giving the factor base P={2,3,11,13,17,19}. (We cannot include 5 and 7 since they are actually factors of 35, which renders the algorithm unusable. Of course, if we already know the factors, we do not need to do the algorithm, but we will anyway to show that the algorithm works, i.e. for demonstration purposes.) Next, we search for values of z -- the first few are 1, 3, 4, 9, 13, 19, and 22, and we can stop there. The seven values of z give seven multiplicative relations (mod 35):

• 2⁰3⁰11⁰13⁰19⁰ = 1 ≡ 36 = 2²3²11⁰13⁰19⁰.............(1)

• 2⁰3¹11⁰13⁰19⁰ = 3 ≡ 38 = 2¹3⁰11⁰13⁰19¹.............(2)

• 2²3⁰11⁰13⁰19⁰ = 4 ≡ 39 = 2⁰3¹11⁰13¹19⁰.............(3)

• 2⁰3²11⁰13⁰19⁰ = 9 ≡ 44 = 2²3⁰11¹13⁰19⁰.............(4)

• 2⁰3⁰11⁰13¹19⁰ = 13 ≡ 48 = 2⁴3¹11⁰13⁰19⁰.............(5)

• 2⁰3⁰11⁰13⁰19¹ = 19 ≡ 54 = 2¹3³11⁰13⁰19⁰.............(6)

• 2¹3⁰11¹13⁰19⁰ = 22 ≡ 57 = 2⁰3¹11⁰13⁰19¹.............(7)

There are now several essentially different ways to combine these and end up with even exponents:

• (2)×(4)×(7): After multiplying these and canceling out common factors (which we can do since they are coprime with n),^[1] this reduces to 3² ≡ 2²19², or 3² ≡ 38². The resulting factorization is 35 = gcd(38-3,35) × gcd(38+3,35) = 35×1. The trivial factorization; try again.

• (1): This says 6² ≡ 1², which gives the factorization 35 = gcd(6-1,35) × gcd(6+1,35) = 5×7. Success!

Note that there were still other combinations we did not need to use, such as (3)×(5) and (2)×(6).

[edit] Limitations of the algorithm

The rational sieve, like the general number field 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.

The bigger 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 need only search for smooth numbers of order n^1/d for some positive integer d (typically 3 or 5), rather than of order n as required here.

[edit] 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. A draft is available at www.std.org/~msm/common/f9paper.ps.

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

[edit] Footnotes

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.