[QUOTE=R.D. Silverman]I am willing to advice people on polynomial selection for SNFS.

Also, anyone who sends me email at my private address can receive a
copy of my paper on optimal parameter selection for NFS.[/QUOTE]
Is the title "[I]Optimal Paramaterization of SNFS[/I]"?
Could you go into a little detail about [B]norm[/B] as used in that paper?

[QUOTE=akruppa]Hey!! Wrong tag name! :rant:

Alex

Edit: Doesn't even look like me.. grmbl...[/QUOTE]

Alex (:alex:), I'd be happy to trade you the one named in my honor, if that will make you feel less sheepish.

-Ernst (:ernst:)

[QUOTE=Joe O]Is the title "[I]Optimal Paramaterization of SNFS[/I]"?
Could you go into a little detail about [B]norm[/B] as used in that paper?[/QUOTE]


Yes. It is that paper.

Norm is just the usual algebraic norm; i.e. the product of all the algebraic conjugates.

Feel free to ask any questions. I'll be happy to answer.

[QUOTE=akruppa]Your number is a wonderful example of a few things that need to be improved in phi.c - the polynomial is horrible. For one thing, it would have been better to use -deg4 with the current phi.c. Since 53%5==3, using degree 5 (the default) causes phi.c to multiply the polynomial by x^2 which increases the difficulty by 5 and results in the large coefficient -102400 in the algebraic polynomial.

It would be even better to teach phi.c about the base splitting trick for composite bases. For example, 8*x^5-25 is a nice polynomial for your number. It may be a while before I get around to do that, though.

Alex[/QUOTE]

I tried a couple of numbers using -deg4, but they all took significantely longer to factor. 15-16 hours versus 8-10 hours for deg5 poly's

I'm not sure how to create poly's of cyclotomic numbers by hand yet. Until i've got time to figure that out, i patiently wait for the next version of phi.

I did a few experiments with phi(53,320), too. The quintic with small coefficients produced ~100 rels/sec on a 1GHz Athlon, the quartic ~83 rels/sec, the default quintic ~65 rels/sec. The other sieving parameters were comparable, so the total number of relations needed should be closely the same for each case.

Whether degree 4 or 5 is better (assuming no useful algebraic factors) depends on how large the number to factor is, and what the exponent (mod 4) and (mod 5) is. x^n-1 with n==3 (mod 5) is rather poor because we need to multiply by x^2 and have that as a coefficient. With large x, this leads to pretty large coefficients. With degree 4 polynomials, you only need to multiply by x in the 3 (mod 4) case or reduce the exponent by 1 in the 1 (mod 4) case - either way, the coefficient is only x. All this assumes that x is prime, i.e. that the base splitting trick does not work.

For x^n-1 with n==1 (mod 5) or ==4 (mod 5), the quintic wins handily.

Alex

[QUOTE=akruppa]
For x^n-1 with n==1 (mod 5) or ==4 (mod 5), the quintic wins handily.
[/QUOTE]

So to take as examples the two roadblock numbers listed at [url]www.oddperfect.org[/url], this would imply that for 5^349-1, the polynomial X^5-5 is a better choice, but for 19^193-1, the polynomial 19*X^4-1 would be better?

[QUOTE=philmoore]So to take as examples the two roadblock numbers listed at [url]www.oddperfect.org[/url], this would imply that for 5^349-1, the polynomial X^5-5 is a better choice, but for 19^193-1, the polynomial 19*X^4-1 would be better?[/QUOTE]

Neither! For numbers this size, a sextic would be quite a bit better than both.

I would use 5x^6 - 1 and 19x^6 - 1. And a quartic becomes sub-optimal
for any number above 150-160 digits. You should choose a polynomial so
that the norms on both sides are as close as possible, unless dealing with
a number of special form (usually a composite exponent) . e.g. 19^195 - 1
should be done with a quartic so you can take advantage of the large
algebraic factor.

Read my paper.

Yes, I was (without stating so) assuming numbers in the range of 130-180 difficulty. Smaller numbers are hard to find these days, and people who seriously consider larger number ought to know SNFS well enough that they don't need a program to make polynomials for them. For numbers in the 130-180 range without useful algebraic factors, degree 5 is a very good default choice. *

Alex

*Edit: subject to aforementioned problems with exponents 2,3 (mod 5) and large bases.

[QUOTE=ewmayer]Alex (:alex:), I'd be happy to trade you the one named in my honor, if that will make you feel less sheepish.

-Ernst (:ernst:)[/QUOTE]

Thanks for the offer, but I fear I must decline. I'm already monkeying around on the forum enough the way it is.

Alex

I've updated phi.c to make better polynomials for numbers with composite base and no useful algebraic factors. It is at [url]http://home.in.tum.de/~kruppa/phi.0.1.2.zip[/url]
The estimated time is still pretty wrong for small numbers. For larger numbers it seems to fit much better. I don't know yet how to accurately model the required time for smaller numbers - tbd...

Alex

[QUOTE=akruppa]I've updated phi.c to make better polynomials for numbers with composite base and no useful algebraic factors. It is at [url]http://home.in.tum.de/~kruppa/phi.0.1.2.zip[/url]
Alex[/QUOTE]

For phi(53,x) the poly's look better (more rels/sec).

I just tried Phi(140,376):

(140 376 (716819461) (C 115))

[CODE]n: 5670349667640533737345129029795054544400388689234852451198849403078229477068582060516180863076298052484046267440141
# 376^70-1, difficulty: 180.26, skewness: 1.00, alpha: 0.00
# cost: 2.38863e+016, est. time: 11.37 GHz days (not accurate yet!)
skew: 1.000
c5: 1
c0: 1
Y1: -1
Y0: 1128833343118249207414947823407333376
m: 1128833343118249207414947823407333376
[/CODE]

Difficulty 180 seems a bit high for a number just over 120 digits

For a deg4 poly things look better:

[CODE]n: 5670349667640533737345129029795054544400388689234852451198849403078229477068582060516180863076298052484046267440141
# 376^70-1, difficulty: 144.21, skewness: 1.00, alpha: 1.45
# cost: 6.70787e+014, est. time: 0.32 GHz days (not accurate yet!)
skew: 1.000
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
Y1: -1
Y0: 1128833343118249207414947823407333376
m: 1128833343118249207414947823407333376
type: snfs
[/CODE]
But still a bit high....