Msieve with GNFS support

[jasonp]

Originally Posted by BWetter246

I was wondering if the next version will be GSL free?

That isn't a priority for me right now; GSL builds without trouble on all the platforms msieve runs on, and Brian Gladman has precompiled binaries if you use Visual Studio. I haven't forgotten about it, but there's neater stuff that needs doing first. If infection with the 'GPL virus' is what's concerning you, I understand but development time is somewhat limited for me.

[Andi47]

Originally Posted by jasonp

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

I hope NFS gets MUCH faster with the new poly selection. I have now stopped the NFS run on the c120 after running (almost) continuously for 30 days on a Core 2 Duo @ 2.0 GHz, found 2.1M relations (need ~7M relations).

SIQS on the c121 is still running (and it seems to be faster then NFS on a number with almost the same size - found 338k relations (need 435k)). I have moved this number to my P4 @ 3.4 GHz yesterday, because my brother needs my laptop over the weekend, so I will not get an accurate benchmark for how long does this number take on a Core 2 Duo.

Can you give an estimate when the new polynomial selection will get ready? On this I will consider if I unreserve the c120 or give it a retry with a new polynomial - I won't run it on GGNFS because my rudimentary linux skills are not sufficient to even get GGNFS installed properly under MinGW.

[jasonp]

Originally Posted by Andi47

Can you give an estimate when the new polynomial selection will get ready? On this I will consider if I unreserve the c120 or give it a retry with a new polynomial - I won't run it on GGNFS because my rudimentary linux skills are not sufficient to even get GGNFS installed properly under MinGW.

The speedup to expect from a good polynomial is a factor of about 2x; the siever will also need modifying to take full advantage of the better polynomials.

Right now I'm estimating 1-2 months until the next version, but it will depend on the amount of spare time I have. If GGNFS isn't an option for your C120 then I'd suggest unreserving it; someone else will be able to finish it off in about a week on a single fast CPU.

jasonp

[Andi47]

Originally Posted by Andi47

SIQS on the c121 is still running (and it seems to be faster then NFS on a number with almost the same size - found 338k relations (need 435k)). I have moved this number to my P4 @ 3.4 GHz yesterday, because my brother needs my laptop over the weekend, so I will not get an accurate benchmark for how long does this number take on a Core 2 Duo.

finished SIQS on 5,4,274+ c121

5,4,274+ = p48 * p74

p48 = 702271395614386104077802804002176154872880097089
p74 = 13364867381280992718284619825485030108685243732130847433376959070734213877

(both certified prime with primo)

[jasonp]

Originally Posted by Andi47

finished SIQS on 5,4,274+ c121

5,4,274+ = p48 * p74

