mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Operation Kibibit (https://www.mersenneforum.org/forumdisplay.php?f=97)
-   -   Call for volunteers: RSA896 (https://www.mersenneforum.org/showthread.php?t=17460)

Dubslow 2013-02-05 00:24

[QUOTE=WraithX;327585]That should be fine. I should be done with my two by then, and can pick up Batch 6, plus this new one.[/QUOTE]

Me too :razz: (my first batch will finish Tuesday to Wednesday overnight). Can we perhaps split 6 and his weekend dump?

Dubslow 2013-02-06 05:04

My batch has finished. Not having heard anything, I started the root sieve... if that finishes too, then I'll grab batch 6.

Edit: In some 20 minutes, I'm seeing 1e-19 with a scattering north of 2e-19. Not particularly impressive, though I am running the full 5000 so... who knows. What's their current best? Is the target still 2e-18?

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 .dat.ms.mpi* 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
[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
[/code]

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
[code]
# norm 5.520074e-020 [B]alpha -12.511594[/B] e 2.837e-019 rroots 4
[/code][/QUOTE]

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

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
[/code]
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.
[url]https://www.dropbox.com/s/meef9g9dkq1j0pz/rsa896_4.dat.m.gz[/url]

WraithX 2013-02-09 07:38

[QUOTE=frmky;328653]Here's another 9.5 million. I've stopped it for now.
[url]https://www.dropbox.com/s/meef9g9dkq1j0pz/rsa896_4.dat.m.gz[/url][/QUOTE]

I have finished my 2 batches of 5M. I'll go ahead and take this batch. Jason, I'll upload all the results once I finish this batch.

poily 2013-02-09 21:09

Finished completely with batch 7. Best I got was 2.42e-19 of combined e.

firejuggler 2013-02-10 19:31

1 Attachment(s)
here are my 5000 best hit
only ran size optimisation...
will run root opti for the top 100
but from earlier run,
[code]
Sat Feb 09 12:13:30 2013 R0: -6203084730713792276611133070779722382751981
Sat Feb 09 12:13:30 2013 R1: 42260925725431380236248723
Sat Feb 09 12:13:30 2013 A0: 592294109350104075885455758432520983785765035911272504595840
Sat Feb 09 12:13:30 2013 A1: -44228198432626906079450591344684081042731028765034896
Sat Feb 09 12:13:30 2013 A2: -1266780839981054007483109448136912523638841412
Sat Feb 09 12:13:30 2013 A3: 25584881562241130646568639974012624680
Sat Feb 09 12:13:30 2013 A4: -32136804857417066806626443393
Sat Feb 09 12:13:30 2013 A5: -3165936771052409436964
Sat Feb 09 12:13:30 2013 A6: 7232286821760
Sat Feb 09 12:13:30 2013 skew 88161163.72, size 5.554e-020, alpha -12.726, combined = 2.853e-019 rroots = 4
[/code]
is my best

Dubslow 2013-02-10 21:13

Okay, the batch 3 top-5000 root opt is complete, and this was the not-very-good best:
[code]# norm 6.222097e-20 alpha -11.905801 e 2.809e-19 rroots 4
skew: 61769793.67
c0: 145232831029996093163552361863066803348899730697627094912576
c1: 1472498973799415233497204250419859073914693142439276
c2: -309381525988912811338453294676772024749774984
c3: -512903027606228113001250486017991403
c4: 32343323870153789851863490738
c5: 180328757325985585752
c6: 5966748627840
Y0: -6405170523828211176788244501877849165285655
Y1: 159602931489094517610579779[/code]

I'll start rootopt on the top-1000 of batch 6 momentarily, and will upload all results at once.

firejuggler 2013-02-10 22:23

best poly only slightly better
[code]
Sun Feb 10 23:04:13 2013 R0: -6121810884144972706146540517486139870590622
Sun Feb 10 23:04:13 2013 R1: 2435907600823901442520753
Sun Feb 10 23:04:13 2013 A0: -300111002775699634366748860938862248175411656644137966719225
Sun Feb 10 23:04:13 2013 A1: -17621784293264685805864325144713943857874136634393260
Sun Feb 10 23:04:13 2013 A2: 498095951660428193317679316044985385382946564
Sun Feb 10 23:04:13 2013 A3: 24445078002437030133657739422237219418
Sun Feb 10 23:04:13 2013 A4: -206436615132453702777897484267
Sun Feb 10 23:04:13 2013 A5: -2593745547217833521550
Sun Feb 10 23:04:13 2013 A6: 7827849469440
Sun Feb 10 23:04:13 2013 skew 67686502.19, size 5.627e-020, alpha -12.009, combined = 2.887e-019 rroots = 6
[/code]
2.853 to 2.887, 1% better

Dubslow 2013-02-11 14:45

Top 1000 of batch 6 revealed this better-but-not-great best:
[code]Sun Feb 10 21:03:13 2013 polynomial selection complete
Sun Feb 10 21:03:13 2013 R0: -6861489586646307495841370548381377833058191
Sun Feb 10 21:03:13 2013 R1: 3562982110672646277353362747
Sun Feb 10 21:03:13 2013 A0: 1397116357446289568248089240738277216190197418531172590400
Sun Feb 10 21:03:13 2013 A1: 2798522157134386626865301273289555923795160762285992
Sun Feb 10 21:03:13 2013 A2: -131505870094157041369095365530216420938114820
Sun Feb 10 21:03:13 2013 A3: -3167161386190221226627602128211193654
Sun Feb 10 21:03:13 2013 A4: 43173308215309686805724932635
Sun Feb 10 21:03:13 2013 A5: 618865219486539197262
Sun Feb 10 21:03:13 2013 A6: 3948311727360
Sun Feb 10 21:03:13 2013 skew 50359208.73, size 5.943e-20, alpha -11.761, combined = 3.105e-19 rroots = 4
Sun Feb 10 21:03:13 2013 elapsed time 05:18:06[/code]
Upload coming in some hours.

Dubslow 2013-02-11 23:56

[QUOTE=Dubslow;328966]
Upload coming in some hours.[/QUOTE]

I've finally gotten around to [URL="http://dubslow.tk/random/batches3and6.tar.gz"]it[/URL]. That's all results of batches 3 and 6 -- caution, it's a hefty 2.09 GiB.

jasonp 2013-02-14 21:52

[QUOTE=Dubslow;328882]Okay, the batch 3 top-5000 root opt is complete, and this was the not-very-good best:
[code]# norm 6.222097e-20 alpha -11.905801 e 2.809e-19 rroots 4
skew: 61769793.67
c0: 145232831029996093163552361863066803348899730697627094912576
c1: 1472498973799415233497204250419859073914693142439276
c2: -309381525988912811338453294676772024749774984
c3: -512903027606228113001250486017991403
c4: 32343323870153789851863490738
c5: 180328757325985585752
c6: 5966748627840
Y0: -6405170523828211176788244501877849165285655
Y1: 159602931489094517610579779[/code]
[/QUOTE]
Could you grep through your dataset for the size-optimized polynomial that generated this, then rerun stage 2 with

-ncr "stage2_norm=1e100"

to see if the best poly changes? If you take the stage 1 hit of this polynomial, then run the CADO size optimization and the CADO root sieve, you get a polynomial that is the 3rd-best across the entire batch, with an E value of 3.47e-19

I've also seen it go the other way, where Msieve produces a polynomial 20% better than the CADO tools, starting from the same stage 1 hit.

I wish this process was a more exact science :(

Dubslow 2013-02-15 16:53

Okay, I only found one size-opt hit where both leading coeffs were the same. The results aren't very encouraging, though per the last command it's entirely possible I screwed it up.

[code]bill@Gravemind ~/msieve ∰∂ grep "159602931489094517610579779" batch3.ms | grep "5966748627840" > thebigtest.ms
bill@Gravemind ~/msieve ∰∂ cat thebigtest.ms
5966748627840 292915719056610727512 36064024000366164152339517778 -84497976889235989825064880544623387 -4788238179361086188471687577637977225787162 4303872043414327223117808302910530617580272619100 81812578696380352446961680035616654504774205872670962790 159602931489094517610579779 -6405170523326284855312354542737323010776179 -3.25 7.963209e+32
bill@Gravemind ~/msieve ∰∂ ./msieve -s thebigtest -npr "stage2_norm=1e100" -v -v


Msieve v. 1.51 (SVN 839M)
Fri Feb 15 10:57:05 2013
random seeds: 3f19d3de de1d536a
factoring 412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391 (270 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (270-digit input)
R0: -6405170523828211176788244501877849165285655
R1: 159602931489094517610579779
A0: 145232831029996093163552361863066803348899730697627094912576
A1: 1472498973799415233497204250419859073914693142439276
A2: -309381525988912811338453294676772024749774984
A3: -512903027606228113001250486017991403
A4: 32343323870153789851863490738
A5: 180328757325985585752
A6: 5966748627840
skew 61769793.67, size 5.287e-20, alpha -11.906, combined = 2.809e-19 rroots = 4
elapsed time 00:00:02
bill@Gravemind ~/msieve ∰∂ ls thebigtest.p
ls: cannot access thebigtest.p: No such file or directory[/code]

jasonp 2013-02-15 17:40

make sure to delete the .fb file from previous runs; poly selection won't happen if a poly was previously selected :)

firejuggler 2013-02-15 18:06

Since I had a slightly better poly than Dubslow, could anyone run the root optimisation on CADO to see if it get any better?
ms line is
[code]
7827849469440 -1688698656210866333070 -412741298353303163926536130117 22088628597291494753673208243029819 2460026875023452236191886387968291153532877 -51597763639642042798524045753868032621520266693 -1903072627680759370872623350274028735027372531045504753 2435907600823901442520753 -6121810884098033236808830895701743366785951 -2.85 2.713411e+033
[/code]

Dubslow 2013-02-15 18:07

[QUOTE=jasonp;329610]make sure to delete the .fb file from previous runs; poly selection won't happen if a poly was previously selected :)[/QUOTE]

:doh!:

Still no dice though :no:

[code]bill@Gravemind ~/msieve ∰∂ ls *.fb
ls: cannot access *.fb: No such file or directory
bill@Gravemind ~/msieve ∰∂ ./msieve -s thebigtest -npr "stage2_norm=1e100" -v -v


Msieve v. 1.51 (SVN 839M)
Fri Feb 15 12:06:31 2013
random seeds: a9bce674 006c45eb
factoring 412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391 (270 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (270-digit input)
commencing number field sieve polynomial selection
polynomial degree: 6
max stage 1 norm: 1.08e+35
max stage 2 norm: 1.00e+100
min E-value: 0.00e+00
poly select deadline: 1079999
<some output cut>
save 3.947336e-20 -11.0664 83032873.06 1.919553e-19 rroots 2
save 4.221554e-20 -10.9790 71903889.86 2.036061e-19 rroots 2
save 3.961664e-20 -10.9835 79329497.80 1.926043e-19 rroots 2
save 3.999238e-20 -11.0302 73106527.34 1.945457e-19 rroots 2
save 3.757523e-20 -10.7323 76486451.56 1.844546e-19 rroots 2
save 4.200518e-20 -10.9976 67624205.44 2.028932e-19 rroots 2
save 4.176910e-20 -10.8469 64825762.71 2.016148e-19 rroots 2
save 3.807056e-20 -10.8570 80262611.92 1.864303e-19 rroots 2
save 4.642810e-20 -11.3833 72318759.06 2.203331e-19 rroots 2
save 4.195944e-20 -11.1807 78137314.03 2.020283e-19 rroots 2
save 4.433539e-20 -11.1565 66924211.34 2.117983e-19 rroots 2
save 3.893669e-20 -10.8356 70668120.76 1.902271e-19 rroots 2
save 4.154376e-20 -11.3156 86416034.04 2.003224e-19 rroots 2
save 4.057933e-20 -11.1925 84146225.68 1.964144e-19 rroots 2
save 4.712178e-20 -11.4340 67858297.12 2.231041e-19 rroots 2
save 4.152387e-20 -10.9331 71694473.04 2.004684e-19 rroots 2
save 4.216924e-20 -11.2536 81619909.97 2.028894e-19 rroots 2
save 4.934413e-20 -11.6056 73488501.64 2.310342e-19 rroots 2
save 4.688152e-20 -11.4344 73565281.50 2.218281e-19 rroots 2
save 3.830063e-20 -11.1606 83666319.72 1.878981e-19 rroots 0
save 3.747557e-20 -10.9032 83747052.72 1.838701e-19 rroots 2
save 4.264919e-20 -11.3510 83343653.25 2.046403e-19 rroots 2
save 4.428248e-20 -11.1230 65199380.06 2.116410e-19 rroots 2
save 4.145648e-20 -11.0592 74433647.23 2.004079e-19 rroots 2
save 4.012624e-20 -11.0295 76371673.59 1.949163e-19 rroots 2
save 3.802001e-20 -10.8642 79223149.73 1.861223e-19 rroots 2
save 3.811027e-20 -11.0082 79488242.07 1.871807e-19 rroots 0
save 4.706179e-20 -11.1340 60395776.89 2.227407e-19 rroots 2
save 4.448211e-20 -11.5815 86469038.59 2.118081e-19 rroots 2
save 4.160428e-20 -10.9427 67360379.26 2.013214e-19 rroots 2
save 4.131368e-20 -11.3841 85509485.39 1.998267e-19 rroots 0
save 4.079451e-20 -10.9952 76076785.46 1.974375e-19 rroots 2
save 4.140827e-20 -11.2588 83942311.77 1.997031e-19 rroots 2
save 4.255084e-20 -10.9028 68621177.37 2.049908e-19 rroots 2
save 4.256610e-20 -10.8840 63981278.39 2.053264e-19 rroots 2
save 4.657343e-20 -11.1925 63527096.61 2.212837e-19 rroots 2
save 4.403163e-20 -10.8138 57929704.14 2.103857e-19 rroots 2
save 4.587910e-20 -11.0303 60641423.29 2.184811e-19 rroots 2
save 3.670518e-20 -10.7047 74614643.68 1.814621e-19 rroots 0
save 4.695195e-20 -11.2385 68353911.15 2.224453e-19 rroots 2
save 4.508486e-20 -11.1086 64879354.16 2.150458e-19 rroots 2
save 3.815136e-20 -10.8629 80117606.38 1.867611e-19 rroots 2
save 4.646511e-20 -11.5507 80552594.85 2.200953e-19 rroots 2
save 5.650782e-20 -11.4279 58048969.28 2.596585e-19 rroots 2
save 4.416760e-20 -11.1866 71527268.43 2.109720e-19 rroots 2
save 4.516239e-20 -11.4791 80948111.76 2.147299e-19 rroots 2
save 4.143805e-20 -10.8801 70091379.91 2.001551e-19 rroots 2
save 4.593008e-20 -11.3070 67534867.63 2.185097e-19 rroots 2
save 4.132403e-20 -10.6159 62370341.50 2.000684e-19 rroots 2
save 4.640242e-20 -11.0296 65025043.12 2.201471e-19 rroots 2
save 4.174704e-20 -10.7153 63346893.35 2.016551e-19 rroots 2
save 5.311891e-20 -11.2311 54488294.71 2.466066e-19 rroots 4
save 5.009504e-20 -11.1024 59632168.69 2.343119e-19 rroots 4
save 4.630128e-20 -11.1450 63054304.34 2.201754e-19 rroots 2
save 4.504668e-20 -11.7496 83616549.38 2.143715e-19 rroots 2
save 4.623599e-20 -11.1866 68410255.43 2.196254e-19 rroots 2
save 5.041043e-20 -11.1417 59970566.27 2.361389e-19 rroots 2
save 3.955263e-20 -10.8369 74989182.85 1.926630e-19 rroots 2
save 4.369945e-20 -11.1095 72655258.69 2.094132e-19 rroots 2
save 4.811656e-20 -11.1958 64149680.18 2.266193e-19 rroots 0
save 4.625367e-20 -11.1980 69650845.37 2.196668e-19 rroots 2
save 4.095296e-20 -10.9491 75055588.28 1.984572e-19 rroots 2
save 4.191206e-20 -10.9489 67164789.55 2.023724e-19 rroots 2
save 3.653828e-20 -10.6603 78454164.39 1.802481e-19 rroots 2
save 4.790134e-20 -11.2734 67947196.28 2.261771e-19 rroots 2
save 4.739820e-20 -10.8710 53456751.96 2.235389e-19 rroots 2
save 4.818606e-20 -11.3443 64694972.58 2.268538e-19 rroots 2
save 4.475268e-20 -11.6216 88004473.00 2.130008e-19 rroots 2
save 4.835692e-20 -11.3066 67745221.37 2.280555e-19 rroots 2
save 3.988391e-20 -11.0951 81673640.57 1.936002e-19 rroots 2
save 4.018257e-20 -11.2769 87451376.84 1.945082e-19 rroots 2
save 5.117322e-20 -11.5321 62696790.59 2.391193e-19 rroots 2
save 3.960427e-20 -10.7816 72516669.36 1.928982e-19 rroots 2
save 4.778196e-20 -11.3050 63944367.44 2.258207e-19 rroots 2
save 6.130356e-20 -11.4356 44785612.91 2.774045e-19 rroots 2
save 4.185609e-20 -11.1317 78224184.69 2.017825e-19 rroots 2
save 6.222097e-20 -11.9058 61769793.67 2.808913e-19 rroots 4
save 4.264545e-20 -10.2442 54950573.38 2.051534e-19 rroots 2
save 4.928169e-20 -11.5086 71926461.06 2.312945e-19 rroots 2
save 4.196658e-20 -11.1476 71953894.63 2.025306e-19 rroots 2
save 4.646550e-20 -11.2352 65184288.65 2.207704e-19 rroots 2
save 4.516357e-20 -11.2060 71861109.02 2.152382e-19 rroots 2
save 4.150550e-20 -10.9148 66891079.47 2.007884e-19 rroots 2
save 4.677628e-20 -11.0511 59232693.67 2.219747e-19 rroots 2
save 4.824944e-20 -11.6306 74952367.47 2.273217e-19 rroots 2
save 4.032679e-20 -11.0104 74218403.15 1.963662e-19 rroots 0
save 4.860252e-20 -10.6232 56532120.39 2.277392e-19 rroots 4
save 4.004554e-20 -10.9140 72373478.15 1.951858e-19 rroots 0
save 5.548791e-20 -11.8212 68087748.44 2.555402e-19 rroots 2
save 3.724777e-20 -10.8287 75935840.11 1.836061e-19 rroots 0
save 4.352597e-20 -10.9005 60616778.58 2.090089e-19 rroots 2
save 3.997581e-20 -10.7941 66980826.67 1.944471e-19 rroots 2
save 3.824978e-20 -10.5894 70361050.54 1.874172e-19 rroots 2
save 4.358953e-20 -11.0892 71473669.62 2.090628e-19 rroots 2
save 4.618876e-20 -10.8968 60031862.15 2.199680e-19 rroots 2
save 4.183853e-20 -11.0079 68424173.57 2.021327e-19 rroots 2
save 5.380261e-20 -10.9908 48889688.23 2.497998e-19 rroots 4
save 4.007341e-20 -10.5354 62556259.55 1.951674e-19 rroots 2
save 4.814487e-20 -11.3321 68668709.63 2.272555e-19 rroots 2
save 4.702187e-20 -10.9579 60193142.86 2.232610e-19 rroots 2
save 4.842087e-20 -11.0021 59493315.37 2.281551e-19 rroots 4
save 5.008828e-20 -11.1593 58963849.46 2.352263e-19 rroots 2
save 4.894984e-20 -11.0813 60711739.54 2.303307e-19 rroots 2
save 4.689371e-20 -11.2929 70516907.06 2.222772e-19 rroots 2
save 5.961949e-20 -11.3175 56653159.66 2.693459e-19 rroots 4
save 4.375730e-20 -11.1637 71946658.31 2.097877e-19 rroots 2
save 4.383412e-20 -11.0724 65300054.68 2.103078e-19 rroots 2
save 4.139671e-20 -10.9816 68676294.45 2.003438e-19 rroots 2
save 3.964200e-20 -10.5476 65248753.94 1.934492e-19 rroots 2
save 4.342538e-20 -10.7197 60759121.38 2.088801e-19 rroots 2
save 4.417396e-20 -11.1453 72453096.36 2.112986e-19 rroots 2
save 3.856231e-20 -10.9713 82325533.65 1.882524e-19 rroots 2
save 4.676908e-20 -11.4711 74739217.91 2.211562e-19 rroots 2
save 5.255395e-20 -11.2297 60044080.87 2.436631e-19 rroots 4
save 6.099422e-20 -11.6128 48262868.16 2.751184e-19 rroots 2
save 4.738095e-20 -11.0734 58545390.87 2.243234e-19 rroots 2
save 4.486233e-20 -10.7002 59376648.00 2.144302e-19 rroots 2
save 5.344911e-20 -11.7338 69976353.91 2.476282e-19 rroots 2
save 4.106341e-20 -11.2040 77691884.96 1.992308e-19 rroots 0
save 4.032072e-20 -10.9286 69542696.67 1.953116e-19 rroots 2
save 3.983298e-20 -11.0079 72942968.36 1.939244e-19 rroots 2
save 5.338276e-20 -10.9932 50932015.73 2.481216e-19 rroots 4
save 4.973592e-20 -11.1273 62499956.65 2.332509e-19 rroots 4
save 5.000013e-20 -12.1380 88068448.46 2.341618e-19 rroots 0
save 4.308004e-20 -10.8922 62686605.42 2.074598e-19 rroots 2
save 5.664843e-20 -11.5932 60738719.77 2.599602e-19 rroots 2
save 3.871707e-20 -10.7746 74731574.48 1.890864e-19 rroots 2
save 5.761066e-20 -11.6032 59882226.21 2.637687e-19 rroots 2
save 5.272300e-20 -11.2583 56650202.64 2.450695e-19 rroots 4
save 4.667325e-20 -10.9000 58697978.97 2.219013e-19 rroots 2
save 4.561481e-20 -11.2828 72782143.83 2.167579e-19 rroots 2
save 4.506090e-20 -10.7861 59313631.45 2.155403e-19 rroots 2
save 4.338009e-20 -10.8601 63493611.43 2.078709e-19 rroots 2
save 4.788762e-20 -11.3248 69779467.09 2.260781e-19 rroots 2
save 4.706070e-20 -11.0031 61253680.91 2.233388e-19 rroots 2
save 4.516019e-20 -11.2548 72810497.47 2.150483e-19 rroots 2
save 6.210916e-20 -11.9057 63108934.50 2.803155e-19 rroots 4
save 4.527742e-20 -10.9387 62024304.39 2.160760e-19 rroots 2
polynomial selection complete
R0: -6405170523828211176788244501877849165285655
R1: 159602931489094517610579779
A0: 145232831029996093163552361863066803348899730697627094912576
A1: 1472498973799415233497204250419859073914693142439276
A2: -309381525988912811338453294676772024749774984
A3: -512903027606228113001250486017991403
A4: 32343323870153789851863490738
A5: 180328757325985585752
A6: 5966748627840
skew 61769793.67, size 5.287e-20, alpha -11.906, [B]combined = 2.809e-19[/B] rroots = 4
elapsed time 00:01:13[/code]

Gimarel 2013-02-15 18:58

[QUOTE=Dubslow;329606]

[code]bill@Gravemind ~/msieve ∰∂ grep "159602931489094517610579779" batch3.ms | grep "5966748627840" > thebigtest.ms
bill@Gravemind ~/msieve ∰∂ cat thebigtest.ms
5966748627840 292915719056610727512 36064024000366164152339517778 -84497976889235989825064880544623387 -4788238179361086188471687577637977225787162 4303872043414327223117808302910530617580272619100 81812578696380352446961680035616654504774205872670962790 159602931489094517610579779 -6405170523326284855312354542737323010776179 -3.25 7.963209e+32
[/code][/QUOTE]

I got the most polys with a score above 2.50e-19 with stage 2 norm: 1.20e+33:
[code]Msieve v. 1.51 (SVN 839M)
Fri Feb 15 19:51:17 2013
random seeds: 719b210b 22a03ff6
factoring 412023436986659543855531365332575948179811699844327982845455626433876445565248426198098870423161841879261420247188869492560931776375033421130982397485150944909106910269861031862704114880866970564902903653658867433731720813104105190864254793282601391257624033946373269391 (270 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (270-digit input)
commencing number field sieve polynomial selection
polynomial degree: 6
max stage 1 norm: 1.08e+35
max stage 2 norm: 1.20e+33
min E-value: 2.50e-19
poly select deadline: 1079999
[...]
save [B]7.491684e-20[/B] -10.1530 14270747.03 3.315128e-19 rroots 4
[...]
polynomial selection complete
R0: -6405170523519122224431286189938989038316907
R1: 159602931489094517610579779
A0: 68050626433271578568685318384352221775949125521047347600
A1: 6144946836109582823983851878814170306470571520300
A2: -4171051543490272451276859199331047990888844
A3: -254727236480010525923254455550860891
A4: 34425129368405391826107226258
A5: 249660419287936454232
A6: 5966748627840
skew 14270747.03, size [B]6.366e-20[/B], alpha -10.153, combined = 3.315e-19 rroots = 4
elapsed time 00:00:46
[/code]Why is the size in the "save" line bigger?

firejuggler 2013-02-15 19:14

wait wait wait... with msieve -npr "stage2_norm=12e32" I get far better result than I had earlier.... computing new best result.

Fri Feb 15 20:55:44 2013 R0: -8602096380804936115194404235733410890312881
Fri Feb 15 20:55:44 2013 R1: 13336877807413110230062477633
Fri Feb 15 20:55:44 2013 A0: -209182739253053726006655140318918878927879369767192283200
Fri Feb 15 20:55:44 2013 A1: 125164652462062643025205625739311696127937050356640
Fri Feb 15 20:55:44 2013 A2: -4785329834286322636391025094355563171194884
Fri Feb 15 20:55:44 2013 A3: -277563743821608084465382222135625976
Fri Feb 15 20:55:44 2013 A4: 544132459232583515175160993
Fri Feb 15 20:55:44 2013 A5: 68260653031946708330
Fri Feb 15 20:55:44 2013 A6: 1016941685760
Fri Feb 15 20:55:44 2013 skew 36575029.84, size 7.565e-020, alpha -9.839, combined = 3.773e-019 rroots = 4

jasonp 2013-02-16 14:27

With the patch that corrects the E-value calculation in SVN 839, the E-value for this last poly is 3.35e-19. This hit has generated their second best, processing with the CADO tools makes a poly with an E-value of 3.50e-19.

Re-running with a smarter stage 2 bound has touched on a somewhat hard problem: we have good algorithms for optimizing the size and very good algorithms for optimizing the roots, but we don't have a good algorithm for optimizing both together (which is what we really want). The compromise in Msieve is that the root optimization is run several times in a row, with the tolerance for worsening the polynomial size increased a little bit each time.

The hope is that polynomials with good size and mediocre root score can compete fairly with polynomials that have mediocre size and excellent root score; the root optimization is very good at producing the latter, and we don't want to drown out the former. Unfortunately, we also don't want to waste time finding the same polynomials over and over again because the tolerance increases by too little.

Currently the first step allows the size to worsen by just 1%, and every succeeding step increases the maximum allowed size by 10%, with a maximum increase given by the stage 2 bound. I guess you can see where this is going: a smart bound increases the size by a little and allows a big root score, while a dumb bound forces a huge root score which will drown out the polynomials that are better.

Automating this process needs to improve; any suggestions?

WraithX 2013-02-17 03:30

Here are my results for batches 2, 5, and 9 (Greg's batch):
[CODE]

From batch 2:
R0: -6855869630699907297016091570304929889936744
R1: 86349725434269516607067101
A0: 100158310063556836609424486493914328735190128179865119167855
A1: -394990555280339871011830300371523604675119606505737
A2: -709978045797318419010032402067014668615306191
A3: 1679401557742011648176099672714595361
A4: 276923296126601996543175262664
A5: -55142581362066684912
A6: 3967771167360
skew 58147449.96, size 5.001e-20, alpha -12.316, combined = 2.677e-19 rroots = 4
From:
3967771167360 -91085255453899353072 277475224322993651395583591624 5502935258205953253131044671638582 -7640474446693880222487188912243687936653594 -59358838933024945735476317518946620449860987228 27301996689933189377473808212046382630942332215517279751 86349725434269516607067101 -6855869630830276040083341264009881229416120 -3.29 2.547156e+33
***** Top 10:
opt2aa.p:# norm 5.657758e-20 alpha -12.211184 e 2.575e-19 rroots 4
opt2aa.p:# norm 5.654170e-20 alpha -12.168969 e 2.589e-19 rroots 4
opt2ab.p:# norm 5.803114e-20 alpha -12.399379 e 2.592e-19 rroots 6
opt2aa.p:# norm 5.708818e-20 alpha -12.196063 e 2.610e-19 rroots 4
opt2aa.p:# norm 5.760602e-20 alpha -12.387765 e 2.618e-19 rroots 4
opt2aa.p:# norm 5.829761e-20 alpha -12.164240 e 2.630e-19 rroots 6
opt2aa.p:# norm 5.884062e-20 alpha -12.040180 e 2.639e-19 rroots 6
opt2aa.p:# norm 5.860074e-20 alpha -13.215139 e 2.640e-19 rroots 4
opt2aa.p:# norm 5.906234e-20 alpha -12.076853 e 2.650e-19 rroots 6
opt2aa.p:# norm 5.885947e-20 alpha -12.315827 e 2.677e-19 rroots 4

Best from batch 2's top-hit with -npr "stage2_norm=1e100":
R0: -6855869631000587402945270139472730383670864
R1: 86349725434269516607067101
A0: 74508181967795609691517252344366344164862330856662635315575
A1: -776711227130695299602103701349312914814694457258897
A2: -707343211865885742506847334492386203663820831
A3: -2187755645988071135320214589146203359
A4: 278605009439190533400325889864
A5: -138040113385792304112
A6: 3967771167360
skew 57290205.68, size 4.851e-20, alpha -12.196, combined = 2.610e-19 rroots = 4

----------------------------------------------------------------------------------

From batch 5:
R0: -5079058595573691211348499019984436079905212
R1: 16280553833711580879589
A0: 125382381632513274348653582122621570068763933866804464170435
A1: 14600964560275661758691695100885222925681365777059427
A2: -227074712183287095332391015632065165050705545
A3: -36566391981865550677305842415043155283
A4: 171383792470404231033152080534
A5: 4331988930768632472416
A6: 24000626666016
skew 47381579.79, size 4.503e-20, alpha -12.296, combined = 2.440e-19 rroots = 4
From:
24000626666016 7290190778608754427488 768256288944493407202298872854 -41799476202620172637158062363831455 -2007192506392900153322682538208589944907837 42793118685565186623233786928172590130028550948 680598398148773355838987641317982642706462342502035767 16280553833711580879589 -5079058595573356767550392277155446534725864 -2.81 3.485938e+33
***** Top 10:
opt5aa.p:# norm 4.867489e-20 alpha -11.669333 e 2.263e-19 rroots 2
opt5aa.p:# norm 4.929563e-20 alpha -11.422590 e 2.272e-19 rroots 4
opt5aa.p:# norm 4.901277e-20 alpha -12.133445 e 2.276e-19 rroots 4
opt5aa.p:# norm 4.904579e-20 alpha -11.983352 e 2.284e-19 rroots 4
opt5aa.p:# norm 4.960431e-20 alpha -11.229162 e 2.324e-19 rroots 4
opt5aa.p:# norm 5.028284e-20 alpha -11.714913 e 2.327e-19 rroots 2
opt5aa.p:# norm 5.027374e-20 alpha -11.485735 e 2.329e-19 rroots 2
opt5aa.p:# norm 5.037490e-20 alpha -11.237410 e 2.340e-19 rroots 4
opt5aa.p:# norm 5.188732e-20 alpha -11.926101 e 2.408e-19 rroots 4
opt5aa.p:# norm 5.299550e-20 alpha -12.295540 e 2.440e-19 rroots 4

Best from batch 5's top-hit with -npr "stage2_norm=1e100":
R0: -5079058595574105383298006985144614295560020
R1: 16280553833711580879589
A0: 143439954791504823156181580567022023618171837151575564284851
A1: 29037909125744013934454577050399296065787116074167101
A2: -533108457619359347510551867204977971549343441
A3: -33873460838810991648509253029674507525
A4: -146648323476537770267231977066
A5: 668580509701228951904
A6: 24000626666016
skew 61596119.67, size 4.199e-20, alpha -12.282, combined = 2.305e-19 rroots = 4

----------------------------------------------------------------------------------

From Greg's 9.6M post:
R0: -4280297519216461984044491095671332337372128
R1: 3880170414765579177875
A0: -1560327327914053039817428213916139986286101543999394209625
A1: 325845275959167670894348281931881321332889289335605
A2: 19861507299135232801412024494835114256509982
A3: -1875959661010151505378959924689772238
A4: -92587082744580628276562309125
A5: 650066562286997881209
A6: 67000520399904
skew 21401253.00, size 4.216e-20, alpha -9.989, combined = 2.338e-19 rroots = 4
From:
67000520399904 7223464034538398555001 229275131993656689147195005075 -335092032680832705166837238390596143 -4859772288297788070911043987453741038177209 2770749856426307578366616868163861841602432837509 13320038009956697955476039369569884286315069669169765439 3880170414765579177875 -4280297519216398537018895651508722763099128 -1.99 7.005018e+33
***** Top 10:
opt4aaa.p:# norm 4.618250e-20 alpha -11.023104 e 2.187e-19 rroots 2
opt4aab.p:# norm 4.636439e-20 alpha -11.668943 e 2.188e-19 rroots 4
opt4aaa.p:# norm 4.610967e-20 alpha -10.917803 e 2.189e-19 rroots 2
opt4aaa.p:# norm 4.639239e-20 alpha -11.642916 e 2.189e-19 rroots 4
opt4aaa.p:# norm 4.644409e-20 alpha -10.750694 e 2.190e-19 rroots 4
opt4aaa.p:# norm 4.805827e-20 alpha -11.332229 e 2.210e-19 rroots 4
opt4aaa.p:# norm 4.685694e-20 alpha -11.047476 e 2.217e-19 rroots 4
opt4aaa.p:# norm 4.682191e-20 alpha -10.610743 e 2.221e-19 rroots 4
opt4aaa.p:# norm 4.939291e-20 alpha -11.580436 e 2.273e-19 rroots 4
opt4aaa.p:# norm 4.961452e-20 alpha -9.989350 e 2.338e-19 rroots 4

Best from batch 9's top-hit with -npr "stage2_norm=1e100":
R0: -4280297519216402914316743956853904907444128
R1: 3880170414765579177875
A0: 41598337194677300308041011298830422262603230060973941309287
A1: -11327455795448811065386078747818063927490131948335139
A2: 122051576297456641580513701325102468768051358
A3: -1279685585946306960691283141270486518
A4: 189809488702852422361438828475
A5: 6769956272097160352121
A6: 67000520399904
skew 41008826.03, size 3.197e-20, alpha -11.376, combined = 1.839e-19 rroots = 2
[/CODE]
This was all with svn 839. It looks like re-running the top hit from each batch with -npr "stage2_norm=1e100" gave a result worse than the best found by msieve on autopilot. I did find that choosing a stage2_norm close to the stage1_norm (anywhere from 1.01x to 5x) seemed to give big variations in output poly's. However, I haven't seen better than what msieve did on autopilot yet. Though, I didn't try that many different variations.

Do you want the top 5000 from each batch? They are each about 1.7MB files. Let me know if there is any more info you need or anything else I can do to help.

jasonp 2013-02-17 12:52

Thanks for all the stage 2 work everybody. I just pointerd Paul's group to the last batch of stage 1 hits in my archives, and it looks like I exhausted everyone's patience so we should probably stop.

I'm just interested in your top-5000 size-optimized hits, not anything else really (they're a good shorthand for the tiny subset of our results worth analyzing in detail). I'd be grateful if you could just post your 1.7MB files somewhere (I don't have the mailbox capacity to be emailed a dozen of them).

This is a taste of what it feels like to participate in a record-size factorization. After 4 months we still don't have a good idea if we've gotten all the lucky breaks that we're entitled to, or whether it would be best to start sieving soon.

The results have also made it clear that I have more tweaking to do on this stage before we can safely throw BOINC-scale resources at a large polynomial selection job. Msieve gets good results but the CADO tools do a little bit better.

debrouxl 2013-02-17 15:48

I'm curious: while 35000 core-years are quite a bit easier to find in 2013-2016 than they used to be in 2006-2009, are there enough cores on Grid5000, and other public research grids in other countries, for not monopolizing a sizable chunk of said grids for RSA-896 factoring in less than a couple wall clock years of sieving ?

BTW, jasonp: is there anything wrong with poily's MPI polsel patch, whose latest version is at [url]http://www.mersenneforum.org/showpost.php?p=328523&postcount=108[/url] ? :smile:
I think it (or a modified / improved version thereof, if deemed necessary) would be a valuable addition to the msieve code base. It works alright for at least poily and me, and today, I've wasted a bit of CPU time due to pilot error: using an older version of that useful out-of-tree patch caused all hits to be processed by every job.

jasonp 2013-02-17 15:51

I haven't looked at the patch, and have no doubt it would work fine, but a year is too long to put off a major release, and everyone has been kind enough to pound on the current code pretty thoroughly. Ilya's work will definitely be pulled in, in the near future, but I just needed to get something out now (see the announcement in the Msieve subforum)

firejuggler 2013-02-17 19:16

re -ran with 1.51 , score confirmed to be @ 3.351

Sun Feb 17 19:41:20 2013 R0: -8602096380833397012435423812964364217581703
Sun Feb 17 19:41:20 2013 R1: 13336877807413110230062477633
Sun Feb 17 19:41:20 2013 A0: -209449862410891863327220520723260590181117542450185455872
Sun Feb 17 19:41:20 2013 A1: 125185072457735002625196594794175637735582223622256
Sun Feb 17 19:41:20 2013 A2: -4783552856337278387247256239963664387059484
Sun Feb 17 19:41:20 2013 A3: -277568385427917645087022656378108224
Sun Feb 17 19:41:20 2013 A4: 543404187531348016550278293
Sun Feb 17 19:41:20 2013 A5: 68247632110602237290
Sun Feb 17 19:41:20 2013 A6: 1016941685760
Sun Feb 17 19:41:20 2013 skew 36596706.80, size 6.428e-020, alpha -9.839, combined = 3.351e-019 rroots = 4

Dubslow 2013-02-17 22:41

Is Msieve stage 1 lacking compared to CADO stage 1? You mentioned something that seemed to indicate that a while back.

Edit: [URL="http://www.mersenneforum.org/showpost.php?p=328536&postcount=109"]Here[/URL]. On a re-read, it sounds like not better code, just better leading coefficients. Did anyone sort that out?

poily 2013-02-18 08:33

Actually that patch is still not working properly: it produces single .fb file with race condition (due to lack of .fb->.fb.mpi patching). But I guess Jason will fix it by himself someday.

jasonp 2013-02-18 21:04

Dubslow, not too sure; the choice of smaller leading rational coefficients is a code issue for Msieve, as these are always made as large as possible due to estimate by Thorsten Kleinjung in his 2006 Math. Comp. paper. By the time we get to RSA1024 I'm convinced we'll need a version of stage 1 that controls the size of the top 4 algebraic coefficients, not just the top 3, since with large skew it will become too rare to find a polynomial that is good at random.

Paul has also asked me to pass on his thanks for everyone's compute cycles, even though we didn't beat their best polynomial. Both CADO and Msieve have needed bug fixes to work correctly for problems this large, and that wouldn't have happened if you had not helped out.

lorgix 2013-09-03 18:11

[QUOTE=jasonp;329958]Dubslow, not too sure; the choice of smaller leading rational coefficients is a code issue for Msieve, as these are always made as large as possible due to estimate by Thorsten Kleinjung in his 2006 Math. Comp. paper. By the time we get to RSA1024 I'm convinced we'll need [B]a version of stage 1 that controls the size of the top 4 algebraic coefficients[/B], not just the top 3, since with large skew it will become too rare to find a polynomial that is good at random.

Paul has also asked me to pass on his thanks for everyone's compute cycles, even though we didn't beat their best polynomial. Both CADO and Msieve have needed bug fixes to work correctly for problems this large, and that wouldn't have happened if you had not helped out.[/QUOTE]
I had forgotten about the bold part when I posted in [URL="http://mersenneforum.org/showthread.php?p=351642#post351642"]the other thread[/URL]. Would a version that controls the top four be tricky to make?

jasonp 2013-09-03 22:08

We don't know how to do that at all, so it's not just a matter of code.


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

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