mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2006-01-31, 07:28   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Exclamation 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
jasonp is offline   Reply With Quote
Old 2006-02-04, 04:18   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2006-04-22, 02:24   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 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
jasonp is offline   Reply With Quote
Old 2006-07-31, 02:51   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2006-08-23, 13:22   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2006-08-24, 00:57   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2006-08-25, 13:31   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default Msieve 1.10

Another emergency bug fix in the multiple precision library.

Sorry for the churn everybody.

jasonp
jasonp is offline   Reply With Quote
Old 2006-09-08, 04:06   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2006-09-09, 02:23   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2006-12-31, 20:41   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

348910 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:

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.
Happy new year, happy factoring,
jasonp
jasonp is offline   Reply With Quote
Old 2007-01-05, 06:33   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66418 Posts
Default 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
jasonp is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 07:12.

Sun Oct 25 07:12:20 UTC 2020 up 45 days, 4:23, 0 users, load averages: 2.11, 1.82, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.