Parameter explorations for CADO 165-170 digits - Page 2

charybdis · 2020-05-19, 02:22

For what it's worth, here are the 95^128+1 factors:

Code:

p61 factor: 6257613858583898709261755903084673553330399368418555296798721
p109 factor: 8402352391630827885506737623084809472170424349385439829494702478551900066063207448078203277908726932399787521

I've submitted these to cownoise and factordb - not sure if there's anywhere else they should be sent.

chris2be8 · 2020-05-19, 15:57

cownoise and factordb are the only places I would submit it to.

Thanks for the factors.

Chris

charybdis · 2020-06-28, 16:38

One more data point: the c169 from 9+8_638M.

Parameters were

Code:

tasks.I = 14
tasks.qmin = 7000000
tasks.lim0 = 50000000
tasks.lim1 = 70000000
tasks.lpb0 = 31
tasks.lpb1 = 31
tasks.sieve.mfb0 = 58
tasks.sieve.mfb1 = 58
tasks.sieve.ncurves0 = 20
tasks.sieve.ncurves1 = 25

Sieving took 21.6M CPU-seconds for 170M relations; max Q was ~138.6M. 165M relations did not built a matrix at TD=100.

Code:

Sun Jun 28 15:03:04 2020  Msieve v. 1.54 (SVN 1030M)
Sun Jun 28 15:03:04 2020  random seeds: 020987c2 2e14909e
Sun Jun 28 15:03:04 2020  factoring 6323148101178192997454526289605277170954218433278054116052056166051527590848248128865718264727023155963463084305589386151325042874693217587179972005266685135356161079181 (169 digits)
Sun Jun 28 15:03:05 2020  searching for 15-digit factors
Sun Jun 28 15:03:05 2020  commencing number field sieve (169-digit input)
Sun Jun 28 15:03:05 2020  R0: -424000671411315695105034591696768
Sun Jun 28 15:03:05 2020  R1: 72112096043794064331337
Sun Jun 28 15:03:05 2020  A0: 24834769717672015656695526227332911290885
Sun Jun 28 15:03:05 2020  A1: 20316186393429687042949998116877192
Sun Jun 28 15:03:05 2020  A2: -1818007152430589614430877325
Sun Jun 28 15:03:05 2020  A3: -200551169527456827261
Sun Jun 28 15:03:05 2020  A4: 8997719941109
Sun Jun 28 15:03:05 2020  A5: 459900
Sun Jun 28 15:03:05 2020  skew 1.00, size 1.828e-16, alpha -6.733, combined = 1.955e-15 rroots = 5
Sun Jun 28 15:03:05 2020  
Sun Jun 28 15:03:05 2020  commencing relation filtering
Sun Jun 28 15:03:05 2020  setting max relations to 170000000
Sun Jun 28 15:03:05 2020  setting target matrix density to 100.0
Sun Jun 28 15:03:05 2020  estimated available RAM is 15845.9 MB
Sun Jun 28 15:03:05 2020  commencing duplicate removal, pass 1
...
Sun Jun 28 15:19:16 2020  found 49673476 hash collisions in 169989969 relations
Sun Jun 28 15:19:16 2020  commencing duplicate removal, pass 2
Sun Jun 28 15:22:21 2020  found 65292334 duplicates and 104697635 unique relations
Sun Jun 28 15:22:21 2020  memory use: 1321.5 MB
Sun Jun 28 15:22:21 2020  reading ideals above 136511488
Sun Jun 28 15:22:21 2020  commencing singleton removal, initial pass
Sun Jun 28 15:29:47 2020  memory use: 2756.0 MB
Sun Jun 28 15:29:48 2020  reading all ideals from disk
Sun Jun 28 15:29:52 2020  memory use: 1584.8 MB
Sun Jun 28 15:29:54 2020  commencing in-memory singleton removal
Sun Jun 28 15:29:56 2020  begin with 104697635 relations and 98408402 unique ideals
Sun Jun 28 15:30:11 2020  reduce to 41074643 relations and 24856975 ideals in 15 passes
Sun Jun 28 15:30:12 2020  max relations containing the same ideal: 21
Sun Jun 28 15:30:14 2020  reading ideals above 720000
Sun Jun 28 15:30:14 2020  commencing singleton removal, initial pass
Sun Jun 28 15:35:16 2020  memory use: 753.0 MB
Sun Jun 28 15:35:17 2020  reading all ideals from disk
Sun Jun 28 15:35:18 2020  memory use: 1560.4 MB
Sun Jun 28 15:35:20 2020  keeping 39923650 ideals with weight <= 200, target excess is 224283
Sun Jun 28 15:35:23 2020  commencing in-memory singleton removal
Sun Jun 28 15:35:25 2020  begin with 41074647 relations and 39923650 unique ideals
Sun Jun 28 15:36:03 2020  reduce to 39865811 relations and 38709614 ideals in 16 passes
Sun Jun 28 15:36:03 2020  max relations containing the same ideal: 200
Sun Jun 28 15:36:16 2020  removing 3404962 relations and 3004962 ideals in 400000 cliques
Sun Jun 28 15:36:17 2020  commencing in-memory singleton removal
Sun Jun 28 15:36:19 2020  begin with 36460849 relations and 38709614 unique ideals
Sun Jun 28 15:36:36 2020  reduce to 36261732 relations and 35502896 ideals in 8 passes
Sun Jun 28 15:36:36 2020  max relations containing the same ideal: 192
Sun Jun 28 15:36:49 2020  removing 2549850 relations and 2149850 ideals in 400000 cliques
Sun Jun 28 15:36:50 2020  commencing in-memory singleton removal
Sun Jun 28 15:36:52 2020  begin with 33711882 relations and 35502896 unique ideals
Sun Jun 28 15:37:09 2020  reduce to 33582756 relations and 33222484 ideals in 9 passes
Sun Jun 28 15:37:09 2020  max relations containing the same ideal: 184
Sun Jun 28 15:37:21 2020  removing 725709 relations and 625606 ideals in 100103 cliques
Sun Jun 28 15:37:21 2020  commencing in-memory singleton removal
Sun Jun 28 15:37:23 2020  begin with 32857047 relations and 33222484 unique ideals
Sun Jun 28 15:37:36 2020  reduce to 32846772 relations and 32586570 ideals in 7 passes
Sun Jun 28 15:37:36 2020  max relations containing the same ideal: 181
Sun Jun 28 15:37:42 2020  relations with 0 large ideals: 757
Sun Jun 28 15:37:42 2020  relations with 1 large ideals: 797
Sun Jun 28 15:37:42 2020  relations with 2 large ideals: 13803
Sun Jun 28 15:37:42 2020  relations with 3 large ideals: 143045
Sun Jun 28 15:37:42 2020  relations with 4 large ideals: 826045
Sun Jun 28 15:37:42 2020  relations with 5 large ideals: 2883247
Sun Jun 28 15:37:42 2020  relations with 6 large ideals: 6400583
Sun Jun 28 15:37:42 2020  relations with 7+ large ideals: 22578495
Sun Jun 28 15:37:42 2020  commencing 2-way merge
Sun Jun 28 15:37:58 2020  reduce to 20116382 relation sets and 19856180 unique ideals
Sun Jun 28 15:37:58 2020  commencing full merge
Sun Jun 28 15:42:35 2020  memory use: 2417.9 MB
Sun Jun 28 15:42:36 2020  found 9692453 cycles, need 9672380
Sun Jun 28 15:42:38 2020  weight of 9672380 cycles is about 967669235 (100.04/cycle)
Sun Jun 28 15:42:38 2020  distribution of cycle lengths:
Sun Jun 28 15:42:38 2020  1 relations: 733278
Sun Jun 28 15:42:38 2020  2 relations: 915189
Sun Jun 28 15:42:38 2020  3 relations: 994301
Sun Jun 28 15:42:38 2020  4 relations: 930915
Sun Jun 28 15:42:38 2020  5 relations: 871603
Sun Jun 28 15:42:38 2020  6 relations: 780528
Sun Jun 28 15:42:38 2020  7 relations: 688823
Sun Jun 28 15:42:38 2020  8 relations: 597770
Sun Jun 28 15:42:38 2020  9 relations: 523494
Sun Jun 28 15:42:38 2020  10+ relations: 2636479
Sun Jun 28 15:42:38 2020  heaviest cycle: 28 relations
Sun Jun 28 15:42:39 2020  commencing cycle optimization
Sun Jun 28 15:42:52 2020  start with 69254191 relations
Sun Jun 28 15:44:19 2020  pruned 2098869 relations
Sun Jun 28 15:44:19 2020  memory use: 2077.5 MB
Sun Jun 28 15:44:20 2020  distribution of cycle lengths:
Sun Jun 28 15:44:20 2020  1 relations: 733278
Sun Jun 28 15:44:20 2020  2 relations: 937882
Sun Jun 28 15:44:20 2020  3 relations: 1033609
Sun Jun 28 15:44:20 2020  4 relations: 959962
Sun Jun 28 15:44:20 2020  5 relations: 899206
Sun Jun 28 15:44:20 2020  6 relations: 796546
Sun Jun 28 15:44:20 2020  7 relations: 700849
Sun Jun 28 15:44:20 2020  8 relations: 603393
Sun Jun 28 15:44:20 2020  9 relations: 524575
Sun Jun 28 15:44:20 2020  10+ relations: 2483080
Sun Jun 28 15:44:20 2020  heaviest cycle: 28 relations
Sun Jun 28 15:44:34 2020  RelProcTime: 2489
Sun Jun 28 15:44:37 2020  
Sun Jun 28 15:44:37 2020  commencing linear algebra
Sun Jun 28 15:44:37 2020  read 9672380 cycles
Sun Jun 28 15:44:52 2020  cycles contain 32650243 unique relations
Sun Jun 28 15:48:25 2020  read 32650243 relations
Sun Jun 28 15:49:03 2020  using 20 quadratic characters above 4294917295
Sun Jun 28 15:51:08 2020  building initial matrix
Sun Jun 28 15:56:02 2020  memory use: 4429.8 MB
Sun Jun 28 15:56:44 2020  read 9672380 cycles
Sun Jun 28 15:56:45 2020  matrix is 9672203 x 9672380 (3951.6 MB) with weight 1209714091 (125.07/col)
Sun Jun 28 15:56:45 2020  sparse part has weight 919819428 (95.10/col)
Sun Jun 28 15:57:58 2020  filtering completed in 2 passes
Sun Jun 28 15:57:59 2020  matrix is 9671585 x 9671762 (3951.6 MB) with weight 1209689275 (125.07/col)
Sun Jun 28 15:57:59 2020  sparse part has weight 919814498 (95.10/col)
Sun Jun 28 15:58:46 2020  matrix starts at (0, 0)
Sun Jun 28 15:58:48 2020  matrix is 9671585 x 9671762 (3951.6 MB) with weight 1209689275 (125.07/col)
Sun Jun 28 15:58:48 2020  sparse part has weight 919814498 (95.10/col)
Sun Jun 28 15:58:48 2020  saving the first 48 matrix rows for later
Sun Jun 28 15:58:49 2020  matrix includes 64 packed rows
Sun Jun 28 15:58:50 2020  matrix is 9671537 x 9671762 (3832.6 MB) with weight 1013022612 (104.74/col)
Sun Jun 28 15:58:50 2020  sparse part has weight 907971208 (93.88/col)
Sun Jun 28 15:58:50 2020  using block size 8192 and superblock size 884736 for processor cache size 9216 kB
Sun Jun 28 15:59:14 2020  commencing Lanczos iteration (6 threads)
Sun Jun 28 15:59:14 2020  memory use: 3620.3 MB
Sun Jun 28 15:59:34 2020  linear algebra at 0.0%, ETA 33h29m

