mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-07-15, 02:12   #1
mhill12
 
Jul 2011

610 Posts
Default 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
mhill12 is offline   Reply With Quote
Old 2011-07-15, 02:52   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by mhill12 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-07-15, 03:51   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011110111102 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2011-07-15, 04:55   #4
Andi_HB
 
Andi_HB's Avatar
 
Mar 2007
Germany

23·3·11 Posts
Default

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
Andi_HB is offline   Reply With Quote
Old 2011-07-15, 11:15   #5
mhill12
 
Jul 2011

2·3 Posts
Default

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
mhill12 is offline   Reply With Quote
Old 2011-07-15, 12:21   #6
mhill12
 
Jul 2011

610 Posts
Default

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.
mhill12 is offline   Reply With Quote
Old 2011-07-15, 15:09   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by mhill12 View Post
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]
R.D. Silverman is offline   Reply With Quote
Old 2012-09-26, 03:23   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by wblipp View Post
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 View Post
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 View Post
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
Dubslow is offline   Reply With Quote
Old 2012-09-26, 03:44   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Default

Quote:
Originally Posted by Dubslow View Post
...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!
Batalov is offline   Reply With Quote
Old 2012-09-26, 03:51   #10
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
Dubslow is offline   Reply With Quote
Old 2012-09-26, 05:24   #11
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

22·3·5·53 Posts
Smile

Should we also re-visit the power-halving technique?

(I'm partly serious about this question for the newbies.)
RichD is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial selection Max0526 NFS@Home 9 2017-05-20 08:57
msieve 1.52 with GPU polynomial selection cgy606 Msieve 16 2016-10-06 14:16
2^877-1 polynomial selection fivemack Factoring 47 2009-06-16 00:24
Polynomial selection CRGreathouse Factoring 2 2009-05-25 07:55
Homogeneous Cunningham snfs poly selection? nuggetprime Factoring 22 2008-08-15 10:01

All times are UTC. The time now is 08:38.

Thu Dec 3 08:38:42 UTC 2020 up 4:50, 0 users, load averages: 1.17, 1.13, 1.08

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.