Polynomial Request Thread - Page 74

Max0526 · 2017-03-31, 03:57

Quote:

Originally Posted by wombatman

Just as an update, I've taken the polynomials provided thus far and re-run them with my best found one. A number of the provided ones were better, and the best (shown below) decreased the expected run time by ~1/3.

Code:

Y0: -6563265022568774266354892868611644711400
Y1: 14737700014198380373
c0: -195885654413301742021926350959343936846901860317941
c1: 225759882978210651012918348758579232741188
c2: 23787287493217528319014779999797510
c3: -86292463186759936420108
c4: -70345879932722289
c5: 15085800
skew: 587128506.45611
type: gnfs

I am telling you -- CADO rocks!
Now seriously, I think that Msieve and CADO should always be used together for polynomial selection. None of them is better. The poly above is impossible to find using Msieve alone though.
I prefer CADO just because I have 6 AMD cores to run it on. I never even start Msieve polyselect from scratch because my GPU is super old (GT 430), and also because there is an army of Windows people running Msieve.
Installing Ubuntu takes minutes now, compiling CADO in it takes some more minutes. Both my machines have both Ubuntu and Windows partitions.
I probably should start a thread detailing how to throw polys back and forth between Msieve and CADO and what manual therapy should be performed to get better polys from the known ones.
Let me know if anybody is interested.

Dubslow · 2017-03-31, 04:41

Quote:

Originally Posted by Max0526

I am telling you -- CADO rocks!
Now seriously, I think that Msieve and CADO should always be used together for polynomial selection. None of them is better. The poly above is impossible to find using Msieve alone though.
I prefer CADO just because I have 6 AMD cores to run it on. I never even start Msieve polyselect from scratch because my GPU is super old (GT 430), and also because there is an army of Windows people running Msieve.
Installing Ubuntu takes minutes now, compiling CADO in it takes some more minutes. Both my machines have both Ubuntu and Windows partitions.
I probably should start a thread detailing how to throw polys back and forth between Msieve and CADO and what manual therapy should be performed to get better polys from the known ones.
Let me know if anybody is interested.

I would be interested except my hard drive died some months ago and one of the few things I didn't have an incidental backup of, was... well the python script I was using to bypass the CADO scripts (which offer very poor custom control, they're much more fire and forget for the whole of NFS, can't do any individual step).

I haven't fiddled with CADO since, unfortunately. Maybe I should return to it...

swellman · 2017-03-31, 11:11

Quote:

Originally Posted by Max0526

I am telling you -- CADO rocks!
Now seriously, I think that Msieve and CADO should always be used together for polynomial selection. None of them is better. The poly above is impossible to find using Msieve alone though.
I prefer CADO just because I have 6 AMD cores to run it on. I never even start Msieve polyselect from scratch because my GPU is super old (GT 430), and also because there is an army of Windows people running Msieve.
Installing Ubuntu takes minutes now, compiling CADO in it takes some more minutes. Both my machines have both Ubuntu and Windows partitions.
I probably should start a thread detailing how to throw polys back and forth between Msieve and CADO and what manual therapy should be performed to get better polys from the known ones.
Let me know if anybody is interested.

I would certainly be very interested in learning how to setup and use CADO as you describe. No doubt others would also be interested.

No hope then of using CADO in Windows? Migrating data back and forth between Linux and Windows environments sounds awkward is all. One could just keep it all in Linux of course...

wombatman · 2017-03-31, 11:40

Quote:

Originally Posted by Max0526

I am telling you -- CADO rocks!
Now seriously, I think that Msieve and CADO should always be used together for polynomial selection. None of them is better. The poly above is impossible to find using Msieve alone though.
I prefer CADO just because I have 6 AMD cores to run it on. I never even start Msieve polyselect from scratch because my GPU is super old (GT 430), and also because there is an army of Windows people running Msieve.
Installing Ubuntu takes minutes now, compiling CADO in it takes some more minutes. Both my machines have both Ubuntu and Windows partitions.
I probably should start a thread detailing how to throw polys back and forth between Msieve and CADO and what manual therapy should be performed to get better polys from the known ones.
Let me know if anybody is interested.

Quote:

Originally Posted by swellman

I would certainly be very interested in learning how to setup and use CADO as you describe. No doubt others would also be interested.

