20100108, 06:23  #1 
A Sunny Moo
Aug 2007
USA (GMT5)
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 pregenerated .poly files from the nearrepdigit 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 
20100108, 07:38  #2  
Nov 2008
2×3^{3}×43 Posts 
Quote:
Code:
n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131 c4: 15 c0: 1 Y1: 1 Y0: 696898287454081973172991196020261297061888 [=2^139] skew: type: snfs Code:
n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131 c5: 30 c0: 1 Y1: 1 Y0: 2596148429267413814265248164610048 [=2^111] skew: type: snfs Code:
n: 45947148675353304988805745980911375149866811121831508012183057488121346393001365840176303292481813012944878439690052564665316728832008131 c6: 60 c0: 4 Y1: 1 Y0: 9903520314283042199192993792 [=2^93] skew: type: snfs (Mods, if I've missed something out, feel free to delete this post.) Last fiddled with by 10metreh on 20100108 at 07:40 

20100108, 08:03  #3 
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 

20100108, 08:40  #4 
Jul 2003
So Cal
2×3×349 Posts 

20100108, 09:01  #5 
Nov 2008
2×3^{3}×43 Posts 

20100108, 18:41  #6  
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
Quote:
Meanwhile, I'll take a whack at those polynomials you providedthanks! 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 20100108 at 18:49 

20100108, 19:17  #7 
Nov 2008
100100010010_{2} Posts 
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)^51 = 15*2^5561 which is by definition a multiple of n, and m2^111 = 0 (obviously).
Last fiddled with by 10metreh on 20100108 at 19:18 
20100108, 19:57  #8  
A Sunny Moo
Aug 2007
USA (GMT5)
3×2,083 Posts 
Quote:
Code:
n: 283347805802003574336187887292901565896290554119953391779442063930786753840404759101112572581306469631045937977931652075948816049919521359133958052805321 c5: 11 c0: 1 Y1: 1 Y0: 10633823966279326983230456482242756608 skew: 1 type: snfs 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? 

20100108, 20:18  #9 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 

20100108, 20:25  #10  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011101110_{2} Posts 
Quote:
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*mm 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. 

20100108, 20:50  #11 
Nov 2008
2·3^{3}·43 Posts 
Bear in mind that when "lpbr" and "lpba" increase by 1, the speed of relationfinding 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: c97c98 is the default crossover from lpbr/a=25 to lpbr/a=26.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
QS polynomials  Till  Factoring  5  20180212 16:30 
SNFS polynomials via lindep  fivemack  YAFU  22  20120312 18:48 
SNFS polynomials.  chris2be8  FactorDB  1  20120310 16:49 
orthogonal polynomials  yemsy  Aliquot Sequences  1  20110217 10:25 
Polynomials and Probability  Orgasmic Troll  Puzzles  4  20030916 16:23 