View Single Post
Old 2006-04-22, 02:24   #3
Tribal Bullet
jasonp's Avatar
Oct 2004

3·1,181 Posts
Default Msieve 1.06

New release now available. I decided to get this out the door because QS improvements have been stacking up. The QS implementation is now 10-20% faster at least, and includes a bug fix or two. The speedup is entirely due to getting rid of avoidable overhead in the sieve phase; it's a little embarrassing that there was so much of it.

This release also contains NFS filtering code. It's a relatively complete and memory-efficient implementation, and includes 2-pass duplicate removal, multi-pass singleton removal (with the first few passes adaptively running from disk file), multi-pass clique removal, and a merge phase that uses Gauss elimination with Markowitz pivoting and a few tricks I'm experimenting with. My test case is a C100, and it reduces 6.7M relations to a system of size 277k and average weight ~50 in about 5 minutes on the opteron.

I have no idea when the next version will be ready; NFS work is proceeding very slowly. The linear alegbra shouldn't be hard since lanczos code is already written, but I'll have to teach myself Nguyen's algorithm before the square root can get coded.

Happy factoring,
jasonp is offline   Reply With Quote