Improved params files for CADO - Page 3

VBCurtis · 2019-09-26, 04:42

That's a good question! I bet this c140 file would be faster for c145, but not for c150. A ballpark way to adjust from this c140 file is to add ~30% to lim0 and lim1 for each 5 digits bigger, and to add ~40% to P and admax for each 5 digits. I'd also add 1M to rels_wanted for each *digit*.

Those adjustments should give decent performance up to the low 150s.

VBCurtis · 2019-09-27, 21:26

RichD and I each tested the new c140 file this week on c141-142 numbers, and we both had to filter multiple times to build a matrix. This means there wasn't enough oversieving, so I have posted a new file with rels_wanted set to 82M rather than 80M.
That is the only change, so if you already downloaded it you can just change that one setting rather than re-downloading.

VBCurtis · 2019-10-11, 21:16

Ed-
On my i7-5820 (6 core haswell), I once completed a C156 with a modified factmsieve.py in *barely* under 7 days (167 hours). I was quite happy with my modifications, as I think the default factmsieve.py had taken 8.x days for a C155.

The attached CADO params file factored a C155 with leading digit 7 on the same machine in 133 hours. I lack the patience to do a comparison run to the factory params, but the front page of the CADO website cites 5.3 days on 16 cores of 2ghz xeon for RSA-155. 32 ghz * 5.3 days = ~170 ghz-days. My C155 took 6*3.3ghz * 5.5 days = 110 ghz-days.
2.7M thread-seconds sieve, 311k thread-seconds matrix. A bit more poly select than I used would be better, so I added 20% to admax for this attached file versus my actual run.
As usual, if you want to reduce matrix time, add ~5% to rels_wanted.

EdH · 2019-10-12, 02:51

Quote:

Originally Posted by VBCurtis

Ed-
On my i7-5820 (6 core haswell), I once completed a C156 with a modified factmsieve.py in *barely* under 7 days (167 hours). I was quite happy with my modifications, as I think the default factmsieve.py had taken 8.x days for a C155.

The attached CADO params file factored a C155 with leading digit 7 on the same machine in 133 hours. I lack the patience to do a comparison run to the factory params, but the front page of the CADO website cites 5.3 days on 16 cores of 2ghz xeon for RSA-155. 32 ghz * 5.3 days = ~170 ghz-days. My C155 took 6*3.3ghz * 5.5 days = 110 ghz-days.
2.7M thread-seconds sieve, 311k thread-seconds matrix. A bit more poly select than I used would be better, so I added 20% to admax for this attached file versus my actual run.
As usual, if you want to reduce matrix time, add ~5% to rels_wanted.

Thanks! I will be running SNFS run for a little while, but some will rely on this file to fill in the SNFS parameters. Not sure when I'll get back to GNFS, but will keep you posted.

Ferrier · 2019-10-27, 23:39

Quote:

Originally Posted by VBCurtis

Attached are my best effort at parameters for C90, C95, and C100. These files all use Gimarel's excellent development with tight lambda settings near 1.80 combined with loose large-prime bounds and very low Q values.
Timing data: For C90, I ran single-threaded. The stock CADO git-install from Feb '19 took 2236 seconds, while my params took 941 seconds.
For C95 on 6 threads of an otherwise busy 6-core i7-haswell, CADO-default takes 1008 seconds while this params file takes 625 seconds.
For C100 on 6 threads, CADO-default takes 1904 seconds while this params file takes 1288 seconds. Poly-select time should probably be reduced a bit on this file, as I just noticed poly select takes 10% of sieving time.
Running multi-threaded, I believe the YAFU-CADO crossover is somewhere near 90 digits! Please run your own tests and report back here.
Edit 15 Apr: C90 file fixed to comment out the input value N. The c90 file is the one that CADO chose to explain all the parameters, so they included a sample N; I do the same.

tested RSA-100 with your c100 param file (20 threads "Intel(R) Xeon(R) Gold 6136 CPU @ 3.00GHz")

