|
[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? |
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? |
Their best is 3.51e-19; the full 5000 will probably take 5 days on one core
|
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: |
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: |
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] |
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] |
[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. |
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 |
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.
|
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. |
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. |
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=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. |
Finished completely with batch 7. Best I got was 2.42e-19 of combined e.
|
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 |
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. |
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 |
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. |
[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. |
[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 :( |
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] |
make sure to delete the .fb file from previous runs; poly selection won't happen if a poly was previously selected :)
|
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] |
[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] |
[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? |
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 |
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? |
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. |
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. |
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. |
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)
|
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 |
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? |
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.
|
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. |
[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? |
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 14:35. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.