Talk:Rational sieve
 | This article has not yet been rated on Wikipedia's content assessment scale. |
The article says:
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 screws up the algorithm. Of course, if we already know the factors, we do not need to do the algorithm, but we will anyway to show that it works.)
I don't understand this. Does this mean that if we don't know the factors, and some of them are, inadvertently, in our factor base, the method fails? Why? And how useful could the method be if it often fails? —RadRafe 22:00, 16 December 2006 (UTC)
- If you're actually trying to factor a number (knowing nothing else about it), the first thing you try is direct division by all primes up to...well, as high as you can go given your time and computation constraints. If that doesn't work, then you would try a fancier method like this one. So it's reasonable and realistic to assume that any prime in the factor base has already been tested for divisibility. Alternatively, you could say that the full algorithm is: 1. Pick a factor base. 2. Test each prime in the factor base for divisibility. 3. Proceed with the algorithm. Regardless, in point of fact, the method actually isn't that useful for factoring big numbers, and it does often fail (when you can't find enough z's), but it's pedagogically useful as a simple version of the special number field sieve and general number field sieve, and that's indeed the only context in which I've seen it discussed. —Preceding unsigned comment added by Sbyrnes321 (talk • contribs)
I have just replaced the old example (factoring 35 but cheating on the selection of P by skipping the actual factors 5 and 7) with a better example (factoring 187 using P={2,3,5,7}). As a bonus, the new example is shorter. On the downside, I couldn't find any way to get the trivial factorization 187 = 1*187 to fall out of the new example's four simultaneous congruences, so it loses that bit of verisimilitude. --Quuxplusone (talk) 00:39, 10 February 2010 (UTC)