How To Calculate SNFS Poly?

[Stargate38]

How do I calculate a SNFS poly? Is there an easy formula based on N?

[VBCurtis]

Give an example of the form of the number you wish to factor. There are many cases.

[Stargate38]

(n^2p+1)/(n²+1) with prime p
n^2[SUP]x[/SUP]+1
aⁿ±bⁿ (take out algebraic factors first)

i.e. 4607450010708798⁸+1 (known factor before I factored it: 449). I wasted 2-3 CPU-days doing GNFS on it, before I realized that I could have done it in a matter of hours with SNFS.

[wblipp]

Have you read the Mersenne Wiki article on polynomial selection?

[R.D. Silverman]

Originally Posted by Stargate38

How do I calculate a SNFS poly? Is there an easy formula based on N?

Optimal Parameterization of SNFS. J. Math. Cryptology

[R.D. Silverman]

Originally Posted by Stargate38

(n^2p+1)/(n²+1) with prime p
n^2[SUP]x[/SUP]+1
aⁿ±bⁿ (take out algebraic factors first)

i.e. 4607450010708798⁸+1 (known factor before I factored it: 449). I wasted 2-3 CPU-days doing GNFS on it, before I realized that I could have done it in a matter of hours with SNFS.

May I suggest that it would be helpful if you would learn how to perform polynomial algebra??

For your first question (n^2p + 1)/(n^2+1) may I suggest performing the division and looking at the
result? One gets a dense polynomial of degree 2p-2........

n^(2^x) + 1 is algebraically prime.

for a^n +/- b^n, start by factoring it, completely. Or are you asking about the primitive cofactor?

[Dubslow]

Yafu can do automatic snfs poly selection for the example as well as the second two forms (though I don't know if it can take advantage of the power of 2 exponent, or if that's even possible).

[R.D. Silverman]

Originally Posted by Dubslow

Yafu can do automatic snfs poly selection for the example as well as the second two forms (though I don't know if it can take advantage of the power of 2 exponent, or if that's even possible).

Another example of: "don't think, just throw a computer at it".

The OP asked HOW. Suggesting to use a black box does not answer that question.

Indeed. Your statement "I don't know........possible." suggests that you should not
have even tried to answer this question.

(Hint: Once you have decided the degree for the SNFS algebraic polynomial for 2^2^n+1,
it is trivial first year algebra to find the representation).