mersenneforum.org SNFS poly for b^n-1, n prime?
 Register FAQ Search Today's Posts Mark Forums Read

 2013-07-18, 21:36 #1 ryanp     Jun 2012 Boulder, CO 5·7·13 Posts SNFS poly for b^n-1, n prime? 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 Code: 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?
2013-07-18, 22:40   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

755610 Posts

Quote:
 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 Code: 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.

 2013-07-18, 22:42 #3 bsquared     "Ben" Feb 2007 EB416 Posts You could try the quintic. Suboptimal degree for the size, but much better coefficients. c5: 1 c0: -31280679788951 m: 957424926574981927749284809890910733899584299547520801
2013-07-19, 12:14   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101100001002 Posts

Quote:
 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.

2013-07-19, 13:18   #5
bsquared

"Ben"
Feb 2007

22×941 Posts

Quote:
 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.

 2013-07-19, 13:39 #6 ryanp     Jun 2012 Boulder, CO 1110001112 Posts 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...
 2013-07-19, 17:23 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33×13×29 Posts 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" ?)

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Factoring 7 2015-05-27 23:09 VBCurtis Factoring 11 2015-03-09 07:01 schickel FactorDB 0 2011-12-16 18:07 JoeCrump Factoring 3 2009-10-29 21:00 nuggetprime Factoring 22 2008-08-15 10:01

All times are UTC. The time now is 06:32.

Thu Jun 1 06:32:11 UTC 2023 up 287 days, 4 hrs, 0 users, load averages: 1.15, 1.08, 1.09