20220712, 21:01  #1 
Sep 2008
Kansas
2·3^{2}·5·41 Posts 
Two similar numbers  wildly different yields
I have another p^231 which is suitable for NFS@Home but the yield is considerably different than a slightly larger one.
The number which has completed is in this post and also follows: Code:
n: 2196446137359053106938322843888526731641085452277355711119901549757077396118238170925287354800180824402178087712112553739977989723468961792365780938151711139319035812841928902047665717382284057567 # 52379047267^231, difficulty: 257.26, skewness: 61.17, alpha: 0.00 # cost: 1.43877e+19, est. time: 6851.28 GHz days (not accurate yet!) lss: 0 skew: 61.168 c6: 1 c0: 52379047267 Y1: 1 Y0: 7527146673760832665395038537255591018765521 type: snfs rlim: 134000000 alim: 134000000 lpbr: 31 lpba: 31 mfbr: 62 mfba: 91 rlambda: 2.7 alambda: 3.6 Code:
Q Yield 14M 8868 20M 9647 60M 7604 100M 6984 200M 4142 260M 4380 Code:
n: 95762446665416432170528779345395824617298589397987483122654389932343133315377477092638183533144546212459348448670021407038663095177050772862772947910846739945799330028390139540028329920329782966910366356039 # 50390258557^231, difficulty: 256.86, skewness: 60.77, alpha: 0.00 # cost: 1.39583e+19, est. time: 6646.81 GHz days (not accurate yet!) lss: 0 skew: 60.775 c6: 1 c0: 50390258557 Y1: 1 Y0: 6447425715227054820320179466380378521618001 type: snfs rlim: 134000000 alim: 134000000 lpbr: 31 lpba: 31 mfbr: 62 mfba: 91 rlambda: 2.7 alambda: 3.6 Code:
Q Yield 20M 5844 60M 100M 3021 
20220712, 22:37  #2 
Apr 2020
2·3·11·13 Posts 
The two polynomials have very different root properties  in other words, the algebraic norms of the first polynomial are much likelier to have lots of small factors, increasing the probability that they are smooth and can result in relations.
Both polys are of the form x^6k, so the algebraic norms are a^6kb^6. A prime p divides a^6kb^6 iff (a/b)^6 == k (mod p). [note: if b is 0 mod p then a would also have to be 0 mod p, but a and b are always coprime, so we don't have to worry about division by 0] So we are interested in the number of 6th roots of k modulo p. In order for any to exist, k must be a square and a cube mod p. Note your k values are both large primes so for our purposes k will not be 0 mod p. The probability that k is a square mod p will always be 1/2 (for p > 2). If it is a square, it has exactly two square roots. If p is 2 mod 3, then everything is a cube mod p, since 3 is coprime to p1 which is the order of the multiplicative group mod p, and so x > x^3 is a bijection mod p. Then with probability 1/2, k is a square and it has two 6th roots: the cube roots of its two square roots. Otherwise k is not a square and has no 6th roots. If p is 1 mod 3, then 3 divides the order of the multiplicative group mod p, and so only a third of the elements are cubes; each has three distinct cube roots. If k is a square mod p (probability 1/2), then with probability 1/3 it is also a cube, and each of its square roots must also be cubes, giving 6 sixth roots. So k has 6 sixth roots with probability 1/6, and no sixth roots with probability 5/6. The quality of the poly is therefore largely determined by how many small primes of the form 1 mod 3 there are for which k happens to have a full set of 6 sixth roots, giving these primes a high chance of appearing as factors of the algebraic norm. Primes of the form 2 mod 3 also have an effect but it is smaller. Your first poly (k=52379047267) is incredibly lucky. Of the 11 primes of the form 1 mod 3 below 100, it has a full set of 6 sixth roots mod 7, 13, 31, 61, 67 and 97  more than half of them, even though the probability for each p is only 1/6. It's like rolling 11 dice and getting 6 sixes. The second poly (k=50390258557) only has the full set of roots for p=31. There is less of a difference in luck for primes of the form 2 mod 3, but as explained above, this is not as important: the 1 mod 3 primes are enough to account for almost all the difference in sieving performance. If you run these polys through msieve you will see that the first poly has a much better alpha value, reflecting its exceptional root properties. Last fiddled with by charybdis on 20220712 at 22:43 
20220713, 15:47  #3 
Sep 2009
2394_{10} Posts 
Having a script to do that:
First poly: msieve rating: skew 61.17, size 2.730e13, alpha 2.577, combined = 4.752e14 rroots = 2 Second poly: msieve rating: skew 60.77, size 9.310e14, alpha 1.358, combined = 2.200e14 rroots = 2 Note that lower alpha is better while higher combined (escore) is better. And the yield usually scales roughly with the escore. 
20220714, 23:19  #4 
Sep 2008
Kansas
7152_{8} Posts 
Thank you for the detailed description of the properties of the sieve. I am still digesting the comprehensive write up. As with most SNFS polynomials (especially large coefficients) there is very little leeway for alternatives. This particular number (among others) will require more ECM to justify the higher equivalent difficulty.

20220715, 11:53  #5 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
13557_{8} Posts 
Are there any possible compensations that can be done for a polynomial like this? Would composite special qs including one or more of the rare small primes(plus a larger prime?) be a possible option?

20220715, 13:57  #6  
Apr 2020
2×3×11×13 Posts 
Quote:
The only thing I can think of is that the algebraic side is effectively larger for the worse poly and so the parameters should maybe be skewed a bit more in that direction. And let's not forget that the second poly isn't horrendously bad; it's only made to appear that way by the first poly being so outrageously lucky. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Yields with 16e  fivemack  Factoring  1  20200419 13:45 
Zero/low yields in KF siever @~67M (badsched bug)  Batalov  Factoring  38  20150209 07:57 
Curtis and similar GPU build  Manpowre  GPU Computing  80  20130914 06:35 
M(57885161) yields no primitive trinomial over GF(2)  ewmayer  Computer Science & Computational Number Theory  5  20130606 02:50 
Wildly differing times for step 2 with ecm6.0.1  Jushi  GMPECM  7  20050912 01:30 