SNFS Polynomial selection help?

[Batalov]

Originally Posted by Dubslow

...interesting. It seems to me, then, that the logical conclusion is that for numbers of the form a^7-1, then ...

Originally Posted by Dubslow

...I have no idea if this is mathematically valid or not, I'm just winging it...

Bill, I wouldn't bother to discuss this at length if it didn't appear that you frequently like to be first to answer any posting no matter how correct. As you put it, winging it.

You wrote that your intuition tells you that (x^7-1)/(x-1) = x^6+x^5+x^4+x^3+x^2+x+1 as the logical conclusion from learning that (x^5-1)/(x-1) = x^4+x^3+x^2+x+1. No need for intuition here! This is factually correct. (and I got punched in the face by C.O. for even typing that, just now)

...However, the full sentence is incorrect.
"The logical conclusion is that for numbers of the form a^7-1, then the sextic (when sextic is preferred over quintic) polynomial should be c6: 1, c5: 1, c4: 1, c3: 1, c2: 1, c1: 1, c0: 1, with m: a." The condition that you applied is extraneous.

An important take-home message in the context of SNFS, though, is that a reducible polynomial is never going to work; the correct implementation of NFS will not accept it. (e.g. x^5-1, or, say, x^4+4) The siever will not sieve. When we reshuffle the polynomial to be irreducible (e.g. x^6-C, by way of selecting other value for m), then the method will accept it -- but it will be slower than the divided-out polynomial even if in an awkward degree. Let alone degree 6 that has very wide range of useability for SNFS.

If you can divide the algebraic part, you should, as long as a poly of reasonable degree (or even degree 8! rarely; search the forum for examples) will result. This is true for most reductions (3, 5, 7, 11, 13, 15, 21, Aurifeuillian, Aurifeuillian*3, etc).

The interesting caveat is when a polynomial is reducible in more than one way, e.g. x^35-1 (by dividing away x^7-1 or x^5-1; but you cannot do both -- without getting an unusable poly, that is) -- that is where some testing needs to be done to compare which one going to be fastest. In different size ranges one will beat the other.

[RichD]

Many years ago Alex had a nice write up in his post.

[jcrombie]

For completeness, somebody should mention the mersennewiki page.

[Dubslow]

Originally Posted by Batalov

Bill, I wouldn't bother to discuss this at length if it didn't appear that you frequently like to be first to answer any posting no matter how correct. As you put it, winging it.

Well see, I have no idea if it's correct or not, which is why I post so that someone can confirm or (more often) deny that. See, I want you (or someone) to discuss this at length -- that's how I learn. Everything I know about NFS has been learned on this forum.

Originally Posted by Batalov

You wrote that your intuition tells you that (x^7-1)/(x-1) = x^6+x^5+x^4+x^3+x^2+x+1 as the logical conclusion from learning that (x^5-1)/(x-1) = x^4+x^3+x^2+x+1. No need for intuition here! This is factually correct. (and I got punched in the face by C.O. for even typing that, just now)

...However, the full sentence is incorrect.
"The logical conclusion is that for numbers of the form a^7-1, then the sextic (when sextic is preferred over quintic) polynomial should be c6: 1, c5: 1, c4: 1, c3: 1, c2: 1, c1: 1, c0: 1, with m: a." The condition that you applied is extraneous.

Thus proving that my intuition wasn't (completely) correct, like wblipp pointed out the first time. Based on what I had learned up to the point I posted that (derived largely from the paper RDS mentions earlier in this thread), you pick out the target degree and then try and make a proper poly. I had no idea that in SNFS, unlike GNFS, the degree is a bit more flexible with what works best. (At least that's what I surmise from the rest of your post.) Additionally, all the examples in RDS' paper are with large exponents, so that none of them divided out the algebraic factor (in hindsight, with your/akruppa's help, I see that that's a result of using a prime exponent -- the polynomial one winds up making doesn't have the algebraic factor, while for small prime exponent you can directly make a poly of the right degree rather than some slight finagling to get the degree small, and without the finagling the algebraic factor is still there [and with composite exponents, like you/akruppa describe, there is an algebraic factor one has to divide out]).

Originally Posted by Batalov

An important take-home message in the context of SNFS, though, is that a reducible polynomial is never going to work; the correct implementation of NFS will not accept it. (e.g. x^5-1, or, say, x^4+4) The siever will not sieve. When we reshuffle the polynomial to be irreducible (e.g. x^6-C, by way of selecting other value for m), then the method will accept it -- but it will be slower than the divided-out polynomial even if in an awkward degree. Let alone degree 6 that has very wide range of useability for SNFS.

