A high-performance degree-6 root sieve
 

It's not done yet, but the initial results are promising.

Can someone compare the yield for RSA200 between the polynomial that was actually used, and this one?
[code]
# norm 3.654470e-15 alpha -11.690009 e 1.019e-15
skew: 1599533700.93
c0: 59779951656974443324757595299721437773698423484835904387
c1: -3650734124438501657842746115963920884981782086493
c2: -8432730247914056321080131487192727012508
c3: 1987529475731346394981376992164
c4: 2246526410779665676181
c5: -828739829271
c6: 180
Y0: -733353324813424457468143920275996
Y1: 10146121641768070157[/code]
That alpha value is not a mistake, and is entirely typical with the current code. I'm in the middle of changes that will probably improve alpha but also worsen the polynomial size, so that the final E value may not wind up any better.

Will post better polynomials if I find any.

Great job! Many have been looking forward to this. :smile:

I don't at present have a siever binary which can use the 35-bit large primes which were used in the real RSA200 project, but (comparing at Q=3e8 with 33-bit large primes, gnfs-lasieve4I16e) my very-initial results are unpromising to the point that I assume I've made an error. Timings on K8/2500:

polynomial from [url]http://www.loria.fr/~zimmerma/records/rsa200:[/url]
total yield: 316, q=300000167 (1.52370 sec/rel)

polynomial from this work:
total yield: 55, q=300000167 (6.44636 sec/rel)

(those were algebraic-side results; rational-side lattice sieving is even worse)

...I also was just now typing something to the same tune. My limits (32-bit, 16e siever, 134M to have fast output) were lower still, so they were even more prone to be misleading, but anyway: they suggested a 3x yield lead by the RSA200-team poly (poly5). This is consistent with the 3x difference in E values, though (both gauged by msieve):

[FONT=Arial Narrow]poly5 skew 2766778.76, size 9.377070e-20, alpha -6.759447, combined = [U]3.869132e-15[/U]
poly6 skew 1599533700.93, size 3.654470e-15, alpha -11.690009, combined = [U]1.019247e-15[/U]
[/FONT]
[FONT=Arial Narrow][FONT=Verdana]Is it possible that Kleinjung et al. chose degree 5 because it was faster than their best degree 6 (if they had one)?[/FONT]
[FONT=Verdana][/FONT]
[FONT=Verdana]Are the new changes make your degree 5 code fly, too?[/FONT]
[FONT=Verdana][/FONT]
[FONT=Verdana]It is a good start though.[/FONT]
[/FONT]

The difference in E values between different degrees are not directly comparable from what I understand; for inputs above 100 digits a degree 4 polynomial has 5x the E-value of a corresponding degree 5, but only sieves about 25-50% faster.

I also don't know how much this can help degree 5; certainly for really big inputs the search space is large enough to get a boost from the techniques used here, and I definitely want to merge degree-5 and degree-6 to share as much common code as possible. But for skew S the total number of combinations to try is S^2 for degree 5 but over S^4.5 for degree 6, and the latter leaves a great deal more room to search for ever-more-perfect rotations.

I suppose this means 200 digits is too small to benefit from a degree-6 polynomial; either that or we have to such for much longer than I did (the current one took only 45 minutes to find).

[quote=jasonp;212288]or we have to such for much longer than I did (the current one took only 45 minutes to find).[/quote]
I would guess this would help. They will have spent many times longer on polynomial selection. Did you use a GPU or a CPU?

I suspect the CPU code would never find hits for an input this big; GPU all the way.

So after a 7-hour run the best polynomials are as follows:

[code]
# norm 4.650795e-15 alpha -14.023266 e 1.224e-15
skew: 3669074663.12
c0: 71046780755294559737849089471137694853806696221785232489025
c1: -85214938924956262093456046622348403904354239838405
c2: -5822653549360934072796526107550420353660
c3: 8407127296553013512504826292892
c4: 1836893694929492612471
c5: 714036673689
c6: 180
Y0: -733338831111512333655969656944362
Y1: 10146121641768070157
# norm 4.767060e-15 alpha -12.910176 e 1.239e-15
skew: 3669074663.12
c0: -2239961586260210913041204919626077178529850564511144597025
c1: -7369682704936333281374337760357276896988988622685
c2: -6218093582390488942462501931002451074380
c3: 3772580356214190824035542436692
c4: 1379231690075687248121
c5: -558693462711
c6: 180
Y0: -733350787847420721126217882295672
Y1: 10146121641768070157
# norm 4.885479e-15 alpha -13.753917 e 1.271e-15
skew: 3669074657.27
c0: -9317576448889630578971266941385045303719860825538059591040
c1: 9973903552116075866600736608173958993124597787056
c2: 9123884421936144923942197855539961831836
c3: 3223050969911337473333191418890
c4: 1654945457282841178286
c5: -656693789151
c6: 180
Y0: -733351708517080900033268025649423
Y1: 10146121641768070157
[/code]
with the last one above being the best overall. The best alpha values are:
[code]
# norm 3.767941e-15 alpha -13.843902 e 1.032e-15
# norm 3.963610e-15 alpha -13.872815 e 1.073e-15
# norm 3.692745e-15 alpha -13.874815 e 1.014e-15
# norm 3.971716e-15 alpha -13.893700 e 1.077e-15
# norm 4.650795e-15 alpha -14.023266 e 1.224e-15
[/code]
I'll try to get the search time down, seven hours is much too long.

