SNFS Polynomial selection help?

[chris2be8]

Is there a simple rule of thumb for which side to sieve on? In particular does it depend on the skew (GNFS usually has much larger skew that SNFS)? I'm most interested in SNFS jobs where one coefficient is much larger then the others (which coefficient is large varies).

Another question, how does effective difficulty of a SNFS job increase as the coefficients get larger? Is adding the number of digits of the largest coefficient to the SNFS difficulty in the right ballpark?

Chris

[Dubslow]

Originally Posted by chris2be8

Is there a simple rule of thumb for which side to sieve on? In particular does it depend on the skew (GNFS usually has much larger skew that SNFS)? I'm most interested in SNFS jobs where one coefficient is much larger then the others (which coefficient is large varies).

Another question, how does effective difficulty of a SNFS job increase as the coefficients get larger? Is adding the number of digits of the largest coefficient to the SNFS difficulty in the right ballpark?

Chris

ba-dump-bump



SB: You want post #18 repeated?! It is definitely a thing to do, at least once, twice, and then your own experience will start giving you hints. "There is no Royal Road to geometry!" (c)

[chris2be8]

Post 18 isn't a lot of help, I'm factoring lots of small numbers which take an hour or two each. I need something I can test in a script to decide which side to sieve on.And the same goes for deciding which siever to use, large prime bounds, etc.

Chris

[Dubslow]

Originally Posted by Dubslow

ba-dump-bump



SB: You want post #18 repeated?! It is definitely a thing to do, at least once, twice, and then your own experience will start giving you hints. "There is no Royal Road to geometry!" (c)

Originally Posted by chris2be8

Post 18 isn't a lot of help, I'm factoring lots of small numbers which take an hour or two each. I need something I can test in a script to decide which side to sieve on.And the same goes for deciding which siever to use, large prime bounds, etc.

Chris

Trial sieving isn't the answer to everything, especially (e.g.) in Chris' case, where trial sieving takes longer than just doing the damn thing. axn must have some rule of thumb for coming to the conclusion in post 19; I'm curious what his train of thought was, and/or if you happen to know.



On a somewhat different and more on topic, how do you decide if a poly with smaller coeffs but higher difficulty will sieve better or not? And before you say trial sieving, of course, but I'm asking in the context of this little prog I've written for my own convenience:

