20140516, 03:30  #1 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·3·353 Posts 
29 to 30 bit large prime SNFS crossover
Conclusion: SNFS213 is a bit faster using 30bit 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 29bit large primes require more relations than ~200 difficulty projects; say, 46M raw relations instead of 4143M. I decided to try running a pair of samesize factorizations with 29 and 30 bit large primes, to compare sieve time. 5*2^7021: SNFS213 diffficulty, 29bit large primes, sextic poly Escore 4.47e12. factmsieve runs with 300k blocks of specialq, and needed 46.8M raw relations, 40.6M unique to build a density70 matrix of size 4.7M. Specialq from 8.9M to 29.3M were sieved. 13*2^7021: SNFS213 difficulty, 30bit large primes, sextic poly score 4.27e12. factmsieve built a matrix the first try with 76.5M raw relations, 69.2M unique to build a density70 matrix of size 5.3M. Specialq 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 specialq blocks, which took about 5% longer in wallclock time compared to the 30bit project. However, the 30bit 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 Escores, but the better Escore took the same time as a 29bit project as the lower one did with 30bit primes. I already factored 13*2^7071 with 29bit primes; I'll do 13*2^7061 and 5*2^7061 as 30bit 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 20140516 at 03:33 
20140516, 07:09  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
6,353 Posts 
I do this fairly constantly for GNFS as I work through aliquot sequences.
It looks as if 2829 is at about C148, 2930 is at about C153, and 3031 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:
CPUhours 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 20140516 at 07:09 
20140516, 07:18  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
6,353 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) Last fiddled with by fivemack on 20140516 at 07:19 
20140516, 13:07  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
2×5×569 Posts 
Extrapolating from those numbers C163 3132 and C168 3233. Does this mean when we do a 180+ digit number our large prime bounds are much too small?

20140516, 15:17  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
6,353 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.

20140516, 16:40  #6 
Apr 2010
2^{2}·5·7 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 
20140516, 22:04  #7  
"Curtis"
Feb 2005
Riverside, CA
2^{2}×3×353 Posts 
Quote:
Thank you for the data and confirmation. 

20140518, 21:48  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
6353_{10} 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 largeprime bounds than I'd previously considered  if you're careful about limits, 28bit LP seems worthwhile as small as C115.

20140519, 04:28  #9 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·3·353 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 28293031 LP bounds, and likewise the points to move to 13e14e15e sievers. I'll play with 13e vs 14e with these new LP bounds myself, but would appreciate if others post their findings also. 
20140519, 22:20  #10 
(loop (#_fork))
Feb 2006
Cambridge, England
6,353 Posts 
Here, for a random C124 with Murphy score 1.77e10, 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 27 101870.2275 11905078 10430364 14715990 fail 28 121324.1423 13759598 11864512 15749318 fail 29 140607.982 15538550 13213233 16632104 fail 210 159487.2929 17218204 14465025 17381742 fail 211 178047.7998 18849180 15663145 18044872 1051033 4 29 204011.4358 21658907 18547562 20149112 879637 28.5 189501.4654 20339028 17534519 19671448 975442 28 174845.7571 18978238 16478927 19137617 fail 39 177762.3 18430231 16338414 19131390 fail 6 39 216706.984 20554991 18272260 20173211 1018070 38.5 197834.5111 18989740 17003043 19563723 fail 8 38.5 220669.0495 19632466 17601209 19902924 1178651 38 198166.9867 17846588 too slow even if it worked Last fiddled with by fivemack on 20140519 at 22:27 
20140523, 21:51  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
18D1_{16} Posts 
I can get the sieving time down to 166k seconds with 13e, 29bit large primes, alim=4000000, sieve 1.5M4M for 27.9M relations.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
QS/NFS crossover points  bsquared  Factoring  24  20160125 05:09 
SNFS poly for b^n1, n prime?  ryanp  Factoring  6  20130719 17:23 
Advice for large SNFS jobs?  ryanp  Factoring  69  20130430 00:28 
Large Prime Variation of QS  Sam Kennedy  Factoring  9  20121218 17:30 
32/33 and 15e/16e crossover point  fivemack  Factoring  7  20090421 07:59 