mersenneforum.org SNFS polynomials for k*b^n+-1
 Register FAQ Search Today's Posts Mark Forums Read

 2010-01-08, 06:23 #1 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 3·2,083 Posts SNFS polynomials for k*b^n+-1 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
2010-01-08, 07:38   #2
10metreh

Nov 2008

232210 Posts

Quote:
 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
Code:
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:

Code:
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):

Code:
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.)

Last fiddled with by 10metreh on 2010-01-08 at 07:40

2010-01-08, 08:03   #3
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

Quote:
 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

2010-01-08, 08:40   #4
frmky

Jul 2003
So Cal

22×11×59 Posts

Quote:
 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

2010-01-08, 09:01   #5
10metreh

Nov 2008

44228 Posts

Quote:
 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".

2010-01-08, 18:41   #6
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

186916 Posts

Quote:
 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 Code: 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: Code: 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): Code: 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.

Last fiddled with by mdettweiler on 2010-01-08 at 18:49

2010-01-08, 19:17   #7
10metreh

Nov 2008

1001000100102 Posts

Quote:
 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).

Last fiddled with by 10metreh on 2010-01-08 at 19:18

2010-01-08, 19:57   #8
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

186916 Posts

Quote:
 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:
Code:
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?

2010-01-08, 20:18   #9
Wacky

Jun 2003
The Texas Hill Country

108910 Posts

Quote:
 Originally Posted by mdettweiler if this was, say, 11*2^615+1 instead, would I just change c0 to a positive 1?
YES

2010-01-08, 20:25   #10
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

603110 Posts

Quote:
 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.

2010-01-08, 20:50   #11
10metreh

Nov 2008

1001000100102 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Till Factoring 12 2021-08-04 21:01 fivemack YAFU 22 2012-03-12 18:48 chris2be8 FactorDB 1 2012-03-10 16:49 yemsy Aliquot Sequences 1 2011-02-17 10:25 Orgasmic Troll Puzzles 4 2003-09-16 16:23

All times are UTC. The time now is 13:57.

Sun Jan 29 13:57:47 UTC 2023 up 164 days, 11:26, 0 users, load averages: 1.19, 1.14, 1.08