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_{k}$ ,

$z=\prod _{{p_{i}\in P}}p_{i}^{{a_{i}}}$

and likewise, for suitable $b_{k}$ , we have

$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}}}\;\operatorname {(mod}\;n\operatorname {)}

(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 pair of factors of n, and the algorithm will terminate.

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):

2¹3⁰5⁰7⁰ = 2 ≡ 189 = 2⁰3³5⁰7¹.............(1)
2⁰3⁰5¹7⁰ = 5 ≡ 192 = 2⁶3¹5⁰7⁰.............(2)
2⁰3²5⁰7⁰ = 9 ≡ 196 = 2²3⁰5⁰7².............(3)
2³3⁰5⁰7¹ = 56 ≡ 243 = 2⁰3⁵5⁰7⁰.............(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^[1]), this reduces to 2⁴ ≡ 3⁸ (mod n), or 4² ≡ 81² (mod n). 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 3² ≡ 14² (mod n), which gives the factorization 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17.

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. Probably the most elegant method is to check whether $\lfloor n^{{1/b}}\rfloor ^{b}=n$ holds for any 1 < b < log(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 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.

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.

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

Number-theoretic algorithms

Primality tests	AKS test APR test Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin

Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization

Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's

Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's

Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve

Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's

Modular square root	Cipolla Pocklington's Tonelli–Shanks

Other algorithms	Chakravala Cornacchia LLL Integer square root Modular exponentiation Schoof's

Italics indicate that algorithm is for numbers of special forms

This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.