View source for Rational sieve

{{Short description|Integer factorization algorithm}}
In [[mathematics]], the '''rational sieve''' is a general [[algorithm]] for [[integer factorization|factoring integers into prime factors]]. It is a special case of the [[general number field sieve]]. While it is less [[algorithmic efficiency|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]] {{Mvar|n}}. We choose a bound ''{{Mvar|B}}'', and identify the ''[[factor base]]'' (which we will call {{Mvar|P}}), the set of all primes less than or equal to ''{{Mvar|B}}''. Next, we search for positive integers {{Mvar|z}} such that both ''{{Mvar|z}}'' and {{Math|''z'' + ''n''}} are ''{{Mvar|B}}''-[[smooth number|smooth]] &mdash; i.e. all of their prime factors are in ''{{Mvar|P}}''. We can therefore write, for suitable exponents {{Math|''a''<sub>''i''</sub>}} and {{Math|''b''<sub>''i''</sub>}},

<math>z=\prod_{p_i\in P} p_i^{a_i} \qquad \text{and} \qquad z+n=\prod_{p_i\in P} p_i^{b_i}.</math>

But {{Mvar|z}} and <math>z+n</math> are congruent modulo {{Mvar|n}}, and so each such integer {{Mvar|z}} that we find yields a multiplicative relation [[Modular arithmetic|(mod]] {{Mvar|n}}) among the elements of ''{{Mvar|P}}'', i.e.

:<math>\prod_{p_i\in P} p_i^{a_i} \equiv \prod_{p_i\in P} p_i^{b_i} \pmod n</math>

(where the {{Math|''a''<sub>''i''</sub>}} and {{Math|''b''<sub>''i''</sub>}} 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 ''{{Mvar|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 {{Math|''a''<sup>2</sup> &equiv; ''b''<sup>2</sup> (mod ''n'')}}, which can be turned into a factorization of {{Math|1=''n'' = gcd(''a'' + ''b'', ''n'') &times; gcd(''a'' &minus; ''b'', ''n'')}}. This factorization might turn out to be trivial (i.e. {{Math|1=''n'' = ''n'' &times; 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 {{Mvar|n}}, and the algorithm will terminate.

== Example ==

We will factor the integer {{Math|1=''n'' = 187}} using the rational sieve. We will arbitrarily try the value {{Math|1=''B'' = 7}}, giving the factor base {{Math|1=''P'' = {{mset|2,3,5,7}}}}. The first step is to test {{Mvar|n}} for divisibility by each of the members of {{Mvar|P}}; clearly if {{Mvar|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 {{Mvar|z}}; the first few are 2, 5, 9, and 56. These four suitable values of {{Mvar|z}} give four multiplicative relations (mod 187):

{{NumBlk|:|<math>2^1 3^0 5^0 7^0  = 2 \equiv 189 = 2^0 3^3 5^0 7^1</math>|{{EquationRef|1}}}}
{{NumBlk|:|<math>2^0 3^0 5^1 7^0  = 5 \equiv 192 = 2^6 3^1 5^0 7^0</math>|{{EquationRef|2}}}}
{{NumBlk|:|<math>2^0 3^2 5^0 7^0  = 9 \equiv 196 = 2^2 3^0 5^0 7^2</math>|{{EquationRef|3}}}}
{{NumBlk|:|<math>2^3 3^0 5^0 7^1  = 56 \equiv 243 = 2^0 3^5 5^0 7^0</math>|{{EquationRef|4}}}}

There are now several essentially different ways to combine these and end up with even exponents. For example,

*({{EquationNote|1}})×({{EquationNote|4}}): After multiplying these and canceling out the common factor of 7 (which we can do since 7, being a member of ''{{Mvar|P}}'', has already been determined to be coprime with {{Mvar|n}}<ref>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]].</ref>), this reduces to {{Math|2<sup>4</sup> &equiv; 3<sup>8</sup> (mod ''n'')}}. The resulting factorization is {{Math|1=187 = gcd(3<sup>4</sup> + 2<sup>2</sup>, 187) &times; gcd(3<sup>4</sup> &minus; 2<sup>2</sup>, 187) = 11 &times; 17}}.

Alternatively, equation ({{EquationNote|3}}) is in the proper form already:

*({{EquationNote|3}}): This says {{Math|3<sup>2</sup> &equiv; 14<sup>2</sup> (mod ''n'')}}, which gives the factorization {{Math|1=187 = gcd(14 + 3, 187) &times; gcd(14 &minus; 3, 187) = 11 &times; 17}}.

== Limitations of the algorithm ==

Like the general number field sieve, the rational sieve cannot factor numbers of the form {{Math|''p''<sup>''m''</sup>}}, where {{Mvar|p}} is a prime and {{Mvar|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 {{Math|1={{floor|1=''n''<sup>1/''b''</sup>}}<sup>''b''</sup> = ''n''}} holds for any {{Math|1 < b &leq; log<sub>2</sub>(''n'')}} using an integer version of [[Newton's method]] for the root extraction.<ref>R. Crandall and J. Papadopoulos, ''On the implementation of AKS-class primality tests,'' available at [https://www.apple.com/acg/pdf/aks3.pdf]</ref>

The biggest problem is finding a sufficient number of ''{{Mvar|z}}'' such that both ''{{Mvar|z}}'' and {{Math|''z'' + ''n''}} are {{Mvar|B}}-smooth. For any given ''{{Mvar|B}}'', the proportion of numbers that are ''{{Mvar|B}}''-smooth decreases rapidly with the size of the number. So if {{Mvar|n}} is large (say, a hundred digits), it will be difficult or impossible to find enough ''{{Mvar|z}}'' 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 {{Math|exp(''C'' (log(''n''))<sup>2/3</sup> (log(log(''n'')))<sup>1/3</sup>)}} for some {{Math|''C'' > 0}}, rather than of order {{Mvar|n}} as required here.<ref>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), p. 328</ref>

== 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 [https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf].
*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 ==

{{reflist}}

{{number theoretic algorithms}}

{{DEFAULTSORT:Rational Sieve}}
[[Category:Integer factorization algorithms]]