mersenneforum.org - View Single Post

jasonp · 2009-02-27, 16:59

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.

2009-02-27, 16:59	#6
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	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.