mersenneforum.org Two similar numbers - wildly different yields
 Register FAQ Search Today's Posts Mark Forums Read

 2022-07-12, 21:01 #1 RichD     Sep 2008 Kansas 2·32·5·41 Posts Two similar numbers - wildly different yields I have another p^23-1 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^23-1, 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 Trial sieving 5K blocks. Code:  Q Yield 14M 8868 20M 9647 60M 7604 100M 6984 200M 4142 260M 4380 The next number I have is slightly smaller and I thought I could use the same parameters. Code: n: 95762446665416432170528779345395824617298589397987483122654389932343133315377477092638183533144546212459348448670021407038663095177050772862772947910846739945799330028390139540028329920329782966910366356039 # 50390258557^23-1, 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 Trial sieving 5K blocks. Code:  Q Yield 20M 5844 60M 100M 3021 The sieving yield is about half the first number. If there is a typo I can't find it. Could it be that one "n" is closer to a perfect power than the other? Why is there such a vast variation in the yield?
 2022-07-12, 22:37 #2 charybdis     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^6-k, so the algebraic norms are a^6-kb^6. A prime p divides a^6-kb^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 p-1 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 2022-07-12 at 22:43
 2022-07-13, 15:47 #3 chris2be8     Sep 2009 239410 Posts Having a script to do that: First poly: msieve rating: skew 61.17, size 2.730e-13, alpha -2.577, combined = 4.752e-14 rroots = 2 Second poly: msieve rating: skew 60.77, size 9.310e-14, alpha 1.358, combined = 2.200e-14 rroots = 2 Note that lower alpha is better while higher combined (e-score) is better. And the yield usually scales roughly with the e-score.
 2022-07-14, 23:19 #4 RichD     Sep 2008 Kansas 71528 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.
 2022-07-15, 11:53 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 135578 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?
2022-07-15, 13:57   #6
charybdis

Apr 2020

2×3×11×13 Posts

Quote:
 Originally Posted by henryzz 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?
Don't think composite special-q would help, the number we really want to be smooth is (algebraic norm)/q and that's still not going to have many small prime factors.

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Factoring 1 2020-04-19 13:45 Batalov Factoring 38 2015-02-09 07:57 Manpowre GPU Computing 80 2013-09-14 06:35 ewmayer Computer Science & Computational Number Theory 5 2013-06-06 02:50 Jushi GMP-ECM 7 2005-09-12 01:30

All times are UTC. The time now is 10:28.

Fri Oct 7 10:28:49 UTC 2022 up 50 days, 7:57, 0 users, load averages: 1.20, 1.10, 1.04