SNFS polynomials for k*b^n+-1

[mdettweiler]

Is there a straightforward way to produce an SNFS polynomial for a number of the form k*b^n+-1? These threads in the Sierpinski/Riesel base 5 forum touched on the subject a bit, but I couldn't make heads or tails of the various discussions in there about producing SNFS polynomials. Ditto for the mersennewiki article on the subject.

What I'm trying to do is take a whack at factoring one of the numbers from the k*2^n+-1 factorization project, many of which seem quite well suited for quick SNFS jobs. Unfortunately, my experience with SNFS factorizations is limited to running pre-generated .poly files from the near-repdigit project, which has a really neat little system that lets it automatically generate SNFS polynomials for its composites. Obviously, then, there is some sort of straightforward method for doing this, and it can be implemented as a completely automated program; I just haven't been able to find a clear description of it anywhere or this forum, or by searching the GGNFS mailing list archives.

Any help on this would be greatly appreciated.

Max

[10metreh]

Originally Posted by mdettweiler

Is there a straightforward way to produce an SNFS polynomial for a number of the form k*b^n+-1? These threads in the Sierpinski/Riesel base 5 forum touched on the subject a bit, but I couldn't make heads or tails of the various discussions in there about producing SNFS polynomials. Ditto for the mersennewiki article on the subject.

What I'm trying to do is take a whack at factoring one of the numbers from the k*2^n+-1 factorization project, many of which seem quite well suited for quick SNFS jobs. Unfortunately, my experience with SNFS factorizations is limited to running pre-generated .poly files from the near-repdigit project, which has a really neat little system that lets it automatically generate SNFS polynomials for its composites. Obviously, then, there is some sort of straightforward method for doing this, and it can be implemented as a completely automated program; I just haven't been able to find a clear description of it anywhere or this forum, or by searching the GGNFS mailing list archives.

Any help on this would be greatly appreciated.

Max

It depends on the number. The rational and algebraic polynomials must have a common root modulo N, whatever the number. I don't think these numbers have algebraic factorizations (and I may be mistaken), so it's actually easier. For instance, for the c137 from 15*2^556-1, 556 is divisible by 4, so you could have the polynomial

n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131
c4: 15
c0: -1
Y1: 1
Y0: -696898287454081973172991196020261297061888 [=2^139]
skew:
type: snfs

You could also have this, because 15*2^556-1 = 30*2^555-1:

n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131
c5: 30
c0: -1
Y1: 1
Y0: -2596148429267413814265248164610048 [=2^111]
skew:
type: snfs

Or this, where the SNFS is actually done on 60*2^558-4, which is 4*(15*2^556-1):

n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131
c6: 60
c0: -4
Y1: 1
Y0: -9903520314283042199192993792 [=2^93]
skew:
type: snfs

Test all three polynomials with skew: 1, and then take the best, test a few different skews and take the best of those.

