-   Msieve (
-   -   Msieve announcements (

jasonp 2006-01-31 07:28

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,

EDIT: Msieve can be downloaded at [url][/url]

EDIT 2: The Msieve source and a precompiled windows binary can be downloaded from [url=""]here[/url]

jasonp 2006-02-04 04:18

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

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

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

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 2006-08-24 00:57

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

Msieve 1.10
Another emergency bug fix in the multiple precision library.

Sorry for the churn everybody.


jasonp 2006-09-08 04:06

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

Msieve 1.12
Previous versions from 1.08 on were broken on 64-bit systems, now fixed :mad:
I've updated the download page to officially make 1.07 available.

Happy (someday bug-free) factoring,


jasonp 2006-12-31 20:41

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 2007-01-05 06:33

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 2007-01-12 04:53

Msieve 1.15
Now available. Major changes include:

- bug fixes, cleanups, memory use reduction and documentation for the NFS square root.

- an overhaul of the linear algebra code, that lets QS factorizations benefit from the much more sophisticated NFS matrix handling

- miscellaneous NFS fixes, and changes for powerpc and x86_64 systems

I'm reasonably confident that NFS factorizations will succeed by default now, although they will proceed much too slowly for my taste :)

The next version will probably take a few months; I want to overhaul the NFS polynomial selector and fold in the latest algorithmic ideas, some of which have never been implemented before.

Happy factoring,

jasonp 2007-01-17 05:51

Msieve 1.16
A few internal changes here, as well as a fix for a silly bug in the multiple precision library (that was causing NFS polynomial selection to quit early).

I've started looking at the polynomials produced by the pol5 code in GGNFS, and compared to the ones produced by msieve the total yield of optimized polynomials should be about 2.2x higher. The reason it's so much more than that in practice is that the sieving region is the wrong shape.

Happy factoring,

jasonp 2007-03-13 02:46

Msieve v1.17
Now available. Highlights include:

- Much better NFS filtering. The current implementation will automatically determine the right matrix size given the current dataset and the level of sparsity desired; it also includes several algorithmic enhancements

- Bug fixes all over the NFS code, some quite serious

- The beginnings of a skewed NFS polynomial selector (currently turned off)

- Pollard Rho factorization is performed automatically. Factorizations with many small factors will complete much faster now

- Recursive factorization has been pushed into the library. Now all factors found are reported at once, in increasing order

This version should have all the machinery in place to complete factorizations started by GGNFS (thanks to Greg Childers for providing a sample SNFS factorization to train the library on). My limited experience here is that msieve uses much less memory (~6x less) to construct the matrix, and the resulting matrix is somewhat larger but much lighter than GGNFS run on the same set of relations.

I haven't been able to reproduce the slowdowns reported when using gcc 4.1.1, but I only managed to try on x64

Happy factoring,

jasonp 2007-04-05 05:09

Msieve v1.18
Now available. Major changes include:

- more automatic tuning of NFS filtering, plus a new postprocessing phase for the merged relations
- bug fixes all over the NFS code
- a fix for a nasty bug in the long division routine

Priorities for the near future, in approximately the order I want to do them, are:

- add support for 'a' values > [tex]2^{32}[/tex] in NFS relations (this should finally allow msieve to act as a drop-in postprocessor for GGNFS)
- add cache blocking to the linear algebra
- work on a skewed polynomial selector

Happy factoring,

jasonp 2007-04-17 14:27

Msieve v1.19
Now available. Highlights include:

- a major overhaul of the linear algebra. I've added cache blocking, use of MMX registers on 32-bit x86 systems, and a fix (I hope) for the trouble people have been seeing with the linear algebra restarting. This version should handle the linear algebra for large NFS jobs 4-5x faster than v1.18!

- changed the format of the factor base file. The new format makes all of the parameters used in an NFS run manually configurable. Restarting an existing NFS job with this msieve version will convert to the new format automatically

- more bug fixes all over

The next version will probably have improvements to the NFS polynomial selection, documenting of the NFS filter phase, and some QS work too (Bill Hart has pointed out the need for more automatic tuning of the QS sieving).

Happy factoring,

jasonp 2007-05-02 04:23

Msieve v1.20
Now available. Highlights include:

- support for NFS relations with 64-bit 'a' values. This should let msieve finish any factorization started with GGNFS

- a lot of QS changes. The biggest is that the core sieving code is now compiled over and over again with different optimization flags and preprocessor directives, and the best version of the sieving code is chosen at runtime. This is basically a do-it-yourself 'fat binary' that should achieve increased performance across a range of processors (though the difference is not that large, 5-10% is typical with smaller factorizations seeing the biggest gains)

- lots of little changes in the NFS postprocessing. This includes bug fixes and documentation of the NFS filtering

The QS changes are still in progress, and there's a lot of potential for more tuning, especially on low-memory machines. I hope to do some of that tuning for the next version, and finally get around to improved NFS polynomial selection.

Happy factoring,

jasonp 2007-05-12 02:48

Msieve v1.21
Now available. Highlights include:

- Much improved NFS filtering, driven by the pounding everyone here is giving the NFS code

- updated MSVC build and MSVC versions of the assembly code, both courtesy of Brian Gladman

- fixes and documentation all over

The next version will hopefully deal with lingering problems several users are reporting, and will hopefully include multithreaded linear algebra.

Happy factoring,

PS: @smh:
Fri May 11 10:52:36 2007 prp49 factor: 6214371966272720891412679817612071803187468972909
Fri May 11 10:52:40 2007 prp62 factor: 13602227447995293360238994329010469074018220326044935134602609

jasonp 2007-05-27 06:01

Msieve v1.22
Now available. Highlights include:

- multithreaded linear algebra for both QS and NFS. This is still sort of a work in progress, and the speedup with two threads is far short of 2x, but it's very cool to solve a matrix for a C211 in just 28 hours.

- the demo binary now will read in numbers in octal or hex format

- bug fixes all over

Brian Gladman is hard at work removing the dependency on the Gnu Scientific Library, and hopefully I'll be able to merge that in for the next version. Other than that, I want to try some more really big NFS jobs, and if nothing unusual shows up I'll go back to NFS polynomial selection.

Happy factoring,

jasonp 2007-06-03 23:01

Msieve v1.23
Now available. This is an interim release to get some linear algebra and NFS filtering fixes out, that seem to be necessary to complete big NFS jobs using msieve.

The plan for the next version is the same as before. Happy factoring,

jasonp 2007-06-25 05:14

Msieve v1.24
Now available. Highlights include:

- removed the dependency on the Gnu Scientific Library. It was a fair amount of work, and lots of credit is due to Brian Gladman for helping out. If anybody wants high-performance numerical integration and polynomial rootfinding code that's free and not a mess, it's in there now.

- tweaked the NFS filtering to handle some of the hard jobs people have tried

- several NFS bug fixes

The removal of GSL is the first step in the long-awaited overhaul of the NFS polynomial selection. That's my top priority now, so hopefully the next version will see some meaningful progress in that regard.

Happy factoring,

jasonp 2007-06-28 03:44

Msieve v1.25
This is an emergency release that fixes a QS problem that affects the core sieving loops for some processors (antiroach, it's the reason you get a seg fault)


jasonp 2007-08-02 13:31

Msieve v1.26
Now available. This is primarily to propagate a fix for a fairly major NFS filtering bug. There's also a bug in the linear algebra for people using MSVC (reported by Timmy above), and I'm working on a fix.

The polynomial selection work is ongoing, and harder than I expected. The NFS poly generation code hasn't changed in this released, since the improved stuff isn't close to ready.

Happy factoring,

jasonp 2007-10-02 05:51

Msieve v1.27
Now available. Highlights include:

- increased the allowed input size to 235 digits (MAX_MP_WORDS=25). No more recompiles to handle big SNFS jobs

- added memory and performance optimizations to the linear algebra code. The result should use 15% less memory and should be slightly (~2%) faster

- a lot more messing around with GNFS polynomial selection, but nothing ready for testing yet

- fixes for a few little things

People have spent a lot of time pounding on the NFS postprocessing code in the last few months, so I think I should spend more time trying to improve it. The square root should be more efficient and multithreaded, I'll look at 64-bit optimizations for the linear algebra, and the NFS filtering has to go on a memory diet. There are also some interesting algorithmic tricks from the sparse matrix literature that I want to explore.

Happy factoring,

jasonp 2007-10-04 03:41

Msieve v1.28
I just posted this emergency release. It fixes the bug referenced above as well as some 64-bit compile errors.

jasonp 2007-10-28 16:35

Msieve v1.29
Now available. Highlights include:

- Major changes to the Lanczos routines. The new version incorporates linear algebra checkpoint and restart; checkpoints happen for large matrices only, once every 2-3 hours and whenever the library is interrupted. The demo binary can restart from a previous checkpoint with the -ncr instead of the -nc2 option. The updated source is also slightly faster

- Major overhaul of the NFS linear algebra driver. Nothing visible at the user level, but it's a lot better now. If you want to use this library version with a previously-completed factorization, you should redo any postprocessing from scratch

- Allowed the large prime bound, and the number of relations used, in the NFS filtering to be specified from the command line. See the new usage in the demo binary

- Miscellaneous fixes all over

The plan for the next version is the same. People are starting to throw NFSNET-size jobs at the NFS postprocessing, and this is quite close to the limit of what the current library can handle. It needs to scale much better, and that means incorporating industrial-strength external libraries instead of my stupid toy subroutines.

- the linear algebra also needs to move to a thread-pool type implementation instead of spawn-and-join. I also will be experimenting with matrix-reordering techniques that should isolate very small dense matrix blocks, and if there are enough of these in the typical matrix then the code can be made much faster and more memory efficient

- the NFS filtering is near the limit of what it can handle. The memory use is terrible on 64-bit systems because pointers are twice as large, and filtering is taking forever because the data structures used are sized suboptimally and have bad worst-case behavior. I'll be experimenting with the Judy library to fix this

- (if time allows) optimize/multithread the FFTs used in the NFS square root. I would love to use FFTW but it's not worth changing the license

Please be on the lookout for suspicious behavior from the new code.

Happy factoring,

jasonp 2007-11-16 08:23

Msieve v1.30
Now available. This is a bug fix release, since an unusually large number of fixes have piled up in the last week or so. The only new feature is the more efficient NFS filtering embodied in the code I posted earlier.

The goals for the next version have not changed.

Happy factoring,

jasonp 2007-12-14 05:39

Msieve v1.31
Now available. Highlights include:

- Provision is made for compiling and running GMP-ECM. If you have the GMP and GMP-ECM libraries, and run make with 'ECM=1' at the end, then the demo will compile a wrapper and link those libraries to it. All factoring inputs will get P+-1 and ECM to the 15-digit level (it takes about 1 second), and running the msieve binary with '-e' will cause it to expend more P+-1 and ECM effort (up to the 35 digit level) before aborting and running the main QS code. The cutoffs are somewhat tuned to give up as early as possible, and to scale the amount of work done so that ECM never takes up more than about 10% of the total runtime. The official binary uses GMP 4.2.2 compiled with --enable-fat, so it should run at high speed on any x86 system (but watch out for crashes, in case I did something wrong and your system is incompatible with my test rig).

- A lot of work on NFS line sieving. The new line siever implements the optimizations described [url=""]here[/url] and has been reformatted to be more readable. Some of this stuff is still experimental

- Lots of internal library changes and cleanups

Based on discussions in the GGNFS mailing list, the next step is going to involve merging part of this msieve version into the GGNFS codebase. The standalone msieve library will still contain NFS code (I will probably prefer to use it for testing), but it's time to merge these two development efforts. GGNFS contains highly efficient NFS polynomial selection and sieving, while msieve has very good postprocessing, and it would be a waste of everyone's time to reinvent the things each package doesn't have. Plus, the GGNFS project has many (>>1) developers, who should be able to continue maintaining my code if I ever put it down. Once that's done, the next step is to make the NFS square root require less memory (than the linear algebra, at least). Doing this right is going to be harder than I thought, so it may take a while.

Happy factoring,

jasonp 2007-12-16 18:52

Msieve v1.32
Now available. I wanted to get this out the door because another NFSNET job is imminent, and there's a potential for a big linear algebra speedup in this version. The windows binary probably will not be much faster, and my 2-CPU linux box is only 4% faster, but multi-core linux machines are reported to be enormously sped up using multithreaded lanczos with this patch.

The GGNFS codebase uses this version of msieve as a baseline.

Happy factoring,

jasonp 2008-01-13 19:47

Msieve v1.33
Now available. Highlights include:

- optimizations in the early stages of NFS filtering
- fixes for handling savefiles larger than 4GB in windows
- a lot of bug fixes all over the library
- a new extra-cool web page (now using Web 1.0 technology)

Be on the lookout for suspicious behavior with this new version, it
has many invasive changes.

Happy factoring,

jasonp 2008-03-23 04:49

Msieve 1.34
Now available. Highlights include:

- Added a native port of the NFS polynomial selection tools from GGNFS. This is a major work in progress, and has a lot of rough edges right now, but it should allow equivalent polynomials to what GGNFS can manage. Note that I've removed the assembly code and many of the obscure parts of the original version; on the plus side, this allows full optimization and makes the code thread-safe, but on the minus side it's currently 2.5x slower than the version in GGNFS. The extra code gets compiled if you use 'make' with ECM=1

- Added tweaks to the NFS filtering that many of you have been kind enough to test out

- Forced the NFS square root to always use IEEE double precision, since trying to guess whether you're using 53-bit or 64-bit registers has caused too many painful debugging episodes. Also added what I think is a fix for the NFS square root problems people have reported, when building with 64-bit MSVC (it's in related code). Can somebody try a square root with the latest version?

- Added many QS cleanups (not faster, just less hackish)

- Added a number of fixes and tweaks from several contributors

Assuming nobody discovers an emergency problem, I'm going to be either working on miscellaneous long-range msieve things, or not.

Happy factoring,

jasonp 2008-04-14 05:03

Msieve v1.35
Now available. Highlights include

- A lot of work on NFS polynomial selection (still a major work in progress)

- A bunch of fixes for Visual Studio. This should fix porting problems in the last version, upgrade the build project to use MSVC 9.0, and should also fix a bug in the NFS square root that showed up in MSVC but also occurs with gcc (thanks to the MSVC users for helping out with this one).

Future work will continue the overhaul of the polynomial selection, and if time allows I'll experiment with using 128-bit vectors to speed up the linear algebra.

Please post followups in one of the other threads in this subforum. Happy factoring,


jasonp 2008-05-17 20:26

Msieve v1.36
Now available. Highlights include:

- a lot of work on NFS polynomial selection; all polynomials are now saved in a file, though none of the other features (limited ranges, limited time) is supported yet

- a lot of NFS fixes and tweaks

- improved cache size detection

I've tried to change the linear algebra to use vectors wider than 64 bits, but could not get the runtime to be faster than the 64-bit time.

The next version should continue current work, and should incorporate GMP-ECM v6.2

Happy factoring,

jasonp 2008-08-27 15:02

Msieve v1.37
Now available. Highlights include:

- A lot of cleanup in the NFS poly selection (still a work in progress)

- A lot of cleanup and optimization in the NFS filtering. The new version should also be faster because it removes several disk based passes. Also, this version now is a lot smarter about handling free relations, and your SNFS jobs will see a large number of extra free relations added.

- Added the '-p' switch to run the demo binary at idle priority

- Miscellaneous bug fixes everywhere

The prospect of describing the NFS filtering at the CADO workshop means that I'll be busy playing with this part of the code for the near future.

Happy factoring,

jasonp 2008-09-25 01:49

Msieve v1.38
Now available. Highlights include:

- A lot of ECM fixes, plus use of GMP-ECM v6.2.2; the demo binary does not have SSE2 support, and this really helps stage 2, so if you want the highest speed you should still compile your own

- Optimizations in the NFS square root that double the speed and halve the memory use

- Bug fixes everywhere, plus a few NFS filtering tweaks

Happy factoring,

PS: Forgot a minor tweak or two; v1.38 has been uploaded again

tmorrow 2008-10-03 12:02

Is GMP-ECM v6.2.2 available? ECMNET and Inria are only reporting v6.2.1.

jasonp 2008-10-03 12:34

[QUOTE=tmorrow;144383]Is GMP-ECM v6.2.2 available? ECMNET and Inria are only reporting v6.2.1.[/QUOTE]
No, that was a typo, sorry.

jasonp 2008-11-22 18:20

Msieve v1.39 beta
There are enough invasive changes in the next release that I wanted to post a beta first for people to test:


Highlights include:

- a completely rewritten NFS polynomial selector. The current version actually finds better polynomials than pol5 does, but in much longer time. In fact, when testing RSA120 it generated a polynomial with the best Murphy alpha I've ever seen (-7.92 !) The demo binary also allows you to specify leading coefficient ranges, and the library now listens to any time limits that are set on polynomial selection (sorry this has taken so long, I know I suck). The stage 2 optimization code, i.e. what pol51opt does, is also enormously better, and for large problems is hundreds of times faster while still finding the best polynomials.

- a lot of patches by Brian Gladman that make the inline asm compile correctly with Intel and Microsoft's compiler, on both windows and linux, both 32- and 64-bit (this was amazingly painful). I've also revamped some of the asm, so that QS is now actually (slightly) faster. We know that QS works, but were hoping someone could verify the NFS code still works in the expected time when compiled with MSVC.

- a set of fixes to the linear algebra that hopefully reduces the number of problem matrices that cause weeks of wasted work right now. Serge, can you verify that the problem factorization we went over now at least generates a matrix without empty and duplicate columns?

- changes to the NFS filtering so that the clique processing is only rerun after the merge phase proves that it would be advantageous to do so

If nobody finds stupid mistakes of mine, I'll make the full release next week.

Batalov 2008-11-23 02:00

my tests went fine. Good stuff!
My 2^743-3 (that had problems with 1.38 before, twice) went through fine. I did, from scratch, -nc1 10000000,10000000 (1.2 hrs) and started -nc2 and tested the resulting matrix for empty or duplicate columns (use the "dump.c" program that I PM'd). Cannot say if the BL will be successful (it takes 5 days*4 threads), but so far, so good. The dumper test has passed. I am pretty sure that this matrix looks good. (I don't know if dumper test is now simply built in. I am going to read the source and diffs. later)

So, I think 1.39-beta is ready for M857.

Bruce, Greg, please nc1, nc2 and after matrix is built -- the dumper test as per PM.

Thanks, Jason!


10metreh 2008-11-23 12:44

I did a quick QS test on R71. I found that v1.39b was 2% slower than v1.38! I hope this is only normal fluctuations, though.

jasonp 2008-11-26 13:55

Msieve v1.39 beta 2
Now available:

[url=""]win32 binary[/url]


- fixed 64-bit NFS poly selection; it was completely broken

- added poly skew to the factor base file format, logfile, and internal structures (not used internally, yet)

- lowered the size of most A5 coefficients that are searched, and increased the time per coefficient

- fixed almost all compile warnings

- added forgotten typo to the NFS filtering

- added more MSVC tweaks from Brian Gladman; the MSVC project will now link with GMP and GMP-ECM by default. See the readme in the build.vc9 directory if you don't want them.

The shoddy state of this beta has me peeved, but hopefully this will be the last one before a full release later in the week.

jasonp 2008-12-02 03:51

Msieve v1.39
Full release is now available (essentially no changes from beta2)

Don't get too attached to the current NFS polynomial selector, I have big plans for improvements in v1.40

Happy factoring,

Batalov 2008-12-10 04:27

Two simple patches to (for v.1.39)
Those who use may want to add somewhere around line 1317 the SKEW to .fb file (it started its internal life in msieve and is reported in ggnfs.log and may be used in versions >= 1.39):
open(OF, ">$FBNAME");
print OF "N $N\nSKEW $SKEW\n"; # patch #1
for my $i (reverse 0..$DEGREE) {
print OF "A$i $COEFVALS{$i}\n";
if(!$COEFHASH{Y1}) { # patch #2 for the Y1/Y0-less .poly files
print OF "R1 $COEFHASH{Y1}\n";
print OF "R0 $COEFHASH{Y0}\n";
(patch #2 is just a convenience thingy - sometimes one gets a poly from old-timer users (or a program-generated), who have "m:" but not "Y1:"/"Y0:")... my 2 cents...

jasonp 2009-03-02 04:03

Msieve v1.40 beta
I have not updated the web page, but a beta of the next version is now available (it's been a while, and bug fixes have piled up).


Highlights include:

- Major internal changes to NFS poly selection; the .p file now outputs polynomials in GGNFS format, and the code now optimizes and reports Murphy's E score, so polynomial scores are now directly comparable to that of the pol5 code in GGNFS

- A fix for a typo that made QS a lot slower

- Huge swaths of NFS code have been made into common code, for bsquared's impending attempt to add three large prime support to QS. This includes the batch factoring code, hashtable code and most of the NFS filtering code

- Miscellaneous bug fixes eveywhere (see the changelog for details). Optimizations to NFS with huge excess will have to wait until v1.41

Please make sure things compile on whatever platforms and compilers you have, and seem to work okay. Replies should go in other threads. I'll give it maybe a week before considering a full release.

jasonp 2009-03-04 14:46

Msieve v1.40 beta 2
Now available:


This fixes MSVC compilation and a bunch of small problems. Keep up the pounding!

jasonp 2009-03-24 14:31

Msieve v1.40
Okay, it's finally available. Changes from beta2 include a streamlining of the MSVC project files and fixes for a few more typos.

Plans for the future involve adding a further excess-removal phase to the NFS filtering, and continued work on NFS polynomial selection. If time allows I'll also do a little QS work, but v1.41 should have a much shorter turnaround time than v1.40 did so I make no promises.

Happy factoring,

jasonp 2009-04-04 03:06

Msieve v1.41
Now available. This adds fixes for a lot of problems reported in the last week or so, as well as a first draft of code that can better deal with huge amounts of excess NFS relations.

Happy factoring,

jasonp 2009-04-04 14:33

PS: The 1.41 source and binary were just updated as of this message to fix an incorrectly fixed bug

jasonp 2009-06-06 04:32

Msieve v1.42 beta
It still needs a little work, but there's enough that's new here that I want to get an early beta out for all you involntary testers out there. Major changes include:

- new, hopefully bulletproof rootfinder; throw your worst SNFS polynomials at it and see

- degree 4 and degree 6 polynomial selection. The minimum GNFS input size has been lowered to just under 90 digits (there's no way it can be faster than QS when the input is that small), and you will now get degree-4 polynomials for 90-100 digit inputs. Depending on whether the sieving is actually faster compared to degree 5, I might raise the upper bound for degree 4 to 105 digits. Degree 6 is not done yet, it needs a better root sieve

- poly selection parameters for inputs over 155 digits. It will still be slow, but at least it won't complain

- plus a bunch of small tweaks

Let me know how it goes (in another thread :)


jasonp 2009-07-07 20:22

Msieve v1.42 beta 2
Now available:


There are a lot of changes since the last beta:

- NFS polynomial selection chooses degree 4 for 85-102 digit inputs

- the NFS filtering has been greatly rearranged, and will now attempt to minimize the number of disk passes based on the number of relations and how much memory the machine has. The demo binary now has a '-mb' switch that lets you specify how much memory to assume. Intermediate information is also cached on disk, to speed up multi-pass filtering. The end result is that NFS filtering will now be faster when your machine has more memory; I've seen 2x speedups on my own tests but the potential (for e.g. Bruce's machines that have tons of memory but slow disk) is much greater

- The linear algebra now includes orthogonality checks that happen periodically, as well as just before a checkpoint file is written. These checks can catch many memory corruption errors, and in fact have already done so on at least one big LA run

I'll be unable to work on the code for a little while; please send feedback to the v1.42 thread.

Happy factoring,

jasonp 2009-07-12 02:55

Beta 3
Now available:


This includes fixes for nasty filtering bugs and two memory leaks spotted by valgrind, as well as a tweak to the filtering that reduces unnecessary memory use somewhat. It also includes fixes for some of the huge number of type conversion warnings noticed by the latest gcc.

jasonp 2009-07-20 04:46

Msieve v1.42
Very few changes from beta 3.

I've decided that continuity of this project requires better resources than I've been giving it, and so there is now [url=""]an Msieve SourceForge project[/url] for hosting the repository and releases. Developers who know the code and want write access are welcome to join. Unfortunately I've only committed revision history starting at v1.41, otherwise the new release would never be ready.

I think the next release will be somewhat delayed; there are big changes I want to make, and now you can watch as I make them :)

Happy factoring,

Batalov 2009-08-30 21:33

[URL][/URL] :

It's not just you! [URL=""][B][COLOR=#0080ff][/COLOR][/B][/URL] looks down from here.

jasonp 2009-09-26 14:37

Msieve v1.43 beta
Available at [url][/url]

This is just SVN 62 with all the bells and whistles compiled in. Assuming nobody reports nasty problems, I'll post a full release on the sourceforge page in a few days.


- GMP or MPIR is now required to compile msieve. These are now easy to build on windows, and the NFS square root is 2.5x faster (compared to the toy large-integer code in previous releases) and will continue to accelerate as these packages improve

- NFS filtering allows relations to have any number of large primes up to 48 bits in size

- the initial stages of the NFS linear algebra and square root now use less memory, and I have ideas to improve on even that

- small bug fixes all over

jasonp 2009-10-18 20:50

Msieve v1.43
Now available on the sourceforge page, with minimal changes from the beta.

Happy factoring,

Andi47 2009-10-19 05:13

Can you please post the link to the sourceforge-project into the first posting of this thread? (I have found it now in the posting about 1.42 (posting #52) and bookmarked it, but - especially for newcomers - the link seems a bit hidden when it is placed only somewhere in the middle of the thread.)

jasonp 2010-02-05 04:54

Msieve v1.44
Now available at sourceforge. This includes a merge of the GPU code into mainline, as well as GPU and non-GPU windows binaries.

Happy factoring,

jrk 2010-02-05 05:00

thanks Jason

Andi47 2010-02-05 05:54


jasonp 2010-04-22 03:47

Msieve v1.45
Now available on the sourceforge page. Major features include a tighter merge of the CPU and GPU poly selection code, the porting of the GPU algorithms into a CPU version (that's pretty slow), and more paranoia with linear algebra checkpoints.

Happy factoring,

scalabis 2010-04-22 07:57

Thank you :smile:

jasonp 2010-07-31 19:26

Msieve v1.46
Now available on sourceforge. Major changes include support for parallel linear algebra using MPI, and a lot of improvements for NFS polynomial selection. See the changelog on sourceforge for more details.

Happy factoring,

firejuggler 2010-09-07 00:56

I am sorry to ask this, but is there a windows compiled version of Msieve 1.47?

jasonp 2010-09-07 01:00

I'll make an official release of v1.47 in the next few days. A fair number of bugfixes have accumulated since v1.46 was released, which stands to reason because the last release had a lot of new stuff.

jasonp 2010-09-19 00:41

Msieve v1.47
Now available on sourceforge. This incorporates a couple of fixes for serious bugs in the NFS linear algebra, and also includes a little tuning for the new Fermi GPU.

Happy factoring,

jasonp 2011-01-08 20:18

Msieve v1.48
Now available on sourceforge.

The major change in this release is a huge overhaul of stage 1 of NFS polynomial selection, courtesy of a great deal of work by jrk with help from me. The code is a great deal better, big CPU serches are actually feasible now, and the GPU code has received an overhaul that should enable higher throughput (no numbers here yet though). Poly selection is fast enough that degree 4 is used for all inputs < 110 digits.

If it was up to me, I'd start an overhaul of stage 2, but maybe I should start on the emergency filtering fixes now, before NFS@Home needs them :)

Happy factoring,

em99010pepe 2011-01-16 10:15


Where can we find some 64-bit Windows binaries for Msieve v1.48?

Thank you in advance,


Jeff Gilchrist 2011-01-16 12:38

Where can we find some 64-bit Windows binaries for Msieve v1.48?

You find them in the usual spot:

The 64bit package contains two binaries, the default msieve binary and also one with LARGEBLOCKS and TD=80 enabled.


JohnFullspeed 2011-06-15 06:13


I'm interrestes by the QS since many years but
I don't find your source code.
How can I get it and where


jasonp 2011-06-15 10:34

Check out the 'Links to Factoring Programs' list at the top of the Factoring subforum. The Msieve development home is [url=""]here[/url]

jasonp 2011-06-16 11:45

Msieve v1.49
Now available on sourceforge. It's really been much too long since the last release, and important bug fixes have accumulated.

I hope to be able to get one more release out before the Workshop in Amsterdam. Until then it's going to be all NFS polynomial selection, all the time.

Happy factoring,

Jeff Gilchrist 2011-06-18 01:01

Msieve v1.49 feedback
FYI, Windows 32bit and 64bit binaries are now available at the usual spot:


Jeff Gilchrist 2011-06-18 17:20

Thanks to Brian Gladman, Windows 32bit and 64bit CUDA binaries are also available on the same site.

jasonp 2012-02-03 21:43

Msieve v1.50
Things have slowed down a little so it's time for another release. The major change here is another huge overhaul of NFS polynomial selection, especially for GPUs. I now think that GPU stage 1 is uniformly faster than CPU stage 1, and the speedup increases with nicer cards. This release also incorporates all the work on degree 6 polynomial selection that folks here contributed to for RSA768 last year.

Comments and questions should go into a separate feedback thread. I don't have a specific agenda for future changes, suggestions are welcome.

Happy factoring,

Jeff Gilchrist 2012-03-30 01:37

Now that GMP 6.4.2 has been released that fixed some Visual Studio issues, I have finally updated my site with the [B]msieve 1.50[/B] binaries that use GMP 6.4.2 and MPIR 2.5.1. There are 64bit binaries for Core2, and i5/i7, and CUDA (generously supplied by Brian Gladman), and 32 bit as well.

Available from:

jasonp 2013-02-17 15:35

Msieve v1.51
Finally, after a year, the next version is out. This incorporates the massively improved GPU polynomial selection, multiple bug fixes, the more flexible input syntax and an overhaul of the NFS documentation.

There's no specific agenda for the next year; I'm open to suggestions (in a separate thread).

Happy factoring,

firejuggler 2013-02-17 16:25

any pre-compiled version availlable yet? 32 bit, 64 bit, anything is fine.

jasonp 2013-02-17 16:45

[QUOTE=firejuggler;329857]any pre-compiled version availlable yet? 32 bit, 64 bit, anything is fine.[/QUOTE]
win32 binaries are available [url=""]here[/url]. 64-bit binaries usually are contributed by Jeff Gilchrist, whenever he can get around to it.

pinhodecarlos 2013-04-26 08:23

Jeff kindly compiled official 1.51 msieve release and the latest 1.52 development pre-release version. Now the flag -nc "target_density=110" can be used.

Available from:

Thank you Jeff.

VBCurtis 2013-05-01 04:11

I see on Jeff's list of binaries, the only CUDA version is still 1.50. Is it correct that the binaries available for 1.51/1.52 are not GPU-enabled?


Ah, found the gpu binary on sourceforge- disregard.

jasonp 2014-02-05 03:52

Msieve v1.52 Available
Prepackaged source and binaries are now up on Sourceforge. This release incorporates quite a few fixes, some of them for serious bugs. It also incorporates a major speedup of the linear algebra.

I have run out of time to work on this project, for the forseeable future. Please do not expect even annual releases. I'm very sorry and wish it was otherwise.

Happy factoring,

BfoX 2015-02-12 19:34

in 'stage1_sieve_gpu.c' need make small correction:
#if 0
if (d->gpu_info->compute_version_major >= 2)
arch = "sm20";
else if (d->gpu_info->compute_version_minor >= 3)
arch = "sm13";
arch = "sm10";
if (d->gpu_info->compute_version_major >= 5)
arch = "sm50";
else if (d->gpu_info->compute_version_major >= 3)
if (d->gpu_info->compute_version_minor >= 5)
arch = "sm35";
arch = "sm30";
if (d->gpu_info->compute_version_major >= 2)
arch = "sm20";
else if (d->gpu_info->compute_version_minor >= 3)
arch = "sm13";
else if (d->gpu_info->compute_version_minor >= 2)
arch = "sm12";
arch = "sm11";

#if 0
if (d->gpu_info->compute_version_major >= 2)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm20.ptx"))
else if (d->gpu_info->compute_version_minor >= 3)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm13.ptx"))
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm11.ptx"))
if (d->gpu_info->compute_version_major >= 5)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm50.ptx"))
else if (d->gpu_info->compute_version_major >= 3)
if (d->gpu_info->compute_version_minor >= 5)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm35.ptx"))
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm30.ptx"))
else if (d->gpu_info->compute_version_major >= 2)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm20.ptx"))
else if (d->gpu_info->compute_version_minor >= 3)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm13.ptx"))
else if (d->gpu_info->compute_version_minor >= 2)
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm12.ptx"))
CUDA_TRY(cuModuleLoad(&t->gpu_module, "stage1_core_sm11.ptx"))

also add to project
'sort_engine_sm12', 'sort_engine_sm30', 'sort_engine_sm35', 'sort_engine_sm50'
'stage1_core_sm12', 'stage1_core_sm30', 'stage1_core_sm35', 'stage1_core_sm50'


ichimarux 2015-12-28 12:27

why i cant run msieve at my laptop. its show error missing pthread32GC.dll. and i download it then its still error its doenst work at all ._.

jasonp 2016-11-11 17:30

Msieve v1.53 available
Now up on sourceforge. I have switched to providing win64 binaries, built with Msys2 for Sandy Bridge and CUDA 6.5; if these are insufficiently optimized then Jeff Gilchrist's page contains win64 binaries built from the Visual Studio projects and using the latest CUDA.

This release folds in two years of bug fixes and improvements.

Happy factoring,

Jeff Gilchrist 2016-11-11 18:39

I just updated the page with fresh builds of most/all of the factoring binaries thanks to Brian Gladman. You can find those msieve builds and others here:

BfoX 2017-04-18 17:45

hi, any1 can explain to me why in the 'msieve153dev_svn1002_win64_cuda' all ptx-file is same - for sm_20 only?

ixfd64 2018-01-11 06:31

Msieve website down
Jason, the Msieve website at [url][/url] is returning a 404 error. Just a heads-up!

All times are UTC. The time now is 09:14.

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