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

[QUOTE=mhill12;266444]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[/QUOTE]

This is a C185 with SNFS ---> easy! Just forget about the known
factors.

Try something like:
[CODE]n: 70660119042903854046516409844370038935302985028064659122643072861070853843136559153244087740059607644464606489303319089200206965812929296697868636129615795714605815617265147516321
c5: 127
c0: -27
Y1: 1
Y0: -5474401089420219382077155933569751763
type: snfs
skew: 0.73[/CODE]
...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 [I]is[/I] easy.

You can try the snfs poly generator (experiment) from this site [URL]http://factorization.ath.cx/index.php[/URL]

This option is new from Syd - more Informations here
[URL]http://www.mersenneforum.org/showpost.php?p=266328&postcount=1128[/URL]

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

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.

[QUOTE=mhill12;266488]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.[/QUOTE]

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]

[QUOTE=wblipp;312760]Today I added a C157 to the list in [URL="http://www.mersenneforum.org/showthread.php?p=311744#post311744"]post 209[/URL]. It would use a quartic. This joins the C171 and C175 not yet claimed. The new number is

[code]
(2403293005054398937076590802836226619421^5-1)/(5*2403293005054398937076590802836226619420)[/code][/QUOTE]

[QUOTE=Dubslow;312772]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
[/code]
If so, then I'll do this when my [URL="http://www.mersenneforum.org/showthread.php?p=311744#post311744"]current reservation[/URL] is done (and I'll then do the C17*s if they're still available).

[SIZE="1"](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 :razz:)[/SIZE]

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]

[QUOTE=wblipp;312778]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.[/QUOTE]
...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?

[QUOTE=Dubslow;312789]...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?[/QUOTE]
Thank you, Capt. Obvious!

[QUOTE=Batalov;312792]Thank you, Capt. Obvious![/QUOTE]

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

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

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