31/31 is probably a little slower for sieving than 31/32, though not by a large enough margin to rule out further testing - might be worth playing around with the mfb bounds, for example?

chris2be8 · 2020-06-28, 19:00

I've decided to do 86^131-1 via NFS@Home. I've found the following poly (9 hours msieve-gpu searching):

Code:

n: 206291417462093576497275239580773052795596055350565606087502662805051224044201602337850673455835775692863740037805407606265476824913591751307682500480113600344276700606001
# norm 1.306001e-16 alpha -8.871987 e 2.977e-13 rroots 3
skew: 162345250.84
c0: -577062733978460861005241440490749355102976512
c1: -12260826936151352820546357994499780916
c2: 178538325918319471247024945044
c3: 958590300841474414947
c4: -4423011255032
c5: 11844
Y0: -1770910298352749710979419014235215
Y1: 613792628360770487
type: gnfs

The record e-score for 171 digits is 3.730e-13 so this is not too bad for a first try.

If Max could see if he can spin it up I would be very grateful.

Also is anyone interested in 24^179+1 ? If not I'll put it through NFS@Home in a week or so.

Chris

charybdis · 2020-06-29, 01:32

Here are a couple better polys for 86^131-1:

Code:

n: 206291417462093576497275239580773052795596055350565606087502662805051224044201602337850673455835775692863740037805407606265476824913591751307682500480113600344276700606001
skew: 41437836.858
c0: -5389519387337140565345516459794841317758000
c1: -143043284702103460455094028784037830
c2: 2239398228891059427583897507
c3: -889691908139885268641
c4: 3496913201934
c5: 95760
Y0: -1659129166378730128203133792666517
Y1: 1742363546744996502291193
# e 3.392e-13

