20030607, 23:06  #1 
"William"
May 2003
New Haven
3·787 Posts 
What traits make a number a good choice for NFSNET?
What traits make a number a good choice for NFSNET? Is the size of the base number (227 digits for 10^2271) important? Is ths size of the composite cofactor (212 digits for 10^2271) important? How big is "too big to be interesting?" How much previous work should have been done by other methods?

20030608, 17:01  #2 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·3,529 Posts 
What traits make a number a good choice for NFSNET? Is the size of the base number (227 digits for 10^2271) important? Is ths size of the composite cofactor (212 digits for 10^2271) important? How big is "too big to be interesting?" How much previous work should have been done by other methods?
Several characteristics are taken into account. Perhaps the most important is that it should not be too hard (or we'd never get it finished with the resources we have) or too easy (or we'd spend more time on administration than computation. For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits. For the time being we want to do numbers which are of some mathematical interest, which means in practice they come from a number of well know tables of factorizations associated with various projects. Almost all so far have come from the Cunningham project. We don't want to spend a great deal of effort finding a factor which could have been found much more easily with the Elliptic Curve Method, so we generally require that a NFSNET candidate have had enough ECM work done on it that it's unlikely to have a factor below 50 digits or so. Paul 
20030807, 22:04  #3  
"William"
May 2003
New Haven
3×787 Posts 
Quote:
1. The 195 digit cofactor is bigger than the 165 digit limit for GNFS. 2. The 358 digit 2^1188+1 is bigger than the 240 digit limit for SNFS. 3. The primitive polynomial is only 217 digits, but (x^33+1)*(x+1)/((x^11+1)*(x^3+1)) isn't special enough for SNFS to take advantage of. Is that all correct? 

20030808, 11:46  #4  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10100101011011_{2} Posts 
Quote:
If you can find a polynomial of degree at most 7 with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217digit number) then we could run SNFS on it. I haven't found any such polynomial. Paul 

20030808, 15:17  #5  
"William"
May 2003
New Haven
3·787 Posts 
Quote:


20030810, 10:28  #6  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10587_{10} Posts 
Quote:
Paul 

20040223, 17:44  #7  
"William"
May 2003
New Haven
3·787 Posts 
Quote:
William 

20040224, 09:11  #8  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
295B_{16} Posts 
Quote:
Paul 

20040224, 11:43  #9 
Nov 2003
165_{10} Posts 
Could someone point me to a good paper on the SNFS? I was able to find one on the GNFS, but I havenβt found one detailing the differences.

20040224, 13:48  #10  
Mar 2003
Braunschweig, Germany
2×113 Posts 
Quote:
There are also large sections about GNFS and SNFS in the book 'Prime Numbers" from Crandall and Pomerance. So far i have not looked into 'The Development of the Number Field Sieve' from Lenstra but maybe i should if i ever want to succeed understanding the SNFS ;) 

20040224, 14:44  #11  
Jan 2004
7·19 Posts 
Quote:
im sure we could find such papers somewhere in US' universities. Maybe Jeff would knows :) later Last fiddled with by junky on 20040224 at 14:45 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Good Carmichael Number construction algorithm?  carpetpool  Miscellaneous Math  3  20180304 13:51 
are blade servers good for number crunching?  ixfd64  Hardware  11  20111102 23:54 
New York Plans to Make Gender Personal Choice  ewmayer  Soap Box  12  20061109 14:40 
http://www.nfsnet.org/downloads/nfsnet04145powerpcMacOSX.tgz  Death  NFSNET Discussion  15  20040622 07:35 
Strength in number don't make right.  Uncwilly  Soap Box  5  20040113 19:48 