View Single Post
Old 2007-12-04, 18:07   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I considered this at one time for my lattice siever. However, I concluded
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 run-time is generally not productive,.

BTW, I split my cofactors with a 'tiny' QS implementation fine tuned
for 63-bit cofactors. Extending this to say 93 bits would be easy, and the
increase in time would not be great.
When using three large primes, the number of cofactors to split goes up by about 50x, and the majority of those are tri-composites that would require ECM or QS. The tiny QS code that I have can do about 100-200 factorizations of 85-bit numbers per second, and this is 10-20x slower than my SQUFOF code (the SQUFOF is quite fast and the QS isn't that great). So if dealing with composite cofactors takes 1% of the time now then it ends up taking 90% of the time when sieve values can have three large primes (i.e. 1000 x 1% = 1000%). This matches my experience with 3LP QS, dealing with so many larger cofactors is a giant pain. Pehaps the picture is different for very large sieving problems, but I'm somewhat doubtful about that.

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 100-150MB of memory. Dumping the batched relations to disk is also an option, and the dump files can be combined and moved to a high-memory 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 2007-12-04 at 18:18
jasonp is offline   Reply With Quote