No hope then of using CADO in Windows? Migrating data back and forth between Linux and Windows environments sounds awkward is all. One could just keep it all in Linux of course...

I can try building CADO in the Ubuntu shell in Windows 10. That would eliminate the need for switching back and forth. Max, can you point me to the correct place to get the CADO source?

jasonp · 2017-04-01, 02:01

Note that the CADO developers do not care about windows at all and probably cannot be convinced to help if there are problems. I don't think any of them even have access to a windows machine.

That being said, CADO polynomial selection wouldn't require building the entire codebase. Make sure to use a windows port of gcc since 64-bit GMP expects a long integer to be 64 bits in size, and guaranteeing this minimizes the chance of silently failing.

wombatman · 2017-04-02, 02:49

Quote:

Originally Posted by jasonp

Note that the CADO developers do not care about windows at all and probably cannot be convinced to help if there are problems. I don't think any of them even have access to a windows machine.

That being said, CADO polynomial selection wouldn't require building the entire codebase. Make sure to use a windows port of gcc since 64-bit GMP expects a long integer to be 64 bits in size, and guaranteeing this minimizes the chance of silently failing.

No doubt. I've so far had no issues building in the Ubuntu shell--GMP, GMP-ECM, YAFU, sr*sieve, and MSieve all build without any problems. The only restriction at the moment is anything needing a graphical interface or CUDA. For that I would have to start an X server (and such programs are available for Windows, but I've not messed with that yet).

I've got a new top scoring polynomial if anyone wants to try it out in CADO:

Code:

# norm 2.355968e-020 alpha -8.637457 e 1.466e-015 rroots 1
skew: 754584017.56
c0: -786603857710966943446024046537073050775258140796560
c1: -716501273417572080490094680715363638285716
c2: -14270771532982785560852469844318132
c3: 30496873584340105471367757
c4: 36980359740030726
c5: 20420400
Y0: -6177613899761822826426969383677261792977
Y1: 78066467661421482511

It is currently being test-sieved in YAFU along with the current fastest-sieving polynomial.

jasonp · 2017-04-02, 02:52

Oh, one more thing: I am not at all convinced that Msieve can successfully complete a GNFS factorization if the leading algebraic coefficient is negative. It may require just a little tweak in the NFS square root, but I don't think anyone has ever tried it. A negative leading rational coefficient happens quite often for SNFS jobs and works fine.

Max0526 · 2017-04-02, 03:37

Quote:

Originally Posted by Max0526

@firejuggler
Oops! Ignore my previous post. I guess you are asking to optimize

Code:

R0: -6538656944147030901974729281399477396702
R1: 72539914394644909709
A0: -41444190994060695382448148406658444357662062124275
A1: 754844027559316401567668757262830610578795
A2: -264679992220691908321444752075053
A3: -12013706814805249129944703
A4: 198488242366576296
A5: 15371820
skew 282712296.24, size 1.468e-020, alpha -7.436, combined = 1.186e-015 rroots = 3

The jump from 1.186e-15 to > 1.425e-15 (or a CADO optimized 1.451e-15 -- see my March 28th post) seems not very likely.
For the fun of it though, I'll try and let you know.

@firejuggler
CADO optimized it to:

Code:

Y0: -6538656944146178613836326287586977122632
Y1: 72539914394644909709
c0: -197719514184257186206798138711873011660202583925
c1: -39700463745561748598773198332189327404925
c2: -523484939236254115088682176605643
c3: -2664150829814841752156383
c4: 199391277610069296
c5: 15371820
skew: 106302831.98350
# lognorm 65.75, E 59.33, alpha -6.42 (proj -1.92), 3 real roots
# MurphyE=1.21056216e-15

Max0526 · 2017-04-02, 03:54

@firejuggler
No matter what the E score became, you'll have to test-sieve it to really see the difference. Just remember that Msieve can't reproduce it even if you feed it in Msieve directly. It just rolls back to 1.186e-15.

Max0526 · 2017-04-02, 09:03

Quote:

Originally Posted by Max0526

Code:

c0: 46940669866055547823109313162012850262763741523200
c1: 3236905767184422265163991871076044888757900
c2: -800578443717778675552745489973381
c3: -17574786098948226617271999
c4: 8665969938351911
c5: 10155780
Y0: -7103803724224543650738252214965600685669
Y1: 3627703029879009973753
skew: 705844749.41479
E: 1.35647549e-15

