20201018, 23:35  #1 
Apr 2020
107 Posts 
NFS cofactorization with 3LP
When sieving with 2 large primes, one tends to find that the optimal value of mfb is slightly less than 2*lpb. Presumably this is because a composite cofactor close to 2^(2*lpb) is unlikely to split into two primes that are both smaller than 2^lpb. For example, for lpb=32 the optimum value of mfb with CADONFS appears to be 60.
Similarly, when sieving with 3 large primes, the optimum value of mfb is slightly less than 3*lpb. However, what happens if we get a cofactor that is just below 2^(2*lpb)? Such a cofactor is still unlikely to contribute to a relation: as in the 2LP case, it is probably not the product of two primes both smaller than 2^lpb, and it will also be too small to be the product of three large primes. So again it should make sense to set a double large prime bound smaller than 2^(2*lpb). Neither GGNFS nor CADO appear to have an option to set a double large prime bound separately from mfb when using 3LP. Does anyone here know what is actually done? Is a value computed automatically, perhaps from the mfb given? 
20201018, 23:56  #2 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·1,097 Posts 
I've wondered about this also, though my curiosity was about cofactors slightly bigger than 2*mfb but still too small to possibly split into 3 large primes.

20201019, 00:05  #3  
Apr 2020
107 Posts 
Quote:
Code:
nd = mpz_get_d (n); B = (double) scs.lim; kB = B * B; for (klpb = lpb; klpb < s; klpb += lpb, kB *= B) { /* invariant: klpb = k * lpb, kB = B^(k+1) */ if (nd < kB) /* L^k < n < B^(k+1) */ return 0; } 

20201019, 00:33  #4 
Apr 2020
107 Posts 
Should have realised that I could just search in a relations file to find an answer to my question
Here's one from a job with lim1=175M, lpb1=32, mfb1=90: 178218979181,5545:2,b,fb,445,3b21,3c47b,166eeb,b38e5f,c2091937:3,3,3,5,71,89,265,9e3f5,c5a6b,451d0b,1c9c589,45458a5,f085ca3b,fb78b42f That's two large 32bit prime factors on the algebraic side, so the cofactor wasn't far off 2^64. It sure looks like CADO is just using a bound of 2^(2*lpb). It feels like there could be a decent speedup from setting the 2LP bound separately in this situation, and I'd be surprised if noone had thought of this before, so is there some reason why this wouldn't actually work in practice? 
20201019, 02:36  #5 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·1,097 Posts 
Well, standard practice for 2LP side is to use mfb of 2* lpb, or 2 * lpb1. We're the weird ones using very nonstandard settings for our params files. Take a look at the factory params files for, say, C130145 to see what I mean.
So, it would not surprise me that nobody thought to do what you're suggesting. Edit: I don't speak code well enough to answer my own question: Could you just modify that formula above to exclude, say, 64bit cofactors when LP = 32? Just that one change should provide a fair bit of speedup. Last fiddled with by VBCurtis on 20201019 at 02:38 
20201019, 18:59  #6  
Apr 2020
107 Posts 
Quote:
Of course, I wouldn't like having to recompile every time I change the bounds, so if this experiment isn't a complete failure I'll get in contact with the authors. Last fiddled with by charybdis on 20201019 at 19:01 