n: 206291417462093576497275239580773052795596055350565606087502662805051224044201602337850673455835775692863740037805407606265476824913591751307682500480113600344276700606001
skew: 3357702.047
c0: -112975106982991917173660977635799247400
c1: 111002282144221726406217931664406
c2: -64145260501719297021407541
c3: -30825474695526305746
c4: 4452459053820
c5: 543690
Y0: -823750842791353826106062726508889
Y1: 34863622316774006451893
# e 3.334e-13

Quote:

Originally Posted by chris2be8

Also is anyone interested in 24^179+1 ? If not I'll put it through NFS@Home in a week or so.

I'll do it.

VBCurtis · 2021-05-10, 02:31

Bur requested a 165 params file, so I attach a draft here.

If you use this file, please report:
1. Did filtering work the first time, or did CADO bounce back and forth between filtering and sieving? If filtering ran multiple times, how many relations were needed for sieving to finish?
2. What was the final-Q sieved?
3. What was the matrix size, in dimensions or "total weight"?

I'm still not sure if 3LP is useful in 165-170 digit range; CADO uses 3 large primes starting at 145 or 150 digits in the default files, so I ought to explore it. One of these days....

bur · 2021-05-10, 06:06

Ok, I started the factorization. I think final q and the matrix properties can be looked up in the log file?

