20130718, 21:36  #1 
Jun 2012
Boulder, CO
5·7·13 Posts 
SNFS poly for b^n1, n prime?
Hi,
Does anyone know how to choose good polynomials for factoring values of the form b^n1, where b is fairly large (but not too huge) and n is a small prime? Here's an example: 31280679788951^191. 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 * lasieve5 produces output files containing no lines (??) * lasieve4I16e works, but is *abysmally* slow, with a very poor yield. Is there something better out there? 
20130718, 22:40  #2  
"Bob Silverman"
Nov 2003
North of Boston
7556_{10} Posts 
Quote:
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 C278C280 or so; But the algebraic side is much larger than that for a typical C278. No siever will help. It's the number itself. 

20130718, 22:42  #3 
"Ben"
Feb 2007
EB4_{16} Posts 
You could try the quintic. Suboptimal degree for the size, but much better coefficients.
c5: 1 c0: 31280679788951 m: 957424926574981927749284809890910733899584299547520801 
20130719, 12:14  #4  
"Bob Silverman"
Nov 2003
North of Boston
1110110000100_{2} Posts 
Quote:
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. 

20130719, 13:18  #5  
"Ben"
Feb 2007
2^{2}×941 Posts 
Quote:


20130719, 13:39  #6 
Jun 2012
Boulder, CO
111000111_{2} 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... 
20130719, 17:23  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{3}×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" ?) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How To Calculate SNFS Poly?  Stargate38  Factoring  7  20150527 23:09 
29 to 30 bit large prime SNFS crossover  VBCurtis  Factoring  11  20150309 07:01 
Ooops....SNFS poly for primes?  schickel  FactorDB  0  20111216 18:07 
SNFS Poly creation for n=2*x^2  1  JoeCrump  Factoring  3  20091029 21:00 
Homogeneous Cunningham snfs poly selection?  nuggetprime  Factoring  22  20080815 10:01 