29 to 30 bit large prime SNFS crossover

VBCurtis · 2014-05-16, 03:30

Conclusion: SNFS-213 is a bit faster using 30-bit large primes than 29. The default factmsieve cutoff at 225 is too high.

As my SNFS tasks creep over 210 digit difficulty, I find that 29-bit large primes require more relations than ~200 difficulty projects; say, 46M raw relations instead of 41-43M. I decided to try running a pair of same-size factorizations with 29 and 30 bit large primes, to compare sieve time.

5*2^702-1: SNFS-213 diffficulty, 29-bit large primes, sextic poly E-score 4.47e-12. factmsieve runs with 300k blocks of special-q, and needed 46.8M raw relations, 40.6M unique to build a density-70 matrix of size 4.7M. Special-q from 8.9M to 29.3M were sieved.

13*2^702-1: SNFS-213 difficulty, 30-bit large primes, sextic poly score 4.27e-12. factmsieve built a matrix the first try with 76.5M raw relations, 69.2M unique to build a density-70 matrix of size 5.3M. Special-q from 8.9M to 27.5M were sieved. I'll edit my factmsieve to try building a matrix with fewer relations next time, which might save more time.

Despite a poly score 5% higher, the first project had to sieve almost 10% more special-q blocks, which took about 5% longer in wall-clock time compared to the 30-bit project. However, the 30-bit project had a matrix 15% larger, making up that 5% savings in sieve time to solve the matrix.

I don't know how to account for the different E-scores, but the better E-score took the same time as a 29-bit project as the lower one did with 30-bit primes.

I already factored 13*2^707-1 with 29-bit primes; I'll do 13*2^706-1 and 5*2^706-1 as 30-bit projects to see if my results here are a fluke.

Has anyone else compared 29 to 30 bits at SNFS difficulties under 220? Has someone done this for GNFS?

fivemack · 2014-05-16, 07:09

I do this fairly constantly for GNFS as I work through aliquot sequences.

It looks as if 28-29 is at about C148, 29-30 is at about C153, and 30-31 at about C158. But it's a reasonably subtle effect and there's about 10% noise in my measurements simply from sometimes sieving a bit too far. Here are some high tide marks

Code:

CPU-hours  size lp
284.9  C139  29
288.5  C140  29
334.9  C142  29
342.6  C142  29
359.6  C143  29
422.0  C144  29
452.9  C145  29
548.4  C146  29
713.8  C148  30
762.8  C148  29
768.4  C149  30
823.6  C149  29
899.3  C150  30
1038.9 C150  30
1100.6 C152  30
1206.6 C153  30
1341.4 C154  30
2500.2 C157  30
2520.5 C158  31
2538.7 C159  31
3012.6 C161  31
4495.7 C162  31
4906.0 C163  31
11246 C169 30(3a)/15
12619 C170 32
19261 C172 31/15

fivemack · 2014-05-16, 07:18

For SNFS, my data's not as good; I haven't done as many numbers, and I haven't been so careful in noting which computer I used for the sieving.

But:

Code:

diff   lp  time/hrs
204.1  29  441.3
208.3  29  767.3
214.9  30  920.7
216.3  30 1031.2
222.0  30 2459.8 (sieved both A and R)
227.7  30 3494.9
233.2 31r30a 5623.6
248.9  31  18034.3
250.4  31/3r 25997.8 (15e)
285.1  33/3r  166625.8 (16e)

so I think I concur that 29/30 is somewhere around 210 and 30/31 somewhere around 230, and everything gets a bit more confusing as you consider using 3 large primes, different LP bounds on the two sides, and the larger-range sievers at the 250-digit level.

henryzz · 2014-05-16, 13:07

Quote:

Originally Posted by fivemack

It looks as if 28-29 is at about C148, 29-30 is at about C153, and 30-31 at about C158. But it's a reasonably subtle effect and there's about 10% noise in my measurements simply from sometimes sieving a bit too far. Here are some high tide marks

Extrapolating from those numbers C163 31-32 and C168 32-33. Does this mean when we do a 180+ digit number our large prime bounds are much too small?

fivemack · 2014-05-16, 15:17

I honestly don't know. I don't think the optimal large prime bound can possibly grow that fast - but it's quite possible that it does grow that fast if we assume use of the 14e siever, which obviously we're not using as the numbers get huge.

Gimarel · 2014-05-16, 16:40

I use 29 at 120 digits GNFS. It's faster then 28 even with the increased filtering time.

Code:

lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
alambda: 2.55
rlambda: 2.55
alim: 99500000
rlim: 1400000

I start sieving at 1000000 and aim for 18300000 raw relations. Thats enough to build a matrix at target_density 90. The resulting matrix has about 670000 dimensions.

VBCurtis · 2014-05-16, 22:04

Quote:

Originally Posted by fivemack

I do this fairly constantly for GNFS as I work through aliquot sequences.

It looks as if 28-29 is at about C148, 29-30 is at about C153, and 30-31 at about C158.

Looks to me like your data indicates 29-30 at C148 and 30-31 at C158. There are no 28-bit projects listed in the data. That takes care of part of Henry's question!

Thank you for the data and confirmation.

fivemack · 2014-05-18, 21:48

Thanks for suggesting this: I have spent most of the weekend running through various parameter choices on C115, C125, C133, C136 that I had lying around, and am now reckoning that it's worth using significantly larger large-prime bounds than I'd previously considered - if you're careful about limits, 28-bit LP seems worthwhile as small as C115.

VBCurtis · 2014-05-19, 04:28

Does using larger LP bounds shift where the 13e to 14e crossover is? It should move a bit upward, right?

I use the python script for my factoring, but am working on building a list of script edits to post here. Perhaps we can build a 2014 consensus for cutoffs for 28-29-30-31 LP bounds, and likewise the points to move to 13e-14e-15e sievers. I'll play with 13e vs 14e with these new LP bounds myself, but would appreciate if others post their findings also.

fivemack · 2014-05-19, 22:20

Here, for a random C124 with Murphy score 1.77e-10, are some timings for different alim and different ranges. They're really not what I expected: I would have thought that sieving well beyond Q0 was a bad idea.

Code:

alim	Q (with 28/12e)	time	rel		uniq		ideals		matrix
2	2-7	101870.2275	11905078	10430364	14715990	fail
	2-8	121324.1423	13759598	11864512	15749318	fail
	2-9	140607.982	15538550	13213233	16632104	fail
	2-10	159487.2929	17218204	14465025	17381742	fail
	2-11	178047.7998	18849180	15663145	18044872	1051033
4	2-9	204011.4358	21658907	18547562	20149112	879637
	2-8.5	189501.4654	20339028	17534519	19671448	975442
	2-8	174845.7571	18978238	16478927	19137617	fail
	3-9	177762.3	18430231	16338414	19131390	fail
6	3-9	216706.984	20554991	18272260	20173211	1018070
	3-8.5	197834.5111	18989740	17003043	19563723	fail
8	3-8.5	220669.0495	19632466	17601209	19902924	1178651
	3-8	198166.9867	17846588	too slow even if it worked

Currently running similar sorts of things with lpbr=29 and with 13e to see how the numbers compare

fivemack · 2014-05-23, 21:51

I can get the sieving time down to 166k seconds with 13e, 29-bit large primes, alim=4000000, sieve 1.5M-4M for 27.9M relations.

2014-05-16, 03:30	#1
VBCurtis "Curtis" Feb 2005 Riverside, CA 5634₁₀ Posts	29 to 30 bit large prime SNFS crossover Conclusion: SNFS-213 is a bit faster using 30-bit large primes than 29. The default factmsieve cutoff at 225 is too high. As my SNFS tasks creep over 210 digit difficulty, I find that 29-bit large primes require more relations than ~200 difficulty projects; say, 46M raw relations instead of 41-43M. I decided to try running a pair of same-size factorizations with 29 and 30 bit large primes, to compare sieve time. 52^702-1: SNFS-213 diffficulty, 29-bit large primes, sextic poly E-score 4.47e-12. factmsieve runs with 300k blocks of special-q, and needed 46.8M raw relations, 40.6M unique to build a density-70 matrix of size 4.7M. Special-q from 8.9M to 29.3M were sieved. 132^702-1: SNFS-213 difficulty, 30-bit large primes, sextic poly score 4.27e-12. factmsieve built a matrix the first try with 76.5M raw relations, 69.2M unique to build a density-70 matrix of size 5.3M. Special-q from 8.9M to 27.5M were sieved. I'll edit my factmsieve to try building a matrix with fewer relations next time, which might save more time. Despite a poly score 5% higher, the first project had to sieve almost 10% more special-q blocks, which took about 5% longer in wall-clock time compared to the 30-bit project. However, the 30-bit project had a matrix 15% larger, making up that 5% savings in sieve time to solve the matrix. I don't know how to account for the different E-scores, but the better E-score took the same time as a 29-bit project as the lower one did with 30-bit primes. I already factored 132^707-1 with 29-bit primes; I'll do 132^706-1 and 52^706-1 as 30-bit projects to see if my results here are a fluke. Has anyone else compared 29 to 30 bits at SNFS difficulties under 220? Has someone done this for GNFS? Last fiddled with by VBCurtis on 2014-05-16 at 03:33*