Should I have cado do the linear algebra or doesn't it matter?

VBCurtis · 2021-05-10, 14:35

Doesn't matter whether msieve or cado does the matrix; I use matrix size as a marker for whether target_relations was set too high or too low.

Final Q can be found in the log, though it's not in the summary. It's easiest to find by scrolling up on the terminal window to find the last Q sieved before filtering.

bur · 2021-05-10, 17:18

Currently sieving ETA is already saturday, 15th, but it usually increased significantly after a while. I report back once the factorization is finished.

bur · 2021-05-17, 06:36

LA is still running, but everything seems to have gone fine:

1) the initial 220,000,000 relations were enough, no going back to sieving after the first filtering
2) last q-range was 66,450,000-66,460,000
3) Merged matrix has 5579102 rows and total weight 836915933 (150.0 entries per row on average)

ETA for krylov is 8 hours from now, mksol will also take a while but I expect a total of less than 8 days. That's fast compared to the ~75 hours a C153 and a C154 took on the same machine.

And a question: How do number of relations, matrix weight/density and time for LA depend on each other?

From some posts it seems to me that having more relations allows for a matrix with higher density and those will result in shorte LA times. Is it like that? So increasing target_density will increase the number of required relations but decrease LA time?

VBCurtis · 2021-05-17, 12:14

Having more available relations allows filtering to work harder, generating a smaller matrix. Setting target density higher explicitly tells filtering to work harder, but even holding target density fixed you'll get a smaller matrix from more relations.

The catch is that it usually takes more time to gather those extra relations than one saves in LA phase. There's a productive amount of oversieving- when one is right at the cusp of building a matrix, a small number of extra relations has a fairly strong effect on matrix size, but diminishing returns sets in rather quickly.

My previous GGNFS/msieve jobs around C165 have had matrices around 9M in size, so this job was rather strongly oversieved. We should cut rels_wanted to 210M for this file and see what matrix comes out.

If you are interested in seeing the effect of the extra relations, zcat all your 220M relations out to a single file, and run msieve's filtering on the file to see what size matrix comes out. Then, restrict the number of relations msieve uses (via a filtering flag, see the -h option list for msieve) to 215, 210, 205 and let us know what size matrices pop out. I suggest a TD of 100 or so for msieve, but you might enjoy trying 100/110/120 on the full dataset to see how target_density affects matrix size.

tasks.qmin can be changed down to 10M. I target a qmin-to-qmax ratio of 7 to 8; your final-Q of 66.5M suggests the chosen qmin of 17M was a little high. Smaller Q sieve faster but yield more duplicate relations, so changing tasks.qmin to 10M should make jobs run a little bit faster because 10-17M will produce more relations (and faster) than 59-66M. Since this job ran faster than expected (based on your ~155 digit experience) and Q is smaller than I expected, you may have found a lucky poly for this job.

Thanks for your data report!