cado-nfs finished in ~324s
yafu(latest trunk version, compilation option: NFS=1 USE_SSE41=1) finished in ~500s

VBCurtis · 2019-10-27, 23:56

Thanks for the report! I'd appreciate a comparison at 94 or 95 digits too; that should be a closer battle.
EDIT: At that size, the close battle should be with the quadratic sieve within YAFU, rather than NFS.

5 minutes to crack a C100 is pretty cool!

Ferrier · 2019-10-29, 04:42

Quote:

Originally Posted by VBCurtis

Thanks for the report! I'd appreciate a comparison at 94 or 95 digits too; that should be a closer battle.
EDIT: At that size, the close battle should be with the quadratic sieve within YAFU, rather than NFS.

5 minutes to crack a C100 is pretty cool!

cado-nfs with default c95 param:

Code:

./cado-nfs.py 48404068520546498995797968938385187958997290617596242601254422967869040251141325866025672337021
...
Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire factorization: 9562.25/269.406

cado-nfs with VBCurtis c95 param:

Code:

./cado-nfs.py 48404068520546498995797968938385187958997290617596242601254422967869040251141325866025672337021
...
Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire factorization: 6511.55/193.041

yafu trunk version (compile option: NFS=1 USE_SSE41=1):

Code:

./yafu 'siqs(48404068520546498995797968938385187958997290617596242601254422967869040251141325866025672337021)'

starting SIQS on c95: 48404068520546498995797968938385187958997290617596242601254422967869040251141325866025672337021

==== sieving in progress (20 threads):   92992 relations needed ====
====            Press ctrl-c to abort and save state            ====
93748 rels found: 24010 full + 69738 from 1277813 partial, (6962.11 rels/sec)

SIQS elapsed time = 206.5399 seconds.
...

yafu wip r379 version (compile option: NFS=1 USE_AVX2=1 SKYLAKEX=1)

Code:

./yafu 'siqs(48404068520546498995797968938385187958997290617596242601254422967869040251141325866025672337021)'

starting SIQS on c95: 48404068520546498995797968938385187958997290617596242601254422967869040251141325866025672337021

==== sieving in progress ( 20 threads):   92992 relations needed ====
====             Press ctrl-c to abort and save state            ====
95438 rels found: 24356 full + 71082 from 1274175 partial, (8081.20 rels/sec)

freeing 1410 poly_a's
building matrix with 95438 columns
SIQS elapsed time = 179.2129 seconds.
...

VBCurtis · 2019-10-29, 05:27

Nice!! So, for non-skylake users, the SIQS/CADO crossover is 93 or 94 digits. For skylake CPUs, more like 96 or 97.

Kudos to BSquared (& co?) for the AVX512 development on YAFU!

bsquared · 2019-10-29, 12:41

Quote:

Originally Posted by VBCurtis

Nice!! So, for non-skylake users, the SIQS/CADO crossover is 93 or 94 digits. For skylake CPUs, more like 96 or 97.

Kudos to BSquared (& co?) for the AVX512 development on YAFU!

Thank you!

Factoring RSA-100 with a two-socket Intel 5122 Gold system (16 threads) I get:

Code:

SIQS elapsed time = 781.4394 seconds.

And for yafu's NFS I get:

Code:

NFS elapsed time = 728.6211 seconds.

Probably a crossover of about 98-99 digits here, but I know that CADO-NFS is faster than yafu's nfs with this number. Unfortunately this system doesn't have python 3 and I can only install in my home directory so I've got a bit of figuring/tinkering to do before I can test it.

VBCurtis · 2019-11-03, 16:47