Code:

c0: 50608218075941554941592343353365754461981759507263
c1: 1381441172185986964849824511200946637939843
c2: -1233655127349780859186011448195019
c3: -50450709273026749596417827
c4: 77575300139332788
c5: 133553160
Y0: -7087473485773569538658762369110485778080
Y1: 3494915370090810326597
skew: 292023526.43429
E: 1.23478058e-15

Code:

c0: 813773569588275365261968461425817298866674784690768
c1: 3861383057198851187427587436368696332048911
c2: -61631780767810719575743108271687814
c3: -91573071945657692896492335
c4: 671457495195380950
c5: 154701960
Y0: -6984897769444385728403767460772654452734
Y1: 3258137590889412483491
skew: 353529344.18221
E: 9.05441400e-16

Msieve's take on polys from VBCurtis (all polys are transformed):

Code:

# norm 2.104799e-020 alpha -6.658015 e 1.359e-015 rroots 5
skew: 653728307.89
c0: 152122473199295983636801991589543502587672029059885
c1: 2065939264685326615071716076444450219143911
c2: -5338907836886783485739041332629664
c3: -13248646991832026013538963
c4: 13599166427601011
c5: 10155780
Y0: -7103803723872110418607633888809320357862
Y1: 3627703029879009973753

Code:

# norm 2.018394e-020 alpha -7.394290 e 1.321e-015 rroots 5
skew: 249637273.89
c0: 47224726451812136500923160912821561668328131326464
c1: 732304448328496708052991281000286599141136
c2: -3048423320736055926581505207855272
c3: -46367710104427426345123331
c4: 85913740430836188
c5: 133553160
Y0: -7087473485729928275303616403933115197499
Y1: 3494915370090810326597

Code:

# norm 1.383686e-020 alpha -7.957578 e 1.017e-015 rroots 5
skew: 334096838.91
c0: 632082519398461870527638462044076245916733795340600
c1: 2804252757344981202398412601649944411726774
c2: -54468579939517460627086559663484161
c3: -145091571574381551993998935
c4: 655863267672460750
c5: 154701960
Y0: -6984897769510070919326117236844789751093
Y1: 3258137590889412483491

Max0526 · 2017-04-02, 09:28

Quote:

Originally Posted by wombatman

Max, can you point me to the correct place to get the CADO source?

The source in constant progress:

Code:

git clone https://scm.gforge.inria.fr/anonscm/git/cado-nfs/cado-nfs.git

The official releases (e.g., CADO-NFS-2.2.0) are useless, they do not compile a lot of executables by default.
I initially compiled CADO using this link: https://bitbucket.org/cybertools/mal...u-installation
Follow the link above but after

Code:

sudo apt-get install python3

also insert

Code:

sudo apt-get install cmake

Without updating cmake to the latest version CADO usually gets confused and doesn't compile.
Good luck and let me know.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GIMPS wiki account request thread	ixfd64	mersennewiki	169	2018-09-21 05:43
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Lost Prime Raider password request thread	cheesehead	Forum Feedback	6	2009-07-28 13:02
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07
Deutscher Thread (german thread)	TauCeti	NFSNET Discussion	0	2003-12-11 22:12

2017-04-01, 02:01	#808
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	Note that the CADO developers do not care about windows at all and probably cannot be convinced to help if there are problems. I don't think any of them even have access to a windows machine. That being said, CADO polynomial selection wouldn't require building the entire codebase. Make sure to use a windows port of gcc since 64-bit GMP expects a long integer to be 64 bits in size, and guaranteeing this minimizes the chance of silently failing.

2017-04-02, 02:52	#810
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	Oh, one more thing: I am not at all convinced that Msieve can successfully complete a GNFS factorization if the leading algebraic coefficient is negative. It may require just a little tweak in the NFS square root, but I don't think anyone has ever tried it. A negative leading rational coefficient happens quite often for SNFS jobs and works fine.

2017-04-02, 03:54	#812
Max0526 "Max" Jun 2016 Toronto 19·47 Posts	@firejuggler No matter what the E score became, you'll have to test-sieve it to really see the difference. Just remember that Msieve can't reproduce it even if you feed it in Msieve directly. It just rolls back to 1.186e-15.