20071203, 15:54  #1 
Tribal Bullet
Oct 2004
3,529 Posts 
NFS with 5 and 6 large primes
I realized last week that the arbitraryprecision library needed by msieve's algebraic square root code could be put to other uses, in particular it can be used to implement Bernstein's batch factoring algorithms to speed up the sieving stage. As a proofofconcept I modified msieve's line siever to use three rational and/or algebraic large primes, but to defer actually trying to factor bi and tricomposites until a few hundred thousand of them have accumulated. Once that happens, batch factoring isolates the ~2.5% of relations whose cofactors actually need processing.
As an example, I used a recent C135 factored by Hallstein using GNFS. His run used 28bit large primes, and my mods used the product of all primes < 2^26 to perform batch factoring. Sieve reports with remaining cofactors smaller than 2^81 get batched and submitted to Bernstein's algorithm, and bi and tricomposites that do not contain at least one factor below 2^26 are aborted. The results are really encouraging. The current code finds twice as many relations and only takes 1.5x longer to do so, for a net speedup of 25%. This is because the vast majority of tricomposites need no explicit factoring at all, and only 1% of the tricomposites that need factoring actually need to be split into three primes (the input would need all three large primes < 2^26, which is extremely rare). The speedup approaches 50% as the norms increase with larger b values, when it becomes feasible to use three large primes on both sides. The extra time needed seems to be split evenly between the batch factoring and the factoring of a much larger number of sieve reports. This isn't going to make a line siever competitive with a good lattice siever, but the same batch factoring techniques can be used with a lattice siever and could conceivably gain the same kinds of speedups for large jobs. jasonp 
20071204, 15:43  #2 
"Ben"
Feb 2007
6332_{8} Posts 

20071204, 16:18  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:
that memory requirements were too great. Furthermore, my code spends so little time splitting the cofactors, that the speed increase offered by batch factoring did not seem worth it. Optimizing something that takes less than 1% of the runtime is generally not productive,. BTW, I split my cofactors with a 'tiny' QS implementation fine tuned for 63bit cofactors. Extending this to say 93 bits would be easy, and the increase in time would not be great. 

20071204, 18:07  #4  
Tribal Bullet
Oct 2004
3,529 Posts 
Quote:
bsquared, the algorithm is from page 18 of http://cr.yp.to/talks/2004.07.07/slides.pdf. Bernstein wants to use it to factor entire sieve values instead of just the parts containing large primes, but I believe in incremental changes :) I'm still getting a handle on the memory use needed, you don't need to batch very many relations in order to get most of the asymptotic speedup (100k is plenty). Basically it looks like sieving speed can double if you can spare 100150MB of memory. Dumping the batched relations to disk is also an option, and the dump files can be combined and moved to a highmemory machine for batch factoring if necessary. However, it's kind of wasteful of disk space when only 2% of what you dump will end up being useful. Last fiddled with by jasonp on 20071204 at 18:18 

20071204, 18:32  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
One part of the PhD I'm working on is optimizing ECM, P1 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 GMPbased implementation in GMPECM isn't 100% complete so the smallmodulus version will take a while yet. Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where do I send my PRP primes with large k?  Trilo  Riesel Prime Search  3  20130820 00:32 
48bit large primes!  jasonp  Msieve  24  20100601 19:14 
lots of large primes  Peter Hackman  Factoring  2  20080815 14:26 
Why only three large primes  fivemack  Factoring  18  20070510 12:14 
What is the use of these large primes  Prime Monster  Lounge  34  20040610 18:12 