View Single Post
Old 2006-12-31, 20:41   #10
Tribal Bullet
jasonp's Avatar
Oct 2004

354310 Posts
Default 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:

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.
Happy new year, happy factoring,
jasonp is offline   Reply With Quote