mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-01-08, 06:23   #1
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default 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
mdettweiler is offline   Reply With Quote
Old 2010-01-08, 07:38   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

44228 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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
10metreh is offline   Reply With Quote
Old 2010-01-08, 08:03   #3
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
smh is offline   Reply With Quote
Old 2010-01-08, 08:40   #4
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22×33×19 Posts
Default

Quote:
Originally Posted by 10metreh View Post
60*2^558-4, which is 4*(15*2^556-1):
A minor correction: 4*(15*2^556-1) = 15*2^558-4
frmky is offline   Reply With Quote
Old 2010-01-08, 09:01   #5
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by frmky View Post
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".
10metreh is offline   Reply With Quote
Old 2010-01-08, 18:41   #6
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

141518 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
mdettweiler is offline   Reply With Quote
Old 2010-01-08, 19:17   #7
10metreh
 
10metreh's Avatar
 
Nov 2008

232210 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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
10metreh is offline   Reply With Quote
Old 2010-01-08, 19:57   #8
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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?
mdettweiler is offline   Reply With Quote
Old 2010-01-08, 20:18   #9
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
if this was, say, 11*2^615+1 instead, would I just change c0 to a positive 1?
YES
Wacky is offline   Reply With Quote
Old 2010-01-08, 20:25   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131728 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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.
henryzz is offline   Reply With Quote
Old 2010-01-08, 20:50   #11
10metreh
 
10metreh's Avatar
 
Nov 2008

44228 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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.
10metreh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
QS polynomials Till Factoring 5 2018-02-12 16:30
SNFS polynomials via lindep fivemack YAFU 22 2012-03-12 18:48
SNFS polynomials. chris2be8 FactorDB 1 2012-03-10 16:49
orthogonal polynomials yemsy Aliquot Sequences 1 2011-02-17 10:25
Polynomials and Probability Orgasmic Troll Puzzles 4 2003-09-16 16:23

All times are UTC. The time now is 02:48.

Fri Dec 4 02:48:44 UTC 2020 up 23 hrs, 0 users, load averages: 2.23, 1.73, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.