View Single Post
Old 2009-02-27, 18:01   #8
Tribal Bullet
jasonp's Avatar
Oct 2004

2×3×19×31 Posts

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
jasonp is offline   Reply With Quote