mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > NFS@Home

Reply
 
Thread Tools
Old 2022-07-12, 21:01   #1
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

2·32·5·41 Posts
Default 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?
RichD is offline   Reply With Quote
Old 2022-07-12, 22:37   #2
charybdis
 
charybdis's Avatar
 
Apr 2020

2·3·11·13 Posts
Default

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
charybdis is offline   Reply With Quote
Old 2022-07-13, 15:47   #3
chris2be8
 
chris2be8's Avatar
 
Sep 2009

239410 Posts
Default

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.
chris2be8 is offline   Reply With Quote
Old 2022-07-14, 23:19   #4
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

71528 Posts
Default

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.
RichD is offline   Reply With Quote
Old 2022-07-15, 11:53   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

135578 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2022-07-15, 13:57   #6
charybdis
 
charybdis's Avatar
 
Apr 2020

2×3×11×13 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Yields with 16e fivemack Factoring 1 2020-04-19 13:45
Zero/low yields in KF siever @~67M (badsched bug) Batalov Factoring 38 2015-02-09 07:57
Curtis and similar GPU build Manpowre GPU Computing 80 2013-09-14 06:35
M(57885161) yields no primitive trinomial over GF(2) ewmayer Computer Science & Computational Number Theory 5 2013-06-06 02:50
Wildly differing times for step 2 with ecm-6.0.1 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