A high-performance degree-6 root sieve

[Batalov]

We have (courtesy of Kleinjung, Franke, via Greg's request) the 33-bit-and-above sievers somewhere on the forum... (AFAIR, called 15f, 15g.) These polyns deserves to be tried with at least 34-bit LPBs; we might get a more realistic picture. I'll take a crack at building and trying them out, better late than never. Curios to see the memory footprints, too.

[jasonp]

Unfortunately the only 'good' degree 6 polynomial I have to compare against is the one used for RSA768:

R0: -1291187456580021223163547791574810881
R1:  34661003550492501851445829
A0: -277565266791543881995216199713801103343120
A1: -18185779352088594356726018862434803054
A2:  6525437261935989397109667371894785
A3: -46477854471727854271772677450
A4: -5006815697800138351796828
A5:  1276509360768321888
A6:  265482057982680
skew 44000.00, size 8.323025e-017, alpha -7.298406, combined = 7.862398e-017

So I've made the changes to do a limited run using the new code. The following is the best it could do after a few minutes:

# norm 7.182579e-018 alpha -13.429458 e 9.551e-018
skew: 16127312406.28
c0: -165540526874822217059371542029722010096953602923027545137571668672
c1:  169050043970374034075850263208826303592255461385546540424
c2: -25086123568192950933274652248848475570220413358
c3: -4638773966041746208606311758584410209
c4:  491021760069332352492784585
c5:  37000920436336995
c6:  1000020
Y0: -32730189031367594561333737133996204135
Y1:  552555777561006102623641

That is some major-league skew. Unfortunately the E-value is less than 1/8 that of the reference polynomial, so about 8.2x slower sieving. I also have no clue what good bounds on the norm should be, so it's no surprise that the first stage 1 hit isn't that great. The very nice alpha in the second case removes about 25% of the difference in sieving speed between the two polynomials.

[jasonp]

Last night I merged the degree 6 poly selection code into the trunk. There are a bunch of changes now if you are interested:

- the default is still to do stage 1 and move to stage 2 whenever a hit is found, but now it's also possible to batch stage 1 hits and then run stage 2 on them all at once (i.e. there are now -np1 and -np2 options alongside -np). This means that stage 1 hits from pol51m0b can be passed to the much more powerful stage 2 code in msieve

- the size optimization in stage 2 should work a lot better even for degree 5 problems; the root sieve is unchanged, but I'm planning to merge the old root sieve with the new more powerful degree 6 code

- stage 2 works a lot better for degree 6 now; for RSA768:

# norm 4.241918e-17 alpha -10.618674 e 4.326e-17 rroots 6
skew: 43219804.59
c0: -95387103515342977859292252739460922728632069702631375
c1: -5782463767837904488920471697926898364680104420
c2:  3297025950763661888403201600602513605609
c3: -37344650766830623857836813239461
c4: -6472695062730863604842570
c5: -176619307146183
c6:  21420000
Y0: -19642281280107733030683475320145535994
Y1:  26077104631367

It turns out the difference in sieving speed between polynomials for RSA768 is much smaller than the ratio of their E-values; the above polynomial sieves only about 20% slower than one actually used for RSA768, even though its E-value is a bit more than half as large. That's not bad considering the reference poly needed dozens of CPU-years to find but it only took a few machine-days to find the stage 1 hit that led to this polynomial and about a minute to run stage 2.

Right now there's no way that msieve will be able to find the stage 1 hit that led to the above; it was actually found by the polyselect2 utility in the CADO NFS suite (which is why the leading rational coefficient is so tiny). Paul Zimmermann tells me that polyselect2 can also be used for degree-5 problems, although it hasn't had a great deal of testing at smaller sizes. Maybe somebody would like to try running a big degree-5 job through polyselect2 for stage 1 and msieve for stage 2...

Finally, I owe a big thank-you to Paul and his group in Nancy for a great deal of help with all of this over the last month.

[Phil MjX]

Originally Posted by jasonp

- the default is still to do stage 1 and move to stage 2 whenever a hit is found, but now it's also possible to batch stage 1 hits and then run stage 2 on them all at once (i.e. there are now -np1 and -np2 options alongside -np). This means that stage 1 hits from pol51m0b can be passed to the much more powerful stage 2 code in msieve

Thanks a lot Jason : I have to polynomials for an aliquot sequence c161 : one found with msieve and a gpu and one found with ggnfs.
I'll try to optimize the latter with msieve now !

Does msieve still be less efficient with larger a5 coefficient, let's say around 1e6 or will the try be worth the pain ?

Kind regards.
Philippe

[jasonp]

The larger a5 shouldn't make a difference.

[Phil MjX]

Hi Jason,

I've found an oddity with the sage 2 of msieve poly optimization.

I have a "second best" poly found by ggnfs with a score of 1.09e-12. Msieve gives it a E score of 1.08e-12

Msieve v. 1.46
random seeds: ecf038b3 d3df6e76
factoring 763153429803080858903089323875507998154917858395651187867985057376493455206857265546827483207908/
58695747320013201478131381582408092466490020127136265836553549173 (161 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (161-digit input)
R0: -8345049961259460996632721855701
R1: 1053074082857139527
A0: 47791955288286001514713420750526784
A1: 9510186942530348961905166931326
A2: 33183394412637773340819383
A3: -8195374691518584298
A4: -28903774016904
A5: 1885680
skew 1091705.68, size 9.629e-16, alpha -5.099, combined = 1.084e-12 rroots = 5

I'd have liked to have this poly optimized by msieve so I have reloaded msieve with the ggnfs .dat.m file dealing with the a5 exponent.

The best poly found had a E score of 1.04e-12 so I have thought that "different algorithm = different poly" from rough data...

Msieve v. 1.46
random seeds: 0e7ad713 52a2db7b
factoring 763153429803080858903089323875507998154917858395651187867985057376493455206857265546827483207908/
58695747320013201478131381582408092466490020127136265836553549173 (161 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (161-digit input)
R0: -8345050075760206025689502626411
R1: 1053074082857139527
A0: -4423268904479711207399026243007245824
A1: 2153396863514499819662285150042
A2: 33782165181515207586214403
A3: 4598383808126023382
A4: -29928923948904
A5: 1885680
skew 1172789.00, size 9.095e-16, alpha -4.976, combined = 1.046e-12 rroots = 5

What really confuses me is that, if you start with a msieve.dat.m containing the ggnfs E=1.08e-12 poly :

1885680 1053074082857139527 8345049961259460996632721855701

msieve does the optimization and prints back the E=1.04e-12 poly...
I think there is no check in msieve to see if the step 2 input is "better" than the output (this should never happen
in the real life but some people may also want to optimize their ggnfs champions as I did)

To be certain that the E=1.04e-12 poly was worse than the E=1.08e-12, I have done litthe sieving with both.

E=1.08e-12
total yield: 984, q=70001083 (0.91694 sec/rel)
total yield: 2194, q=70002013 (0.88283 sec/rel)
total yield: 3427, q=70003081 (0.86553 sec/rel)

E=1.04e-12
total yield: 944, q=70001083 (0.85747 sec/rel)
total yield: 2330, q=70002013 (0.87610 sec/rel)
total yield: 3602, q=70003081 (0.89227 sec/rel)

Nothing clear by sieving but the choice of the better poly for the sieve is done on the E value both by ggnfs and msieve.

I have a better poly currently running, and this was just experiment, but I hope this helps.

Kind regards and thanks for the BIG job !

Philippe

[henryzz]

Phil, you just gave msieve the rational poly for stage 2 optimization so you would expect the result to be different.

[Phil MjX]

Indeed but I did expect one with a better or equal overall score than the input...

I also give it the output of ggnfs stage 1 file with the same result. In that particular case, ggnfs stage2 gives me an apparent better poly, at least one with a higher E score.

Regards.
Philippe

[jasonp]

If you ask for polynomial selection, the code will not run if there already is a .fb file with a polynomial in it.

You actually are only giving msieve's stage 2 three numbers out of the 8 that fully specify a polynomial; the stage 2 code has no idea that a complete polynomial has already been found elsewhere, it runs stage 2 from scratch. I agree that it would be nice to take a complete polynomial as input, maybe tweak it a little, and print out anything that turns out better, but the code doesn't presently do that.

We're in the very beginning stages of being able to compare the two stage 2 codes; my feeling has always been that msieve would do better but that may not be true, or may only be true occasionally (like when the search space for the root sieve is very large)

Also, the computation of E-value is very different between GGNFS and msieve; I'm reasonably sure the msieve version is more accurate but the two results are hopefully always very close.

[Phil MjX]

Thanks Jason,
I am ashamed I missed the point that the poly was not completely defined with A5, Y0 and Y1...

The good news is that, with gpu-msieve for lower leading coefficient and ggnfs for larger one, the search space can be greatly expanded for the first stage of the polynomial selection.

I often use greater multipliers with ggnfs (144 or 720) for large a5 coefficients and it gives good results imho.
With a quad core, I'll try to make the two programs run in parallel for stage 1 (but after the current composite, in two months and a half ).
Then, optimizing all the data with either msieve or ggnfs will be just nice, and a matter of taste !

Thank you again for the improvements in this part of the code : I think that the synergy between msieve and ggnfs can be of great interest here.

Regards.
Philippe