def opnpoly(k, b, n, c, deg, hi=None):
     # Create an SNFS poly for k*b^n+c with given degree. This is based largely
     # on http://www.mersenneforum.org/showpost.php?p=54606&postcount=39 and
     # http://www.mersenneforum.org/showthread.php?t=15773.
     # Currently it only works for prime b & n, n > 13. (Rather, results are
     # guaranteed to be pseudo-optimal only under those conditions. The code 
     # will work in some other cases, but it might not be the best option. I
     # plan to add in some other cases later.)

     N = k * b**n + c
     out = "c{deg}: {cdeg}\nc0: {c0}\nm: {m}\nskew: {skew}\ntype: snfs\nsize: {size}"

     def low_poly(k, b, n, c, N, deg):      
          # Round down to multiple of deg
          m, cdeg = divmod(n, deg)
          m = b**m
          cdeg = k * b**cdeg
          skew = (abs(c/cdeg))**(1/deg)
          return {'deg': deg, 'cdeg': cdeg, 'c0': c, 'm': m, 'skew': skew, 'size': _len(N)}, max(abs(cdeg), abs(c))

     def hi_poly(k, b, n, c, N, deg):
          # Round up to multiple of deg, increase difficulty
          xtra = ((deg - (n % deg)) % deg)
          N *= b**xtra
          cdeg = k
          c0 = b**xtra * c
          m = b**((n+xtra)//deg)
          skew = (abs(c0/cdeg))**(1/deg)
          return {'deg': deg, 'cdeg': cdeg, 'c0': c0, 'm': m, 'skew': skew, 'size': _len(N)}, max(abs(cdeg), abs(c0))

     if hi is not None and not hi: # User only wants smaller size poly
          print(out.format(**low_poly(k,b,n,c,N,deg)[0]))

     elif hi: # User only wants larger size poly
          print(out.format(**hi_poly(k,b,n,c,N,deg)[0]))

     else: # User wants to let this function decide

          score = [None, None] # Largest algebraic coefficient for each poly
          polys = [None, None]
          polys[0], score[0] = low_poly(k,b,n,c,N,deg)
          polys[1], score[1] = hi_poly(k,b,n,c,N,deg)

          if score[0] <= score[1]:
               print("I recommend the following polynomial:")
               print(out.format(**polys[0]))
          else:
               if _len(b) * xtra > 5: # Rather spurious decision
                    print("Warning: this poly has a significantly larger difficulty than the number",
                          "in question, consider doing some test sieving")
               else:
                    print("I recommend the following polynomial:")
               print(out.format(**polys[1]))

In particular, the last ten lines. There has got to be a better estimate than extra difficulty of 5, since (e.g.) for 53929223^23-1, the lower coeff poly is 16 digits harder, but still sieves faster. I'm asking for others' experience, since mine is limited. (And yes, for this job I did do trial sieving.)

[chris2be8]

I've at last found enough free time to compare yields sieving a few polys on each side.I picked a few polys from factordb that I'm sieving on my old P4 and sieved some of the same range on the other side on an even older P3 (It's normally only used as a CD player). Comparing average yield per special Q I found:
Sextics get better yield on the algebraic side. I got 11% to 26% better yield.
Quartics are better on the rational side. I got from 23% to 68% better yield.
Quintics are slightly better on the rational side. I got 4% better yield.

Note I only tested 3 quartics, 2 quintics and 2 sextics. All around 110-130 digits SNFS difficulty. So YMMV.

If anyone has an explanation for this I would be interested. Is it because with higher degree the coefficients on the rational side are smaller? If so septics and octics would show a bigger gain on the algebraic side.

Chris

[bsquared]

It all comes down to the size of the norms.

To approximate the norms you need your linear and algebraic polynomials and the size of your sieve region. The linear norm is the absolute max of a - mb, where m is the common root (typically Y0) and a,b are the size of the sieve region. For lasieve4I13e, a would be 2^13 and b would be 2^12 (change as appropriate for different sievers). The algebraic norm, assuming a quintic, would be x*a^5 + y*b^5, where a,b are the same as before and x,y are the coefficients of the ^5 term and the ^0 term. Whichever norm is larger is the one you want to sieve special-q on. If you have a choice of several different polynomials, then pick the one that produces norms of approximately the same size (i.e. quartic vs. sextic). If you are stuck with a poly producing norms that are very skewed, then you can try to go to extra lengths to help the factorization on that side, like increase the factor base bounds and/or using 3LP on that side.

[henryzz]

It all depends on the size of the numbers being checked for smoothness. It is generally faster if you sieve on the side that is larger(since you already know a factor).
If you call the algebraic polynomial f(x) and the rational polynomial g(x) then the numbers being factored are b^d*f(a/b) and b*g(a/b).
Higher degrees and to some degree larger coefficients increase the size of the polynomials. Increasing the degree of the algebraic poly will improve the rational poly but make the algebraic poly worse. The size of the numbers involved effects what degree is optimal.
It is possible to work out what the maximum size of b^d*f(a/b) and b*g(a/b) by plugging a and b values into the formula. I just checked a relations file I had lying around and the max a was 1e9 and the max b was 1e6. I don't know whether this is effected by which siever you use.

I will now compare the polys axn listed for 2^648+5
x^5+20 (m=2^130)
f(x) has size 45 and g(x) has size 45.1.
8*x^5+5 (m=2^129)
f(x) has size 45.9 and g(x) has size 44.8.
x^6+5 (m=2^108)
f(x) has size 54 and g(x) has size 38.5.

Looks like degree 5 is probably the way to go with this one sieving on either side. With the degree 6 poly you would want to sieve on the algebraic side. With degree 4 the rational side.

Unfortunately size isn't the only factor playing a part. Some polys are smoother for some reason. I think this is measured by the alpha value in msieve.

[jasonp]

Originally Posted by henryzz

Unfortunately size isn't the only factor playing a part. Some polys are smoother for some reason. I think this is measured by the alpha value in msieve.

Correct, alpha is the shorthand for it. Basically it measures how much of an average sieve value is left after small primes are divided out of it. Most SNFS polynomials have bad to terrible alpha, though, because the number fields that lead to such small norms do not behave at all like typical number fields.

[Dubslow]

Originally Posted by bsquared

It all comes down to the size of the norms.

To approximate the norms you need your linear and algebraic polynomials and the size of your sieve region. The linear norm is the absolute max of a - mb, where m is the common root (typically Y0) and a,b are the size of the sieve region. For lasieve4I13e, a would be 2^13 and b would be 2^12 (change as appropriate for different sievers). The algebraic norm, assuming a quintic, would be x*a^5 + y*b^5, where a,b are the same as before and x,y are the coefficients of the ^5 term and the ^0 term. Whichever norm is larger is the one you want to sieve special-q on. If you have a choice of several different polynomials, then pick the one that produces norms of approximately the same size (i.e. quartic vs. sextic). If you are stuck with a poly producing norms that are very skewed, then you can try to go to extra lengths to help the factorization on that side, like increase the factor base bounds and/or using 3LP on that side.

Originally Posted by henryzz

It all depends on the size of the numbers being checked for smoothness. It is generally faster if you sieve on the side that is larger(since you already know a factor).
If you call the algebraic polynomial f(x) and the rational polynomial g(x) then the numbers being factored are b^d*f(a/b) and b*g(a/b).
Higher degrees and to some degree larger coefficients increase the size of the polynomials. Increasing the degree of the algebraic poly will improve the rational poly but make the algebraic poly worse. The size of the numbers involved effects what degree is optimal.
It is possible to work out what the maximum size of b^d*f(a/b) and b*g(a/b) by plugging a and b values into the formula. I just checked a relations file I had lying around and the max a was 1e9 and the max b was 1e6. I don't know whether this is effected by which siever you use.

I will now compare the polys axn listed for 2^648+5
x^5+20 (m=2^130)
f(x) has size 45 and g(x) has size 45.1.
8*x^5+5 (m=2^129)
f(x) has size 45.9 and g(x) has size 44.8.
x^6+5 (m=2^108)
f(x) has size 54 and g(x) has size 38.5.

Looks like degree 5 is probably the way to go with this one sieving on either side. With the degree 6 poly you would want to sieve on the algebraic side. With degree 4 the rational side.

Unfortunately size isn't the only factor playing a part. Some polys are smoother for some reason. I think this is measured by the alpha value in msieve.

Originally Posted by jasonp

Correct, alpha is the shorthand for it. Basically it measures how much of an average sieve value is left after small primes are divided out of it. Most SNFS polynomials have bad to terrible alpha, though, because the number fields that lead to such small norms do not behave at all like typical number fields.

Has anyone written a program to do these sorts of analysis on SNFS polys? How hard is it to determine the alpha of a poly? What's akruppa's "phi" program that chris2be8 rcv mentioned in the Brent thread? Is the source available somewhere? Thanks guys!

[jasonp]

Msieve does all the analysis to any SNFS polynomial you give it, with the proviso that you really cannot compare Murphy E values for different-degree polynomials.

The general function that does the analysis is analyze_poly, in gnfs/poly/polyutil.c; note that it has many many dependencies.

[chris2be8]

Originally Posted by jasonp

Msieve does all the analysis to any SNFS polynomial you give it, with the proviso that you really cannot compare Murphy E values for different-degree polynomials.

Thanks for all the advice. But I'll still have to work out a rule of thumb for deciding which poly would be best, a lot of the comparisons are different degrees.

Chris