2014-05-16, 07:09	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	I do this fairly constantly for GNFS as I work through aliquot sequences. It looks as if 28-29 is at about C148, 29-30 is at about C153, and 30-31 at about C158. But it's a reasonably subtle effect and there's about 10% noise in my measurements simply from sometimes sieving a bit too far. Here are some high tide marks Code: CPU-hours size lp 284.9 C139 29 288.5 C140 29 334.9 C142 29 342.6 C142 29 359.6 C143 29 422.0 C144 29 452.9 C145 29 548.4 C146 29 713.8 C148 30 762.8 C148 29 768.4 C149 30 823.6 C149 29 899.3 C150 30 1038.9 C150 30 1100.6 C152 30 1206.6 C153 30 1341.4 C154 30 2500.2 C157 30 2520.5 C158 31 2538.7 C159 31 3012.6 C161 31 4495.7 C162 31 4906.0 C163 31 11246 C169 30(3a)/15 12619 C170 32 19261 C172 31/15 Last fiddled with by fivemack on 2014-05-16 at 07:09

2014-05-16, 07:18	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	For SNFS, my data's not as good; I haven't done as many numbers, and I haven't been so careful in noting which computer I used for the sieving. But: Code: diff lp time/hrs 204.1 29 441.3 208.3 29 767.3 214.9 30 920.7 216.3 30 1031.2 222.0 30 2459.8 (sieved both A and R) 227.7 30 3494.9 233.2 31r30a 5623.6 248.9 31 18034.3 250.4 31/3r 25997.8 (15e) 285.1 33/3r 166625.8 (16e) so I think I concur that 29/30 is somewhere around 210 and 30/31 somewhere around 230, and everything gets a bit more confusing as you consider using 3 large primes, different LP bounds on the two sides, and the larger-range sievers at the 250-digit level. Last fiddled with by fivemack on 2014-05-16 at 07:19

2014-05-16, 16:40	#6
Gimarel Apr 2010 2³·31 Posts	I use 29 at 120 digits GNFS. It's faster then 28 even with the increased filtering time. Code: lpbr: 29 lpba: 29 mfbr: 58 mfba: 58 alambda: 2.55 rlambda: 2.55 alim: 99500000 rlim: 1400000 I start sieving at 1000000 and aim for 18300000 raw relations. Thats enough to build a matrix at target_density 90. The resulting matrix has about 670000 dimensions.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
QS/NFS crossover points	bsquared	Factoring	67	2022-02-21 01:54
SNFS poly for b^n-1, n prime?	ryanp	Factoring	6	2013-07-19 17:23
Advice for large SNFS jobs?	ryanp	Factoring	69	2013-04-30 00:28
Large Prime Variation of QS	Sam Kennedy	Factoring	9	2012-12-18 17:30
32/33 and 15e/16e crossover point	fivemack	Factoring	7	2009-04-21 07:59

2014-05-16, 15:17	#5
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	I honestly don't know. I don't think the optimal large prime bound can possibly grow that fast - but it's quite possible that it does grow that fast if we assume use of the 14e siever, which obviously we're not using as the numbers get huge.

2014-05-18, 21:48	#8
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	Thanks for suggesting this: I have spent most of the weekend running through various parameter choices on C115, C125, C133, C136 that I had lying around, and am now reckoning that it's worth using significantly larger large-prime bounds than I'd previously considered - if you're careful about limits, 28-bit LP seems worthwhile as small as C115.

2014-05-19, 04:28	#9
VBCurtis "Curtis" Feb 2005 Riverside, CA 2×3²×313 Posts	Does using larger LP bounds shift where the 13e to 14e crossover is? It should move a bit upward, right? I use the python script for my factoring, but am working on building a list of script edits to post here. Perhaps we can build a 2014 consensus for cutoffs for 28-29-30-31 LP bounds, and likewise the points to move to 13e-14e-15e sievers. I'll play with 13e vs 14e with these new LP bounds myself, but would appreciate if others post their findings also.

2014-05-23, 21:51	#11
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100110110₂ Posts	I can get the sieving time down to 166k seconds with 13e, 29-bit large primes, alim=4000000, sieve 1.5M-4M for 27.9M relations.