View Single Post
Old 2007-12-04, 18:32   #5
akruppa's Avatar
Aug 2002

2,467 Posts

One part of the PhD I'm working on is optimizing ECM, P-1 and some other factoring algorithms (maybe P+1, Pollard rho is most likely useless) for NFS with more than two large primes on one side.

Peter's new idea for the P+/-1 stage 2 looks very attractive for the job as the asymptotic complexity drops from O(d (log d)^2) to O(d log d), d the degree of the polynomial we evaluate, and perhaps more importantly the implied constant drops by rather a lot. I.e. or a c200, B2=10^9 the old code took 4.0 seconds, the new code takes 1.0 second. I'm hopeful that a properly optimized implementation operating on, say, 96 or 128 bit moduli would be quite useful for refactoring. However, at the moment, even the GMP-based implementation in GMP-ECM isn't 100% complete so the small-modulus version will take a while yet.

akruppa is offline   Reply With Quote