View Single Post
Old 2021-02-16, 14:55   #2
bsquared's Avatar
Feb 2007

22·859 Posts

Originally Posted by jyb View Post
Can anybody help me understand the values Yafu is claiming for the difficulty in this example?
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:

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.

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
bsquared is offline   Reply With Quote