(Mods, if I've missed something out, feel free to delete this post.)

[smh]

Originally Posted by 10metreh

Test all three polynomials with skew: 1, and then take the best, test a few different skews and take the best of those.

Correct me if I'm wrong, but I think the skew for these numbers should be:

(1/15)^0.25 = 0.508
(1/30)^0.2 = 0.506
(4/60)^0.1667 = 0.637

[frmky]

Originally Posted by 10metreh

60*2^558-4, which is 4*(15*2^556-1):

A minor correction: 4*(15*2^556-1) = 15*2^558-4

[10metreh]

Originally Posted by frmky

A minor correction: 4*(15*2^556-1) = 15*2^558-4

*grrrr* - change c6: 60 to c6: 15 and change "I am mentally healthy" to "I am mentally ill".

[mdettweiler]

Originally Posted by 10metreh

It depends on the number. The rational and algebraic polynomials must have a common root modulo N, whatever the number. I don't think these numbers have algebraic factorizations (and I may be mistaken), so it's actually easier. For instance, for the c137 from 15*2^556-1, 556 is divisible by 4, so you could have the polynomial

n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131
c4: 15
c0: -1
Y1: 1
Y0: -696898287454081973172991196020261297061888 [=2^139]
skew:
type: snfs

You could also have this, because 15*2^556-1 = 30*2^555-1:

n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131
c5: 30
c0: -1
Y1: 1
Y0: -2596148429267413814265248164610048 [=2^111]
skew:
type: snfs

Or this, where the SNFS is actually done on 60*2^558-4, which is 4*(15*2^556-1):

n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131
c6: 60
c0: -4
Y1: 1
Y0: -9903520314283042199192993792 [=2^93]
skew:
type: snfs

Test all three polynomials with skew: 1, and then take the best, test a few different skews and take the best of those.

(Mods, if I've missed something out, feel free to delete this post.)

Pardon my stupidity, but what exactly do you mean by "common root modulo N"? I found a lot of info on "primitive root mod n" via Google, but that didn't seem to apply here since, if I'm understanding this correctly, I would need to find a primitive root of 15 to check c4 in the first polynomial, except that one apparently doesn't exist for 15.

Meanwhile, I'll take a whack at those polynomials you provided--thanks! Edit: Looks like the degree 5 one was the best. The degree 6 one was slightly worse, and the degree 4 was abysmal.

[10metreh]

Originally Posted by mdettweiler

Pardon my stupidity, but what exactly do you mean by "common root modulo N"?

Basically, when the polynomials (rational and algebraic) are calculated for a certain number m (it doesn't matter what this is), they are both equivalent to 0 (mod N), i.e. they are either 0, N or a multiple of N. For the degree 5 polynomial, m = 2^111: 30*(2^111)^5-1 = 15*2^556-1 which is by definition a multiple of n, and m-2^111 = 0 (obviously).

[mdettweiler]

Originally Posted by 10metreh

Basically, when the polynomials (rational and algebraic) are calculated for a certain number m (it doesn't matter what this is), they are both equivalent to 0 (mod N), i.e. they are either 0, N or a multiple of N. For the degree 5 polynomial, m = 2^111: 30*(2^111)^5-1 = 15*2^556-1 which is by definition a multiple of n, and m-2^111 = 0 (obviously).

Aha! That makes sense now. Based on that, I was able to construct a degree 5 polynomial for another similar number, 11*2^615-1:

n: 283347805802003574336187887292901565896290554119953391779442063930786753840404759101112572581306469631045937977931652075948816049919521359133958052805321
c5: 11
c0: -1
Y1: 1
Y0: -10633823966279326983230456482242756608
skew: 1
type: snfs

This polynomial was accepted by factMsieve.pl and produced relations at a rate of 0.01975 sec/rel--which seems within normal range.

Thanks for all the help! I think I've got a pretty good idea now of how this works. Just one last question though: if this was, say, 11*2^615+1 instead, would I just change c0 to a positive 1?

[Wacky]

Originally Posted by mdettweiler

if this was, say, 11*2^615+1 instead, would I just change c0 to a positive 1?

YES

[henryzz]

Originally Posted by mdettweiler

Thanks for all the help! I think I've got a pretty good idea now of how this works. Just one last question though: if this was, say, 11*2^615+1 instead, would I just change c0 to a positive 1?

yes
the way i think about it is:
the number being factored = c5*m^5+c4*m^4+c3*m^3+c2*m^2+c1*m^1+c0 for a degree 5 poly
and the rational poly is almost always 1*m-m for snfs polys
you can add a multiplier to the number being factored to give it better properties that often outway the fact you are factoring a larger number
AFAIK smaller leading coefficients(c5 for degree 5, c6 for degree 6 etc) tend to sieve faster. This is a weakness in factoring riesel numbers as you often end up with the k in the leading coefficient. I would always compare you best snfs poly to a very quick gnfs poly as some numbers are just not suited to snfs.

[10metreh]

Originally Posted by mdettweiler

This polynomial was accepted by factMsieve.pl and produced relations at a rate of 0.01975 sec/rel--which seems within normal range.

Bear in mind that when "lpbr" and "lpba" increase by 1, the speed of relation-finding doubles, but so does the number of relations needed (roughly). This means that, for instance, when you are doing GNFSs with factMsieve.pl, c98s always have a much faster sec/rel than c97, but take longer because they need twice as many relations: c97-c98 is the default crossover from lpbr/a=25 to lpbr/a=26.