mersenneforum.org SNFS Polynomial selection help?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-07-15, 02:12 #1 mhill12   Jul 2011 2×3 Posts SNFS Polynomial selection help? I am having trouble with writing an SNFS polynomial of the form (381*(3^381)-1)/(2*37*4223). Is it feasable to write a SNFS polynomial, or would GNFS be better? Matt Hill
2011-07-15, 02:52   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by mhill12 I am having trouble with writing an SNFS polynomial of the form (381*(3^381)-1)/(2*37*4223). Is it feasable to write a SNFS polynomial, or would GNFS be better? Matt Hill
This is a C185 with SNFS ---> easy! Just forget about the known
factors.

 2011-07-15, 03:51 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×7×331 Posts Try something like: Code: n: 70660119042903854046516409844370038935302985028064659122643072861070853843136559153244087740059607644464606489303319089200206965812929296697868636129615795714605815617265147516321 c5: 127 c0: -27 Y1: 1 Y0: -5474401089420219382077155933569751763 type: snfs skew: 0.73 ...or 1143*m^5-1, m-3^something, with a large skew, and it is probably better. Or a couple sims with the 6th degree. It is easy. Last fiddled with by Batalov on 2011-07-15 at 04:03
 2011-07-15, 04:55 #4 Andi_HB     Mar 2007 Germany 23·3·11 Posts You can try the snfs poly generator (experiment) from this site http://factorization.ath.cx/index.php This option is new from Syd - more Informations here http://www.mersenneforum.org/showpos...postcount=1128
 2011-07-15, 11:15 #5 mhill12   Jul 2011 2·3 Posts Thanks guys. I am new to SNFS, so I was playing around with the polys. I won't get around to running it for a day or so, until my gnfs C134 finishes. The link is useful too, as I was unsure about where to set the other factors of the search (rlim, alim, etc.) Matt Last fiddled with by mhill12 on 2011-07-15 at 11:24
 2011-07-15, 12:21 #6 mhill12   Jul 2011 2×3 Posts Are there any default guesses for skews, for a deg. 4, 5, and 6 poly of this type? I plan on doing some pretesting first, but I would like to know what skew values are good guesses for the degrees. I plan on testing each poly I have, then narrowing in on the right skew value.
2011-07-15, 15:09   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by mhill12 Are there any default guesses for skews, for a deg. 4, 5, and 6 poly of this type? I plan on doing some pretesting first, but I would like to know what skew values are good guesses for the degrees. I plan on testing each poly I have, then narrowing in on the right skew value.
Read my paper: Optimal Parameter Selection for SNFS, J. Math. Cryptology

Computing the skew is easy. No need to guess.

Let the polynomial be a_n x^n + .... + a_0.
Set the skew to (a_0/a_n)^1/n [or its reciprocal depending on how the
code uses it]

2012-09-26, 03:23   #8
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by wblipp Today I added a C157 to the list in post 209. It would use a quartic. This joins the C171 and C175 not yet claimed. The new number is Code: (2403293005054398937076590802836226619421^5-1)/(5*2403293005054398937076590802836226619420)
Quote:
 Originally Posted by Dubslow Okay, on further thought, I believe this is the correct polynomial (and is quartic): Code: c4: 2403293005054398937076590802836226619421 c0: -1 m: 2403293005054398937076590802836226619421 # This is the same as Y0 == -m and Y1=1, right? skew: 7001670688 If so, then I'll do this when my current reservation is done (and I'll then do the C17*s if they're still available). (PS In case it's not clear, after some reading/thinking I'm pretty sure I can create polys now for most numbers of the form a^b+-1, and possibly other forms if I thought about those. I'd still like to be sure though ) Edit: Is there a way to take advantage of the apparently-larger-than-usual algebraic factor? (Meaning usually it's just a-1, but in this case it looks like b*(a-1).)
Quote:
 Originally Posted by wblipp No. The polynomial you want is x^4+x^3+x^2+x+1. The (x-1) factor of x^5-1 is already divided out.
...interesting. It seems to me, then, that 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?

Last fiddled with by Dubslow on 2012-09-26 at 03:30

2012-09-26, 03:44   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·7·331 Posts

Quote:
 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 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?
Thank you, Capt. Obvious!

2012-09-26, 03:51   #10
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

Quote:
 Originally Posted by Batalov Thank you, Capt. Obvious!
I'm Mjr. learned-how-to-do-this-a-few-hours-ago, and Cnl. wants-to-be-sure-his-intuition-is-correct-to-prevent-future-fsck-ups. (Note this is the "help" thread. Thanks for helping, I suppose.)

Last fiddled with by Dubslow on 2012-09-26 at 03:52

 2012-09-26, 05:24 #11 RichD     Sep 2008 Kansas 1100101011002 Posts Should we also re-visit the power-halving technique? (I'm partly serious about this question for the newbies.)

 Similar Threads Thread Thread Starter Forum Replies Last Post Max0526 NFS@Home 9 2017-05-20 08:57 cgy606 Msieve 16 2016-10-06 14:16 fivemack Factoring 47 2009-06-16 00:24 CRGreathouse Factoring 2 2009-05-25 07:55 nuggetprime Factoring 22 2008-08-15 10:01

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

Wed Jan 27 16:48:42 UTC 2021 up 55 days, 13 hrs, 1 user, load averages: 5.31, 5.15, 5.11