View Single Post
Old 2009-02-27, 16:59   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

You can use a factor base that will skip over primes that will never divide the numbers produced at each step, and you can also use single and double large primes on numbers that survive that step, combined with generation of cycles. Put another way, whether you use QS, NFS or CFRAC the postprocessing behaves the same, manipulating graph quantities that are derived from the relations produced by the algorithm.

You can also use Bernstein's batch factoring algorithm to massively speed up trial division by larger primes, or his batch gcd algorithm to flag relations that are likely to be smooth. I'm quite partial to the latter.
jasonp is offline   Reply With Quote