2006-01-31, 07:28 | #1 |
Tribal Bullet
Oct 2004
3·1,163 Posts |
Msieve announcements
It is with great exhaustion that I announce the availability of Msieve 1.04, which is completely reorganized and now includes about 1/3 of a general number field sieve implementation. There is no NFS postprocessing code yet, the limit is still 125 digits, and the demo application still defaults to the quadratic sieve; but I had to start somewhere.
This release is for test purposes only. You will need to install the Gnu Scientific Library because the NFS polynomial selection has to perform nasty numerical integrations I didn't feel like implementing just yet (does anyone know if there's non-GPL numerical integration code available that is adaptive, handles doubly-infinite intervals and can deal with multiple integrable singularities? I used to love numerical integration and extrapolation methods, but it would be nice to avoid having to build them all from scratch just so Msieve can stay public domain). Be sure to read the documentation if you feel brave enough to play around with it. My first priority is going to be getting some sort of end-to-end NFS cobbled together, but that also means that the performance is not going to be very good for a long time. The QS module had been under development for about 9 months before I made a public release, but this stuff is only in month 2. Nevertheless I'm trying to make the pieces that are there as high-quality as possible, even if future versions replace them wholesale. I also want the NFS code to be immediately useful; it's a waste of time to start using NFS for 30-digit factorizations just because the implementation is too crude. The next release or two should come quickly; the Mac version is completely broken (QS and NFS) and people will no doubt notice various other broken things. I should also mention that there is a new Yahoo! group, nfs-hacks, that has recently started. We hope that people interested in number field sieve implementations will join in. Happy factoring, jasonp EDIT: Msieve can be downloaded at http://www.boo.net/~jasonp/qs.html EDIT 2: The Msieve source and a precompiled windows binary can be downloaded from here Last fiddled with by jasonp on 2009-10-19 at 10:06 Reason: Added url |
2006-02-04, 04:18 | #2 |
Tribal Bullet
Oct 2004
3×1,163 Posts |
Msieve 1.05
Now available at the usual place.
This is primarily a bug fix release, though there are a few cleanups in the line siever. jasonp |
2006-04-22, 02:24 | #3 |
Tribal Bullet
Oct 2004
3·1,163 Posts |
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 |
2006-07-31, 02:51 | #4 |
Tribal Bullet
Oct 2004
3·1,163 Posts |
Msieve 1.07
Now available. Major changes include:
- added an NFS linear algebra phase that builds the matrix and reuses the existing Lanczos codebase. Writing this has made me realize how crude the QS matrix phase really is - tweaked the NFS filtering code to produce slightly better matrices and reduced worst-case memory use - a few QS sieving tweaks; small factorizations are slightly faster now - by popular demand: the makefile builds QS code only by default; a separate make target builds the NFS code (and pulls in the external library it needs). (see the change log for the complete list) For the next version I hope to integrate NFS sieving with NFS filtering, rearrange some code, and document a bunch of NFS stuff. The version after that will hopefully have NFS square root code, but I don't know how long my brain will need to understand the math. Happy factoring, jasonp |
2006-08-23, 13:22 | #5 |
Tribal Bullet
Oct 2004
3×1,163 Posts |
Msieve 1.08
Just uploaded the next version. Highlights include:
- An expression evaluator and a bunch of additions and fixes from Brian Gladman - Major reorganization, cleanup, documenting and (minor) optimization of the NFS source - More minor QS improvements. Once again, the multiplier selection has been tweaked. Factorizations in progress can use the new msieve version only if it chooses the same multiplier as before See the changelog for the complete list. The next version will attempt some kind of NFS square root phase. Happy factoring, jasonp Last fiddled with by jasonp on 2006-08-23 at 13:22 |
2006-08-24, 00:57 | #6 |
Tribal Bullet
Oct 2004
3×1,163 Posts |
Msieve 1.09
It turns out that a last minute bug fix in v1.08 exposed another bug in the multiple-precision library, so I've released v1.09
Philippe, the limit on the input size applies to both QS and NFS (they both use the same MP library). Increasing the limit should be simply a matter of incrementing MAX_MP_WORDS from 13 to 14, commenting out the check for 125 digits or less, and recompiling. I'll PM the instructions on running the line siever as part of your GGNFS run. Happy factoring, jasonp |
2006-08-25, 13:31 | #7 |
Tribal Bullet
Oct 2004
3×1,163 Posts |
Msieve 1.10
Another emergency bug fix in the multiple precision library.
Sorry for the churn everybody. jasonp |
2006-09-08, 04:06 | #8 |
Tribal Bullet
Oct 2004
3·1,163 Posts |
Msieve 1.11
Now available. It turns out a fix was needed for the previous fix to the multiple precision library. This release also includes the very beginning of an NFS square root.
Happy factoring, jasonp |
2006-09-09, 02:23 | #9 |
Tribal Bullet
Oct 2004
3·1,163 Posts |
Msieve 1.12
Previous versions from 1.08 on were broken on 64-bit systems, now fixed
I've updated the download page to officially make 1.07 available. Happy (someday bug-free) factoring, jasonp |
2006-12-31, 20:41 | #10 |
Tribal Bullet
Oct 2004
3489_{10} Posts |
Msieve 1.13
Now available at the usual place. Highlights include:
- increased the limit on inputs to 164 digits, as threatened - GNFS now works end-to-end, automatically; just add a '-n' when running the demo. That's not to say it's very efficient; my test 100-digit factorization needs approximately 80 hours to complete (compared to 12 hours using the QS code). Also, the square root is somewhat memory-hungry and there seems to be occaisional trouble with the linear algebra not generating an algebraic square all the time. If you want to give it a try, keep the input to 105 digits or less, anything larger is completely untested. Also, if you want to try using msieve to complete a factorization started using GGNFS, let me know and we can all save some testing time. - other little changes all over the place The next release will be sometime soon; I want to get to a few neglected things, add documentation, and test on platforms other than 32-bit x86. Note to L33t HaXoRs, from the NFS readme: Code:
Before taking the plunge and using this code, you should understand that the NFS module still needs a lot of work before it can truly handle big problems. I haven't done any of that work because it's so difficult to get even something basic up and running. That means you have a really tough job to do: not use it. One of the unfortunate side effects of cryptography in general, and RSA in particular, is that it's just so damn cool. Factoring big numbers has an undeniable whiff of the subversive to it, and lots of people are attracted to that. More and more stuff in the information age is protected by RSA, and that means more and more people have an interest in breaking it, usually by factoring the RSA modulus. The number field sieve is the only practical tool for breaking RSA; if you try anything else, you will fail. Period. So, given that bank accounts, computer games, and factoring contest prize money is all protected by RSA, and other NFS tools require a lot of sophistication from the people using them, I suspect that flocks of people will want to use Msieve to solve factoring problems that are much too large (i.e. 155 digits and up). If you are one of those people, *please* don't use Msieve. NFS is so hard that making sure it works takes extensive testing, which has not been done at all for factorizations over about 105 digits as of version 1.13; in addition, the performance difference between a basic and an advanced implementation of NFS is a factor of at least 10, so by refusing to learn how to use advanced tools like GGNFS you've turned a months-long factoring job into a years-long factoring job. Finally, I can't stop you from wasting your time, but I also can't stop you from making your friends believe Msieve will work, or from starting up distributed computing projects that use Msieve to waste the time of thousands of strangers. To the extent that my opinion matters to you, I think this would be bad. jasonp |
2007-01-05, 06:33 | #11 |
Tribal Bullet
Oct 2004
6641_{8} Posts |
Msieve 1.14
Now available. Highlights include:
- optimize the NFS square root; it's much faster and somewhat more frugal with memory now - add support for free relations in the NFS postprocessing - fix a long-standing bug in the buffering of data to be written to the savefile, that occaisionally caused corrupted savefile output (this is the reason I'm doing another release so soon) Happy factoring, jasonp |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Primenet maintenance announcements | Madpoo | PrimeNet | 7 | 2015-11-12 05:50 |
GMP-ECM Announcements | akruppa | GMP-ECM | 12 | 2013-02-27 15:30 |
Phrot announcements | rogue | Conjectures 'R Us | 33 | 2010-01-22 19:39 |
msieve help | em99010pepe | Msieve | 23 | 2009-09-27 16:13 |
Announcements | hhh | Prime Cullen Prime | 10 | 2007-05-16 20:42 |