Congratulations! This is one of the larger msieve QS factorizations that I know about (the absolute largest is 126 digits, but of course people don't have to tell me when they finish big jobs :) . Be sure to mail xilman so you get credit.

jasonp

[Andi47]

Originally Posted by jasonp

Congratulations! This is one of the larger msieve QS factorizations that I know about (the absolute largest is 126 digits, but of course people don't have to tell me when they finish big jobs :) . Be sure to mail xilman so you get credit.

jasonp

Thanks. I have sent the email to xilman immediately after I have posted here.

[Andi47]

Originally Posted by jasonp

The speedup to expect from a good polynomial is a factor of about 2x; the siever will also need modifying to take full advantage of the better polynomials.

Do you meen two times faster or twenty'ish times faster?

If it is two times faster, then it would be approx. 2 months instead of 4 months for a c120 (I stopped my factorisation after just over one month on a 2 GHz Core 2 Duo havng 2M of 7.1M relations), which still seems to be quite loooong - compared to the one-week-run with GGNFS you mentioned. So maybe a lattice siever would be better anyway?

[jasonp]

Originally Posted by Andi47

Do you meen two times faster or twenty'ish times faster?

If it is two times faster, then it would be approx. 2 months instead of 4 months for a c120 (I stopped my factorisation after just over one month on a 2 GHz Core 2 Duo havng 2M of 7.1M relations), which still seems to be quite loooong - compared to the one-week-run with GGNFS you mentioned. So maybe a lattice siever would be better anyway?

If I knew how to make the sieving twenty times faster by choosing a better polynomial, I'd be publishing papers and not code :) I did mean two times faster, this is typical of the difference between excellent and merely decent polynomials.

I should also stress that the goal of all this code is not to beat GGNFS but to make the best NFS code I possibly can. Since the last few weeks haven't seen any work on either poly selection or building a lattice siever, maybe I should put it to a vote: who wants the next big release to have improved polynomial selection, and who wants the next big release to have a lattice siever? Both of these are extremely complicated, both are needed badly, both are interchangeable with the code already in GGNFS, and neither will be as good as the code in GGNFS for a while. My preference is for better polynomial selection, because there are tricks published in several papers that have not appeared in code, and those could possibly be leveraged to make better polynomials than anybody else. But I can be convinced otherwise.

(Note that I'll be making a release in the next few days that will just include bug fixes and a few tweaks, just to get that out of the way)

Sander, I don't know what could be going on; if you can get me the relations I'll get to the bottom of it, otherwise I'd suggest waiting for 1.20 and then taking this to email.

[Andi47]

Originally Posted by jasonp

I should also stress that the goal of all this code is not to beat GGNFS but to make the best NFS code I possibly can. Since the last few weeks haven't seen any work on either poly selection or building a lattice siever, maybe I should put it to a vote: who wants the next big release to have improved polynomial selection, and who wants the next big release to have a lattice siever? Both of these are extremely complicated, both are needed badly, both are interchangeable with the code already in GGNFS, and neither will be as good as the code in GGNFS for a while. My preference is for better polynomial selection, because there are tricks published in several papers that have not appeared in code, and those could possibly be leveraged to make better polynomials than anybody else. But I can be convinced otherwise.

If the goal is to find better polynomials first - which can also be used for a later implemented lattice siever, then I will not poke you for makting a lattice siever quickly any more.

But - I will wait until the poly selection and the lattice siever is ready before I will do more c120+ factorizations.

[fivemack]

Many thanks.

Is there any way, perhaps for 1.21, that you could get the Makefile to set -arch=athlon or -arch=k8 depending on whether you asked 'make x86' or 'make x86_64' ? At the moment downloading and saying 'make x86_64' gives an error 'CPU you selected does not support x86-64 instruction set', and now that you don't have to edit the makefile to select the CPU it seems a pity to have to edit it otherwise.

[fivemack]

This is a C136, ~28 million input relations sieved with fb=9000000 lp=2^29

Sun May 13 19:01:59 2007  commencing linear algebra
Sun May 13 19:01:59 2007  factor base loaded:
Sun May 13 19:01:59 2007  432073 rational ideals (max prime = 6299987)
Sun May 13 19:01:59 2007  431981 algebraic ideals (max prime = 6299977)
Sun May 13 19:02:08 2007  read 1974179 cycles
Sun May 13 19:02:17 2007  cycles contain 5415935 unique relations
Sun May 13 19:03:26 2007  read 5415935 relations
Sun May 13 19:03:35 2007  using 32 quadratic characters above 536870600
Segmentation fault

When I rerun with gdb, it seems that the problem is at line 431 of gnfs/gf2.c

dense_rows[idx/32] |= 1<<(idx%32)

in nfs_solve_linear_system; debugging optimised code is always a bit painful, but looking at the registers is telling me that idx=0xFE56E115 at this line, which doesn't look good. I suspect that the bsearch at line 424 returned NULL, at which point QCB_SIZE+1+(loc-small_ideals) is very negative and we get the failure.

So it's trying to handle a dense ideal which isn't in the table of small ideals. I'm happy to run more tests if you suggest what to run ...