Post #6 now contains polyselect-optimized params for 190 and 195 digit inputs. The only difference is a slightly smaller P for 190.
User hnoey has run a wide variety of poly select params for a set of 6 C193s, and has determined with some certainty that these choices of NQ and incr produce generally-better results than other common alternatives (incr tested were 60,210,420,4620 with 4620 best; nq tested 3125 15625 78125, with 15625 clearly best). However, no P value was always best; for C193 tests, P=3e6 often was good, but when the poly produced had a score below expectations a higher P-value often produced a more acceptable score.
So, our advice: Use the files as posted, but if score doesn't meet your wishes try again with a doubling of P. These two runs combined would still be shorter than the default CADO suggestion. A halving of P is also a reasonable suggestion.
Cownoise scores for the list of 6 C193s ranged from 1.35e-14 to 1.44e-14.

VBCurtis · 2020-04-05, 04:11

I upgraded my CPU on my home system (was i7-5820k haswell 6x3.3ghz, now Xeon of same era 12x2.5ghz. Same mobo), so I started over at C100 trying to optimize settings.

I managed to crack a C100 in under 6 minutes wall-clock on this single-socket 2013-era system.

This is roughly a 15% improvement on the previous C100 file posted in this thread last year.

Attached is the params file I used.

2019-10-27, 23:56	#28
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Thanks for the report! I'd appreciate a comparison at 94 or 95 digits too; that should be a closer battle. EDIT: At that size, the close battle should be with the quadratic sieve within YAFU, rather than NFS. 5 minutes to crack a C100 is pretty cool! Last fiddled with by VBCurtis on 2019-10-27 at 23:57

2019-11-03, 16:47	#32
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Post #6 now contains polyselect-optimized params for 190 and 195 digit inputs. The only difference is a slightly smaller P for 190. User hnoey has run a wide variety of poly select params for a set of 6 C193s, and has determined with some certainty that these choices of NQ and incr produce generally-better results than other common alternatives (incr tested were 60,210,420,4620 with 4620 best; nq tested 3125 15625 78125, with 15625 clearly best). However, no P value was always best; for C193 tests, P=3e6 often was good, but when the poly produced had a score below expectations a higher P-value often produced a more acceptable score. So, our advice: Use the files as posted, but if score doesn't meet your wishes try again with a doubling of P. These two runs combined would still be shorter than the default CADO suggestion. A halving of P is also a reasonable suggestion. Cownoise scores for the list of 6 C193s ranged from 1.35e-14 to 1.44e-14. Last fiddled with by VBCurtis on 2019-11-03 at 16:51

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Posting log files or other text files	Xyzzy	Forum Feedback	3	2018-12-30 19:37
Improved NFS polynomial selection	jasonp	Operation Kibibit	5	2014-09-07 11:02
CADO-NFS	skan	Information & Answers	1	2013-10-22 07:00
could oddperfect's ecm progress page be improved?	jasong	GMP-ECM	11	2007-05-30 03:08
Factoring progress has really improved!	eepiccolo	Lone Mersenne Hunters	3	2003-04-12 02:04

2019-09-26, 04:42	#23
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	That's a good question! I bet this c140 file would be faster for c145, but not for c150. A ballpark way to adjust from this c140 file is to add ~30% to lim0 and lim1 for each 5 digits bigger, and to add ~40% to P and admax for each 5 digits. I'd also add 1M to rels_wanted for each digit. Those adjustments should give decent performance up to the low 150s.

2019-09-27, 21:26	#24
VBCurtis "Curtis" Feb 2005 Riverside, CA 1001011111101₂ Posts	RichD and I each tested the new c140 file this week on c141-142 numbers, and we both had to filter multiple times to build a matrix. This means there wasn't enough oversieving, so I have posted a new file with rels_wanted set to 82M rather than 80M. That is the only change, so if you already downloaded it you can just change that one setting rather than re-downloading.

2019-10-29, 05:27	#30
VBCurtis "Curtis" Feb 2005 Riverside, CA 12FD₁₆ Posts	Nice!! So, for non-skylake users, the SIQS/CADO crossover is 93 or 94 digits. For skylake CPUs, more like 96 or 97. Kudos to BSquared (& co?) for the AVX512 development on YAFU!