If you can divide the algebraic part, you should, as long as a poly of reasonable degree (or even degree 8! rarely; search the forum for examples) will result. This is true for most reductions (3, 5, 7, 11, 13, 15, 21, Aurifeuillian, Aurifeuillian*3, etc).

The interesting caveat is when a polynomial is reducible in more than one way, e.g. x^35-1 (by dividing away x^7-1 or x^5-1; but you cannot do both -- without getting an unusable poly, that is) -- that is where some testing needs to be done to compare which one going to be fastest. In different size ranges one will beat the other.

This is the sort of information-goldmine I wouldn't get without making stupid (to you) posts. So, like I said before, thanks! (You can imagine that with as little or as much sarcasm as you like -- I do truly mean it, but I can't help but imagine it at least slightly sarcastically )

Originally Posted by RichD

Many years ago Alex had a nice write up in his post.

Originally Posted by jcrombie

For completeness, somebody should mention the mersennewiki page.

Many thanks! I had seen the Wiki page before (which now looks like it's more or less a copy/paste of akruppa's post), but at the time I was more overwhelmed rather than informed. Alex's post, and thus the article, start with the assumption that you already know the idea behind a polynomial -- I didn't. The first two sentences are the only attempts to provide that basis, and without an example (and due to my lack of experience with any sort of number theory/moduli) they didn't really help. When I went through RDS' paper, and its worked example(s), is when it started to click (and as you can see by my recent posting history, the clicking has taken a while ).

[Batalov]

How was the exam?

[swishzzz]

For something like 2^648+5 (snfs 196), would a degree 5 or a degree 6 polynomial be better? I've heard that the switch between degree 5 and degree 6 GNFS is somewhere up in 205-210 digits, but the trade-off here is between having smaller coefficients for the degree 6 polynomial versus having a degree 5 polynomial, which usually sieves faster for numbers of this size.

[Batalov]

The best answer will be given by small-scale trial sieving.

Several notes:
- construct both polys
- determine ballpark lims, and other params - from experience ...or by running factMsieve.pl on the poly, killing and taking hints from the .job files (note that in job files on e of the lims will be lowered by script; restore it to the other lim, add to the bottom of poly file)
- sieve both candidates from the lim with -c 10000 on both sides
- you may see that sextic will sieve better on one side, and quintic on the other
- Compare the better of each pair
- time permitting, sieve some more, e.g. in four or five 10000 regions
- collate, analyze

The same recipe can be used on several gnfs top polys (for sizeable jobs, when it matters)

[axn]

Originally Posted by swishzzz

For something like 2^648+5 (snfs 196), would a degree 5 or a degree 6 polynomial be better? I've heard that the switch between degree 5 and degree 6 GNFS is somewhere up in 205-210 digits, but the trade-off here is between having smaller coefficients for the degree 6 polynomial versus having a degree 5 polynomial, which usually sieves faster for numbers of this size.

The obvious polys are x^5+20 (m=2^130), 8*x^5+5 (m=2^129), and x^6+5 (m=2^108). None of them have "large" coefficients. The degree 5's should be sieved on rational side, while degree 6 should probably be sieved on algebraic side.

If I were to guess, the first poly would be the best (with possibly a larger than normal skew). But, for a job this large, definitely follow Batalov's advice.

[Dubslow]

Originally Posted by axn

The degree 5's should be sieved on rational side, while degree 6 should probably be sieved on algebraic side.

How do you figure that?

[xilman]

Originally Posted by swishzzz

For something like 2^648+5 (snfs 196), would a degree 5 or a degree 6 polynomial be better? I've heard that the switch between degree 5 and degree 6 GNFS is somewhere up in 205-210 digits, but the trade-off here is between having smaller coefficients for the degree 6 polynomial versus having a degree 5 polynomial, which usually sieves faster for numbers of this size.

I'm currently working my way through quite a few SNFS in the 200-210 range. Trial sieving convinced me that quintics are almost always better so I no longer bother using anything else. As each one takes only a few days sieving, the hassle involved in attempting to save a couple of hours computation really isn't worth it.

When the current batch is finished and the 210-220 batch is started I'll revisit the choices.

[chris2be8]

Originally Posted by jcrombie

For completeness, somebody should mention the mersennewiki page.

That should say that for a^13k-1 you get:
f(x)=x^6+x^5-5x^4-4x^3+6x^2+3x-1

Chris