-   Operation Kibibit (
-   -   Call for volunteers: RSA896 (

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 :wink:

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* files are found :wink:

Dubslow 2013-02-07 05:41

I suddenly have two [i]more[/i] 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 :razz:

firejuggler 2013-02-07 18:22

i'm far from being done, but so far best poly give 2.837e-019
# 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]

[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]

[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[/code]

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[/code]

akruppa 2013-02-08 09:42

[QUOTE=firejuggler;328350]i'm far from being done, but so far best poly give 2.837e-019
# norm 5.520074e-020 [B]alpha -12.511594[/B] 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
# 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
# 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

1 Attachment(s)
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.

All times are UTC. The time now is 05:19.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.