mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-07-18, 21:36   #1
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

3×59 Posts
Default 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?
ryanp is online now   Reply With Quote
Old 2013-07-18, 22:40   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

3×13×191 Posts
Default

Quote:
Originally Posted by ryanp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-07-18, 22:42   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

26·3·17 Posts
Default

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

c5: 1
c0: -31280679788951
m: 957424926574981927749284809890910733899584299547520801
bsquared is offline   Reply With Quote
Old 2013-07-19, 12:14   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

3×13×191 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-07-19, 13:18   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

26×3×17 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
bsquared is offline   Reply With Quote
Old 2013-07-19, 13:39   #6
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

3·59 Posts
Default

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...
ryanp is online now   Reply With Quote
Old 2013-07-19, 17:23   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2×7×647 Posts
Default

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" ?)
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How To Calculate SNFS Poly? Stargate38 Factoring 7 2015-05-27 23:09
29 to 30 bit large prime SNFS crossover VBCurtis Factoring 11 2015-03-09 07:01
Ooops....SNFS poly for primes? schickel FactorDB 0 2011-12-16 18:07
SNFS Poly creation for n=2*x^2 - 1 JoeCrump Factoring 3 2009-10-29 21:00
Homogeneous Cunningham snfs poly selection? nuggetprime Factoring 22 2008-08-15 10:01

All times are UTC. The time now is 18:41.

Thu Jul 9 18:41:29 UTC 2020 up 106 days, 16:14, 1 user, load averages: 1.60, 1.93, 1.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.