We are maximizing E, but can we trust E?
 

[quote=jasonp;212288]The difference in E values between different degrees are not directly comparable from what I understand; for inputs above 100 digits a degree 4 polynomial has 5x the E-value of a corresponding degree 5, but only sieves about 25-50% faster.[/quote]
True. Definitely not directly.
This seems to be less pronounced for comparing degrees-5 vs. 6. Forgive me a small tangent - maybe you will find it useful, if not relevant? Here goes nothing:

I ran some tests for two (equally useless*) polynomials for 10,286+:
- t5, a quintic diff.260 from /11 reduction and
- t6, a sextic diff.264 from /13 reduction.
The E values are
[FONT=Arial Narrow]t5 Mon Apr 19 00:19:37 2010 skew 1.00, size 1.427820e-17, alpha 2.379130, combined = 5.388172e-14[/FONT]
[FONT=Arial Narrow]t6 Mon Apr 19 00:20:35 2010 skew 1.00, size 7.112909e-13, alpha 3.125762, combined = 8.705755e-14[/FONT]
but the sieving speeds are not differing by that much (same limits, 30-bit, 134M, 15e):
[FONT=Arial Narrow]-r t5 total yield: 604, q=134001001 ([B]1.29765[/B] sec/rel)[/FONT]
[FONT=Arial Narrow]-a t5 total yield: [COLOR=darkred]267[/COLOR], q=134001001 ([COLOR=darkred]2.51970[/COLOR] sec/rel)[/FONT]
[FONT=Arial Narrow]-r t6 total yield: 596 , q=134001001 ([B]1.32622[/B] sec/rel) \__ but both sides are OK-ish[/FONT]
[FONT=Arial Narrow]-a t6 total yield: 581, q=134001001 (1.56935 sec/rel) /[/FONT]
[FONT=Arial Narrow](need to sieve more, much more before making far-fetching propositions; but I didn't have time)[/FONT]

If we were planning to sieve on both sides, t6 here is better; if one side, then need to sim more before deciding*...

Is it possible that E score is rather correlated to predicting "a blend" of sieving on both sides (which in real life a user doesn't have to do, instead wisely chosing the better side; hence the difference)? This could explain the quartic/quintic comparisons around the division line (there, quartic has a horrible one side and a better other side, quintic is OK-ish for both).

I meant this tangent to lead to a possibly better understanding if E is still a useful indicator (even if between degrees), or if only sims could be trusted.

I don't understand the E score enough to suppose it can be modified to predict the yield from a certain side of sieving, ...can it?

_____
*useless because the true winner for this number is the [I]gnfs[/I] polynomial. There are very few other Cunnigham table examples left with simultaneous reduction by 11 and 13 (or 11 and 7, where 7 will win, so that's not too interesting) so I went with this one.

The E-value computation looks at the probability that both the rational and algebraic polynomials are smooth, then multiplies those together and integrates over a sample sieving region. To account for large primes (including special-q) you'd have to modify the probability function in very complex ways. Murphy's dissertation goes into the gory details.

If you want a somewhat unrealistic idea of how the two sides of the polynomial pair behave individually, you could always go to gnfs/poly/size_score.c:520 and comment out one call to dickman() or the other.

More changes in the pipeline, but in the meantime a nice improvement:
[code]
R0: -733353401621513341007654478236140
R1: 10146121641768070157
A0: 1477396862285918910964124660292692112463593156295871422227
A1: 7059861951105466533887079259576011943187171578707
A2: 930817317592755233385078920781705632292
A3: 1918896273539831751475486102804
A4: 2278049739986484659141
A5: -836915636631
A6: 180
skew 3669074663.12, size 5.677371e-15, alpha -13.871297, combined = 1.424316e-15
[/code]