mersenneforum.org > YAFU Yafu SNFS difficulty calculation
 Register FAQ Search Today's Posts Mark Forums Read

 2021-02-16, 06:07 #1 jyb     Aug 2005 Seattle, WA 24×107 Posts Yafu SNFS difficulty calculation Can anybody help me understand the values Yafu is claiming for the difficulty in this example? Code: n: 401721424383720426137324949508336187045848565417289917430550907056665790265814883369879394476169080075318675151956526421358049691930517872710129161972339727160629599769770122149882863 # 7^307+6^307, difficulty: 260.29, anorm: 1.30e+037, rnorm: 1.27e+049 # scaled difficulty: 262.29, suggest sieving rational side # size = 1.218e-012, alpha = 0.000, combined = 1.324e-013, rroots = 0 type: snfs size: 260 skew: 0.9746 c6: 7 c0: 6 Y1: -4849687664788584363858837602739217760256 Y0: 12589255298531885026341962383987545444758743 ... The actual SNFS difficulty given by these polynomials is 259.445, according to every definition of SNFS difficulty that I've ever seen. So what are "difficulty", "scaled difficulty" and "size" (the second one) supposed to represent here?
2021-02-16, 14:55   #2
bsquared

"Ben"
Feb 2007

D6E16 Posts

Quote:
 Originally Posted by jyb Can anybody help me understand the values Yafu is claiming for the difficulty in this example? Code: n: 401721424383720426137324949508336187045848565417289917430550907056665790265814883369879394476169080075318675151956526421358049691930517872710129161972339727160629599769770122149882863 # 7^307+6^307, difficulty: 260.29, anorm: 1.30e+037, rnorm: 1.27e+049 # scaled difficulty: 262.29, suggest sieving rational side # size = 1.218e-012, alpha = 0.000, combined = 1.324e-013, rroots = 0 type: snfs size: 260 skew: 0.9746 c6: 7 c0: 6 Y1: -4849687664788584363858837602739217760256 Y0: 12589255298531885026341962383987545444758743 ... The actual SNFS difficulty given by these polynomials is 259.445, according to every definition of SNFS difficulty that I've ever seen. So what are "difficulty", "scaled difficulty" and "size" (the second one) supposed to represent here?

Difficulty is computed in the normal way, except here it looks like I may have included the contribution of the leading coefficient twice. Thanks for that report. As for scaled difficulty, quoting here from the code:

Quote:
 Originally Posted by snfs.c // poly degrees yielding very unbalanced norms are less desirable for sieving. // reflect this by scaling the difficulty of these polys. Since special-q can // bring the norm down on one side or another (at the expense of the other side), // we add one to the difficulty for every order of magnitude imbalance beyond 6 // between the two sides (until we figure out something more accurate)
i.e., it's an attempt to call attention to polynomials that are very unbalanced (of undesirable degree). If the scaled difficulty is sufficiently bigger than the normal difficulty, yafu will try to compensate by increasing the factor base, large prime bounds, and trial factoring bounds. This happens in skew_snfs_params(). Looks like the scaled difficulty needs to be at least 4 bigger than normal (corresponding to 24 orders of magnitude difference in norms) before any parameters are altered.

Size is rounded difficulty. IIRC ggnfs doesn't use size for anything.

p.s.
I'm happy to consider alternatives if you have any suggestions! As indicated above, scaled difficulty was a mix of numerology and experience from back when I was actively performing snfs work.

Last fiddled with by bsquared on 2021-02-16 at 15:08 Reason: more details

2021-02-16, 18:08   #3
charybdis

Apr 2020

23×3×11 Posts

Quote:
 Originally Posted by jyb Code: anorm: 1.30e+037, rnorm: 1.27e+049
These are a bit small, especially anorm; the code uses a = 1e6*sqrt(skew), b=1e6/sqrt(skew) which might work well for small jobs but for numbers this large 1e6 is a big underestimate.

Really it should be something like a = sqrt(2^(2I-1)*Q*skew)*const, b = sqrt(2^(2I-1)*Q/skew)*const where Q is a realistic average special-q; smaller a and b give more relations so const should maybe be around 0.2? Not sure how it would be best to code this, given that the scaled difficulty informs the choice of I and Q. Perhaps use some function of difficulty that's a reasonable approximation of sqrt(2^(2I-1)*Q)?

And really anorm ought to be multiplied by exp(alpha) to account for root properties of the algebraic polynomial, but if you're doing a job large enough that this matters, then you ought to be test-sieving anyway.

2021-02-16, 19:33   #4
bsquared

"Ben"
Feb 2007

2·32·191 Posts

Quote:
 Originally Posted by charybdis ... Not sure how it would be best to code this, given that the scaled difficulty informs the choice of I and Q. Perhaps use some function of difficulty that's a reasonable approximation of sqrt(2^(2I-1)*Q)? ...
Thanks for the suggestions! Using the siever area is simple and straightforward and by itself gets the estimates much closer to actual norm sizes. So I'm tempted to just use
sqrt(2^(2I-1)*1e6*skew) and sqrt(2^(2I-1)*1e6/skew) as I think finer adjustments to Q or using alpha would be in the noise of what this estimate is used for.

 2021-02-24, 16:23 #5 jyb     Aug 2005 Seattle, WA 24·107 Posts Here's another one, though perhaps with the opposite cause. The correct difficulty is 255.99. It looks like in this case Yafu didn't add the leading coefficient at all (255.14 ≈ 245*log_10(11)). Code: n: 7384049810391587250211352363287406947175960642669013845450189424529816242856745368078260733462087073764724231472029401134928725306986130695481851831787933178814661362606610448657133293018573723301486442995118362671069447396748839101553572591556351201 # 11^244+7^244, difficulty: 255.14, anorm: 1.75e+031, rnorm: 1.02e+057 # scaled difficulty: 259.44, suggest sieving rational side # size = 1.944e-017, alpha = 0.000, combined = 7.014e-014, rroots = 1 type: snfs size: 255 skew: 1.0946 c5: 7 c0: 11 Y1: -256923577521058878088611477224235621321607 Y0: 1067189571633593786424240872639621090354383081702091

 Similar Threads Thread Thread Starter Forum Replies Last Post StrongestStrike Factoring 6 2020-09-16 22:40 Alberico Lepore Alberico Lepore 3 2020-04-29 16:28 EdH YAFU 8 2018-03-14 17:22 fivemack Factoring 4 2007-06-30 09:20 Rosenfeld Lounge 16 2004-07-31 22:15

All times are UTC. The time now is 12:53.

Sun May 16 12:53:49 UTC 2021 up 38 days, 7:34, 0 users, load averages: 2.21, 2.37, 2.39