Call for volunteers: RSA896 - Page 10

jasonp · 2013-02-06, 12:26

Their best is 3.51e-19; the full 5000 will probably take 5 days on one core

debrouxl · 2013-02-06, 18:55

Size optimization finished on batch 1 (nearly 48h wall-clock time for 4 processes on Xeon E3-1230, 2 processes finished ~30' earlier) and batch 8 (~44h30 wall clock time for 8 processes on FX-8150; 6 processes finished 2h earlier).
FWIW, both runs used MPI-patched msieve with a single .dat.m input file, so poily's latest patch works for me

MPI root optimization has started.

EDIT: BTW, poily, it would be great to make the same kind of change for root optimization as you did for size optimization: the ability to trigger multi-process root optimization from a single input file, if no .dat.ms.mpi* files are found

Dubslow · 2013-02-07, 05:41

I suddenly have two more cores that are free, so I'm taking batch 6. (I suppose it will take 4 days to do, using half the cores.)

PS If we do the root sieve, do you want the sizeopt hits as well as the final polys?

Edit: When using `split -n`, be sure to right `split -n l/2` as opposed to `split -n 2`. That doesn't split lines

firejuggler · 2013-02-07, 18:22

i'm far from being done, but so far best poly give 2.837e-019

Code:

# norm 5.520074e-020 alpha -12.511594 e 2.837e-019 rroots 4
skew: 81766141.19
c0: 3607869805213281554823252296618828604677914930359987025344
c1: 23220164568489045138114308221677930169305838193010240
c2: 9203124297129543437723323024998562111194036
c3: 9334995343944464727631510927880010416
c4: -324816754181582556026397511033
c5: -2223278394876459083044
c6: 7232286821760
Y0: -6203084729795742043403960083120441126010795
Y1: 42260925725431380236248723

debrouxl · 2013-02-08, 07:55

The three best polys, in batch 1 (processed by the Xeon E3-1230 with 8 processes in ~29h wall clock time, 7 of the 8 processes finished at 16-17h) are

Code:

# norm 6.453437e-20 alpha -12.047099 e 3.248e-19 rroots 6
skew: 84355332.37
c0: -40946290090445266551161549499305741933274180644750016085425
c1: -10467357875909381144128954908126047238982795499683785
c2: 575409405642562087310720821835776371535397053
c3: 9572582929973485805475819618000250061
c4: -148894749080944910994034682372
c5: -724347752270183267004
c6: 1859803545600
Y0: -7778737956208683626717082871144859356558432
Y1: 10686505327134712299646993

Code:

# norm 6.056026e-20 alpha -11.631907 e 3.052e-19 rroots 4
skew: 48793635.82
c0: 9335896655809604327925621788999250854933506382363022965344
c1: 1925306846817736254699271114907020489847742878092288
c2: -169310545848405710260883307959917839585756986
c3: -3496004302313744686041859045254926483
c4: 275085812586209584750675391032
c5: 1408333791906605513980
c6: 478010332800
Y0: -9755452962557811620933593496014011645343335
Y1: 4282423141698728009631007

Code:

# norm 5.969626e-20 alpha -11.556799 e 3.019e-19 rroots 6
skew: 47942131.68
c0: 18012875627631792901670781168326202449068477209742252483200
c1: 1457681444502169713650799905383394058738666204734748
c2: -139260042798502345861170120050843951277513880
c3: -5797429652761017495601014198560882931
c4: 259974699150207277836260389632
c5: 1402165548484195645180
c6: 478010332800
Y0: -9755452962567021682782058132587572724643997
Y1: 4282423141698728009631007

The best poly produced from batch 8 (FX-8150, ~25h wall clock time, 7 of the 8 processes finished around 15h) has larger norm but worse e:

Code:

# norm 6.632671e-20 alpha -11.607950 e 2.967e-19 rroots 4
skew: 49069361.13
c0: 28745311041103203356576951005989940082831495232341768515776
c1: -205998030496036644387588200533512340837882272321360
c2: -132018394189437555571701225591789662744633256
c3: 1365610013934000246262086253251260366
c4: 19443724695135903573441283643
c5: 392511937028479386086
c6: 5858173601280
Y0: -6424804940317563889082609710168513250186575
Y1: 451681905409118609701262291

akruppa · 2013-02-08, 09:42

Quote:

Originally Posted by firejuggler

i'm far from being done, but so far best poly give 2.837e-019

Code:

# norm 5.520074e-020 alpha -12.511594 e 2.837e-019 rroots 4

This is crazy.

The young 'uns may not know it but there was a time when alpha < -5 was considered really lucky.

firejuggler · 2013-02-08, 10:01

and what does it say about my personality? (no seriously... what does the low alpha mean? I won't ask about double rainbow, don't worry)
and for the sake of it my lowest alpha value

Code:

# norm 4.628932e-020 alpha -12.956412 e 2.448e-019 rroots 4
skew: 111461741.54
c0: 4596185303540975912941768799404404251911067990661592486450560
c1: -280987050579580684349518348073004894589766436497544888
c2: -5453326966044145207308567141134658983582007302
c3: 92528123968159463596593396717045851089
c4: 560963993141923165266152827450
c5: -2978793911777564174904
c6: 6711846261120
Y0: -6280776226247745384246196650168744854827871
Y1: 80764498754829792133232269

new record holder for my batch

Code:

# norm 5.554255e-020 alpha -12.726487 e 2.853e-019 rroots 4
skew: 88161163.72
c0: 592294109350104075885455758432520983785765035911272504595840
c1: -44228198432626906079450591344684081042731028765034896
c2: -1266780839981054007483109448136912523638841412
c3: 25584881562241130646568639974012624680
c4: -32136804857417066806626443393
c5: -3165936771052409436964
c6: 7232286821760
Y0: -6203084730713792276611133070779722382751981
Y1: 42260925725431380236248723

not terribly better, I know

akruppa · 2013-02-08, 11:49

The alpha value is a measure for how many very small prime factors the polynomial values contain on average. We are looking for smooth polynomial values (= no large prime factors), and there will be more of those in the search region if the polynomial values tend to contain a lot of very small primes. The alpha value tells that, thanks to having many small primes, polynomial values F(a,b) are about as likely smooth as as an integer around F(a,b)*exp(alpha), so with alpha=-12, the polynomial values are about as likely to be smooth as if they were smaller by a factor of ~16000.

poily · 2013-02-08, 12:31

Hm, I was under impression the patch should also work for poly root optimization... But it didn't due to copy-paste mistype, here's fixed version of the patch.

I finished the batch 7, started poly root optimization of best 5000.

jasonp · 2013-02-08, 13:07

The other thing that really jumps out at me from the list of best polynomials is that all of them are coming from stage 1 hits found by the CADO tools. I think the Msieve hits are the ones with lots of high-order zeroes in the leading algebraic coefficient, and in all the stage 2 that I've run locally the best E value I've been able to find from an Msieve stage 1 hit is around 3e-19.

Paul has been suggesting that targeting a leading rational coefficient size that is somewhat smaller than the maximum possible, for a given choice of stage 1 size bound, gives a better chance of a good polynomial after size optimization. Looks like I should try a few experiments.

I think all of modern GNFS polynomial selection is basically a struggle to increase the amount of skew without making stage 1 stop working; the end result is a playground of absurd alpha values. It doesn't hurt that the playground is enormously larger now that we're in degree-6 territory (an alpha value < -5 is still pretty unusual for degree-5 polynomials). Shi Bai's dissertation found that for RSA768 a large sampling of size-optimized polynomials had a mean alpha value of -0.2 and standard deviation of about 0.8; so finding an alpha value of say -10.0 is a 12-sigma event.

frmky · 2013-02-09, 06:53

Here's another 9.5 million. I've stopped it for now.
https://www.dropbox.com/s/meef9g9dkq...896_4.dat.m.gz

2013-02-06, 18:55	#101
debrouxl Sep 2009 3D1₁₆ Posts	Size optimization finished on batch 1 (nearly 48h wall-clock time for 4 processes on Xeon E3-1230, 2 processes finished ~30' earlier) and batch 8 (~44h30 wall clock time for 8 processes on FX-8150; 6 processes finished 2h earlier). FWIW, both runs used MPI-patched msieve with a single .dat.m input file, so poily's latest patch works for me MPI root optimization has started. EDIT: BTW, poily, it would be great to make the same kind of change for root optimization as you did for size optimization: the ability to trigger multi-process root optimization from a single input file, if no .dat.ms.mpi* files are found Last fiddled with by debrouxl on 2013-02-06 at 19:29

2013-02-07, 05:41	#102
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1110000110101₂ Posts	I suddenly have two more cores that are free, so I'm taking batch 6. (I suppose it will take 4 days to do, using half the cores.) PS If we do the root sieve, do you want the sizeopt hits as well as the final polys? Edit: When using `split -n`, be sure to right `split -n l/2` as opposed to `split -n 2`. That doesn't split lines Last fiddled with by Dubslow on 2013-02-07 at 06:20

2013-02-08, 11:49	#107
akruppa "Nancy" Aug 2002 Alexandria 9A3₁₆ Posts	The alpha value is a measure for how many very small prime factors the polynomial values contain on average. We are looking for smooth polynomial values (= no large prime factors), and there will be more of those in the search region if the polynomial values tend to contain a lot of very small primes. The alpha value tells that, thanks to having many small primes, polynomial values F(a,b) are about as likely smooth as as an integer around F(a,b)exp(alpha), so with alpha=-12, the polynomial values are about as likely to be smooth as if they were smaller by a factor of ~16000. Last fiddled with by akruppa on 2013-02-08 at 13:32 Reason: of->if. Edit: ah, I had not taken into consideration that this was a deg 5 vs. deg 6 issue. thanks Jason!*

2013-02-08, 13:07	#109
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	The other thing that really jumps out at me from the list of best polynomials is that all of them are coming from stage 1 hits found by the CADO tools. I think the Msieve hits are the ones with lots of high-order zeroes in the leading algebraic coefficient, and in all the stage 2 that I've run locally the best E value I've been able to find from an Msieve stage 1 hit is around 3e-19. Paul has been suggesting that targeting a leading rational coefficient size that is somewhat smaller than the maximum possible, for a given choice of stage 1 size bound, gives a better chance of a good polynomial after size optimization. Looks like I should try a few experiments. I think all of modern GNFS polynomial selection is basically a struggle to increase the amount of skew without making stage 1 stop working; the end result is a playground of absurd alpha values. It doesn't hurt that the playground is enormously larger now that we're in degree-6 territory (an alpha value < -5 is still pretty unusual for degree-5 polynomials). Shi Bai's dissertation found that for RSA768 a large sampling of size-optimized polynomials had a mean alpha value of -0.2 and standard deviation of about 0.8; so finding an alpha value of say -10.0 is a 12-sigma event. Last fiddled with by jasonp on 2013-02-08 at 13:21

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Volunteers needed	axn	GPU Computing	28	2012-05-28 12:05
call for volunteers: RSA768 polynomial selection	jasonp	Operation Kibibit	200	2011-11-05 21:31
Call for help	Wacky	NFSNET Discussion	13	2005-07-14 00:25
Volunteers needed!	Xyzzy	Hardware	23	2003-04-18 23:27
We need two volunteers...	Xyzzy	PrimeNet	8	2003-02-27 02:26

2013-02-06, 12:26	#100
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	Their best is 3.51e-19; the full 5000 will probably take 5 days on one core

2013-02-09, 06:53	#110
frmky Jul 2003 So Cal 11²×17 Posts	Here's another 9.5 million. I've stopped it for now. https://www.dropbox.com/s/meef9g9dkq...896_4.dat.m.gz