2020-05-19, 02:22	#12
charybdis Apr 2020 2×5²×19 Posts	For what it's worth, here are the 95^128+1 factors: Code: p61 factor: 6257613858583898709261755903084673553330399368418555296798721 p109 factor: 8402352391630827885506737623084809472170424349385439829494702478551900066063207448078203277908726932399787521 I've submitted these to cownoise and factordb - not sure if there's anywhere else they should be sent.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Some CADO-NFS Work At Around 175-180 Decimal Digits	EdH	CADO-NFS	127	2020-10-07 01:47
Sigma parameter in ecm	storm5510	Information & Answers	4	2019-11-30 21:32
PrimeNet error 7: Invalid parameter	ksteczk	PrimeNet	6	2018-03-26 15:11
Parameter Underestimation	R.D. Silverman	Cunningham Tables	14	2010-09-29 19:56
ECM Work and Parameter Choices	R.D. Silverman	Cunningham Tables	11	2006-03-06 18:46

2020-05-19, 15:57	#13
chris2be8 Sep 2009 2³×5×61 Posts	cownoise and factordb are the only places I would submit it to. Thanks for the factors. Chris

2021-05-10, 06:06	#18
bur Aug 2020 796581e-4;32539e-3 1322₈ Posts	Ok, I started the factorization. I think final q and the matrix properties can be looked up in the log file? Should I have cado do the linear algebra or doesn't it matter?

2021-05-10, 14:35	#19
VBCurtis "Curtis" Feb 2005 Riverside, CA 5725₁₀ Posts	Doesn't matter whether msieve or cado does the matrix; I use matrix size as a marker for whether target_relations was set too high or too low. Final Q can be found in the log, though it's not in the summary. It's easiest to find by scrolling up on the terminal window to find the last Q sieved before filtering.

2021-05-10, 17:18	#20
bur Aug 2020 796581e-4;32539e-3 2·19² Posts	Currently sieving ETA is already saturday, 15th, but it usually increased significantly after a while. I report back once the factorization is finished.

2021-05-17, 06:36	#21
bur Aug 2020 796581e-4;32539e-3 1322₈ Posts	LA is still running, but everything seems to have gone fine: 1) the initial 220,000,000 relations were enough, no going back to sieving after the first filtering 2) last q-range was 66,450,000-66,460,000 3) Merged matrix has 5579102 rows and total weight 836915933 (150.0 entries per row on average) ETA for krylov is 8 hours from now, mksol will also take a while but I expect a total of less than 8 days. That's fast compared to the ~75 hours a C153 and a C154 took on the same machine. And a question: How do number of relations, matrix weight/density and time for LA depend on each other? From some posts it seems to me that having more relations allows for a matrix with higher density and those will result in shorte LA times. Is it like that? So increasing target_density will increase the number of required relations but decrease LA time?

2021-05-17, 12:14	#22
VBCurtis "Curtis" Feb 2005 Riverside, CA 5²·229 Posts	Having more available relations allows filtering to work harder, generating a smaller matrix. Setting target density higher explicitly tells filtering to work harder, but even holding target density fixed you'll get a smaller matrix from more relations. The catch is that it usually takes more time to gather those extra relations than one saves in LA phase. There's a productive amount of oversieving- when one is right at the cusp of building a matrix, a small number of extra relations has a fairly strong effect on matrix size, but diminishing returns sets in rather quickly. My previous GGNFS/msieve jobs around C165 have had matrices around 9M in size, so this job was rather strongly oversieved. We should cut rels_wanted to 210M for this file and see what matrix comes out. If you are interested in seeing the effect of the extra relations, zcat all your 220M relations out to a single file, and run msieve's filtering on the file to see what size matrix comes out. Then, restrict the number of relations msieve uses (via a filtering flag, see the -h option list for msieve) to 215, 210, 205 and let us know what size matrices pop out. I suggest a TD of 100 or so for msieve, but you might enjoy trying 100/110/120 on the full dataset to see how target_density affects matrix size. tasks.qmin can be changed down to 10M. I target a qmin-to-qmax ratio of 7 to 8; your final-Q of 66.5M suggests the chosen qmin of 17M was a little high. Smaller Q sieve faster but yield more duplicate relations, so changing tasks.qmin to 10M should make jobs run a little bit faster because 10-17M will produce more relations (and faster) than 59-66M. Since this job ran faster than expected (based on your ~155 digit experience) and Q is smaller than I expected, you may have found a lucky poly for this job. Thanks for your data report!