No, there's no way to just look at one of those numbers and immediately know a collection of small primes that does not divide it. This is why CFRAC has so much trouble even with 40-digit numbers, and QS completes in milliseconds. Using a sieve in QS improves the asymptotic complexity over CFRAC, as well as the implied constant in the asymptotics (getting both of these is pretty unusual in an advanced algorithm; look at how big a number has to be before NFS becomes faster than QS despite the additional overhead of NFS)
Last fiddled with by jasonp on 2009-02-27 at 18:02
|