Talk:Rational sieve

From Wikipedia, the free encyclopedia

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.