A high-performance degree-6 root sieve

jasonp · 2010-04-18, 05:00

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

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.

jrk · 2010-04-18, 05:05

Great job! Many have been looking forward to this.

fivemack · 2010-04-18, 09:49

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 http://www.loria.fr/~zimmerma/records/rsa200:
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)

Batalov · 2010-04-18, 10:04

...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):

poly5 skew 2766778.76, size 9.377070e-20, alpha -6.759447, combined = 3.869132e-15
poly6 skew 1599533700.93, size 3.654470e-15, alpha -11.690009, combined = 1.019247e-15

Is it possible that Kleinjung et al. chose degree 5 because it was faster than their best degree 6 (if they had one)?

Are the new changes make your degree 5 code fly, too?

It is a good start though.

jasonp · 2010-04-18, 12:34

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).

henryzz · 2010-04-18, 12:37

Quote:

Originally Posted by jasonp

or we have to such for much longer than I did (the current one took only 45 minutes to find).

I would guess this would help. They will have spent many times longer on polynomial selection. Did you use a GPU or a CPU?

jasonp · 2010-04-18, 12:43

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

jasonp · 2010-04-20, 13:01

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

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

I'll try to get the search time down, seven hours is much too long.

Batalov · 2010-04-20, 23:58

Quote:

Originally Posted by jasonp

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.

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
t5 Mon Apr 19 00:19:37 2010 skew 1.00, size 1.427820e-17, alpha 2.379130, combined = 5.388172e-14
t6 Mon Apr 19 00:20:35 2010 skew 1.00, size 7.112909e-13, alpha 3.125762, combined = 8.705755e-14
but the sieving speeds are not differing by that much (same limits, 30-bit, 134M, 15e):
-r t5 total yield: 604, q=134001001 (1.29765 sec/rel)
-a t5 total yield: 267, q=134001001 (2.51970 sec/rel)
-r t6 total yield: 596 , q=134001001 (1.32622 sec/rel) \__ but both sides are OK-ish
-a t6 total yield: 581, q=134001001 (1.56935 sec/rel) /
(need to sieve more, much more before making far-fetching propositions; but I didn't have time)

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 gnfs 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.

jasonp · 2010-04-21, 01:56

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.

jasonp · 2010-04-24, 01:57

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

2010-04-18, 05:00	#1
jasonp Tribal Bullet Oct 2004 110111010101₂ Posts	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 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.

2010-04-18, 09:49	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	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 http://www.loria.fr/~zimmerma/records/rsa200: 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) Last fiddled with by fivemack on 2010-04-18 at 10:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Choice of SNFS polynomial degree	lavalamp	Factoring	15	2018-02-11 14:46
Cyclotomic primes (degree>=5)	Batalov	And now for something completely different	0	2016-06-21 21:02
GNFS polynomial degree	joral	Factoring	6	2008-09-26 22:15
High first prime mod-root Quadratics	grandpascorpion	Puzzles	9	2005-09-25 13:45
Running Prime on High Performance Computer Clustering	fxmulder	Software	5	2003-11-20 22:42

2010-04-18, 05:05	#2
jrk May 2008 3×5×73 Posts	Great job! Many have been looking forward to this.

2010-04-18, 10:04	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	...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): poly5 skew 2766778.76, size 9.377070e-20, alpha -6.759447, combined = 3.869132e-15 poly6 skew 1599533700.93, size 3.654470e-15, alpha -11.690009, combined = 1.019247e-15 Is it possible that Kleinjung et al. chose degree 5 because it was faster than their best degree 6 (if they had one)? Are the new changes make your degree 5 code fly, too? It is a good start though.

2010-04-18, 12:34	#5
jasonp Tribal Bullet Oct 2004 3,541 Posts	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).

2010-04-18, 12:43	#7
jasonp Tribal Bullet Oct 2004 6725₈ Posts	I suspect the CPU code would never find hits for an input this big; GPU all the way.

2010-04-21, 01:56	#10
jasonp Tribal Bullet Oct 2004 3,541 Posts	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.