SNFS Polynomial selection help?

mhill12 · 2011-07-15, 02:12

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

R.D. Silverman · 2011-07-15, 02:52

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.

Batalov · 2011-07-15, 03:51

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.

Andi_HB · 2011-07-15, 04:55

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

mhill12 · 2011-07-15, 11:15

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

mhill12 · 2011-07-15, 12:21

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.

R.D. Silverman · 2011-07-15, 15:09

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]

Dubslow · 2012-09-26, 03:23

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?

Batalov · 2012-09-26, 03:44

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!

Dubslow · 2012-09-26, 03:51

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

RichD · 2012-09-26, 05:24

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

(I'm partly serious about this question for the newbies.)

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

2011-07-15, 03:51	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·37·127 Posts	Try something like: Code: n: 70660119042903854046516409844370038935302985028064659122643072861070853843136559153244087740059607644464606489303319089200206965812929296697868636129615795714605815617265147516321 c5: 127 c0: -27 Y1: 1 Y0: -5474401089420219382077155933569751763 type: snfs skew: 0.73 ...or 1143m^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, 11:15	#5
mhill12 Jul 2011 110₂ 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

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

2011-07-15, 04:55	#4
Andi_HB Mar 2007 Germany 108₁₆ 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, 12:21	#6
mhill12 Jul 2011 110₂ 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.

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