SNFS poly for b^n-1, n prime?

[ryanp]

Hi,

Does anyone know how to choose good polynomials for factoring values of the form b^n-1, where b is fairly large (but not too huge) and n is a small prime?

Here's an example: 31280679788951^19-1. I'm trying the "obvious" sextic. The remaining cofactor is here: http://www.factordb.com/index.php?id...00000626001619

n: 56345888...6599
m: 30607548590205662094417371657380933049351
type: snfs
deg: 6
c6: 31280679788951
c0: -1

With this:

* lasieve5 produces output files containing no lines (??)
* lasieve4I16e works, but is *abysmally* slow, with a very poor yield.

Is there something better out there?

[R.D. Silverman]

Originally Posted by ryanp

Hi,

Does anyone know how to choose good polynomials for factoring values of the form b^n-1, where b is fairly large (but not too huge) and n is a small prime?

Here's an example: 31280679788951^19-1. I'm trying the "obvious" sextic. The remaining cofactor is here: http://www.factordb.com/index.php?id...00000626001619

n: 56345888...6599
m: 30607548590205662094417371657380933049351
type: snfs
deg: 6
c6: 31280679788951
c0: -1

With this:

* lasieve5 produces output files containing no lines (??)
* lasieve4I16e works, but is *abysmally* slow, with a very poor yield.

Is there something better out there?

When in doubt, look at typical norms......

Consider, e.g. what an "average" norm looks like for the algebraic
polynomial. A typical lattice point (say (10^6, 10^6) will have
norm 3 x 10^13 x 10^36 ~ 10^49 or so. This is very large;

The problem is the coefficient, ~ 3.12 x 10^13. I see no way to get rid of it.
Further, the rational side has norms ~ (3.12 x 10^13)^3 x 10^6, ~
3 x 10^46 which is typical for a C278-C280 or so; But the algebraic
side is much larger than that for a typical C278.


No siever will help. It's the number itself.

[bsquared]

You could try the quintic. Suboptimal degree for the size, but much better coefficients.

c5: 1
c0: -31280679788951
m: 957424926574981927749284809890910733899584299547520801

[R.D. Silverman]

Originally Posted by bsquared

You could try the quintic. Suboptimal degree for the size, but much better coefficients.

c5: 1
c0: -31280679788951
m: 957424926574981927749284809890910733899584299547520801

Huh? The algebraic coefficient remains the same. The rational coefficient
goes from b^3 to b^4. Thus, the rational norms increase by a factor of
b, [big! ~ 10^13] while the algebraic norms only drop by the average
value of a lattice point (say 10^6 or so)

Going to a quintic should make it WORSE.

[bsquared]

Originally Posted by R.D. Silverman

Huh? The algebraic coefficient remains the same. The rational coefficient
goes from b^3 to b^4. Thus, the rational norms increase by a factor of
b, [big! ~ 10^13] while the algebraic norms only drop by the average
value of a lattice point (say 10^6 or so)

Going to a quintic should make it WORSE.

I didn't look closely at it, just suggested it as a means of reducing the large leading coefficient. Using three large primes on the rational side might mitigate the quintic norm increase somewhat, but probably not enough.

[ryanp]

The quintic actually does seem to help -- if only that lasieve5 isn't choking on it now.

I don't know why lasieve5 produces empty output files for the original sextic that I tried...

[Batalov]

Try putting a manually picked skew in the sextic poly file?
It is possible that the script that prepares it for you (since it is not in the file) rounds it down to "0". (e.g. printf's it with "%.2f" ?)