mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > NFSNET Discussion

 
 
Thread Tools
Old 2003-06-07, 23:06   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

234010 Posts
Default 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^227-1) important? Is ths size of the composite cofactor (212 digits for 10^227-1) important? How big is "too big to be interesting?" How much previous work should have been done by other methods?
wblipp is offline  
Old 2003-06-08, 17:01   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

100111100000012 Posts
Default

What traits make a number a good choice for NFSNET? Is the size of the base number (227 digits for 10^227-1) important? Is ths size of the composite cofactor (212 digits for 10^227-1) 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
xilman is offline  
Old 2003-08-07, 22:04   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by xilman
For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.
So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

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?
wblipp is offline  
Old 2003-08-08, 11:46   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

278116 Posts
Default

Quote:
Originally Posted by wblipp
Quote:
Originally Posted by xilman
For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.
So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

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?
Sounds like a good summary to me.

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 217-digit number) then we could run SNFS on it. I haven't found any such polynomial.


Paul
xilman is offline  
Old 2003-08-08, 15:17   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

234010 Posts
Default

Quote:
Originally Posted by xilman
Quote:
Originally Posted by wblipp
So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

1. The 195 digit cofactor ...

2. The 358 digit 2^1188+1 ....

3. The primitive polynomial is only 217 digits ...
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 217-digit number) then we could run SNFS on it. I haven't found any such polynomial.
Is it sufficient for the root to be modulo the C195 cofactor, or does the root really need to be modulo the C217 primitive factor?
wblipp is offline  
Old 2003-08-10, 10:28   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·3,371 Posts
Default

Quote:
Originally Posted by wblipp
Quote:
Originally Posted by xilman
Quote:
Originally Posted by wblipp
So looking at the 195 digit cofactor from 2^1188+1, it's not a good candidate.

1. The 195 digit cofactor ...

2. The 358 digit 2^1188+1 ....

3. The primitive polynomial is only 217 digits ...
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 217-digit number) then we could run SNFS on it. I haven't found any such polynomial.
Is it sufficient for the root to be modulo the C195 cofactor, or does the root really need to be modulo the C217 primitive factor?
Modulo the C195 is fine. Oh, I forgot: the polynomial has to have degree at least 4.

Paul
xilman is offline  
Old 2004-02-23, 17:44   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by xilman
For SNFS, the range is about 180 to 240 digits. For GNFS the range is perhaps 135 digits to 165 digits.
...
If you can find a polynomial of degree at most 7 (and at least 4) with coefficients all of which are smaller than, say, 9 digits and a corresponding root modulo N (where N is the 217-digit number (or the 195-digit number)) then we could run SNFS on it.
For cases where we can find such a polynomial, is the feasible range then same 180-240 digits quoted above? Or would such a "found" polynomial be less effective, so that the practical range is something between these ranges?

William
wblipp is offline  
Old 2004-02-24, 09:11   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·3,371 Posts
Default

Quote:
Originally Posted by wblipp
For cases where we can find such a polynomial, is the feasible range then same 180-240 digits quoted above? Or would such a "found" polynomial be less effective, so that the practical range is something between these ranges?

William
The range 180-240 remains the same.

Paul
xilman is offline  
Old 2004-02-24, 11:43   #9
nfortino
 
nfortino's Avatar
 
Nov 2003

2458 Posts
Default

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.
nfortino is offline  
Old 2004-02-24, 13:48   #10
TauCeti
 
TauCeti's Avatar
 
Mar 2003
Braunschweig, Germany

2×113 Posts
Default

Quote:
Originally Posted by nfortino
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.
An excellent and freely available 142-page paper (diploma thesis) with an explanation of the general ideas behind NFS and a GNFS/SNFS comparison can be found here. But AFAIK it's only available in german language.

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 ;)
TauCeti is offline  
Old 2004-02-24, 14:44   #11
junky
 
junky's Avatar
 
Jan 2004

7·19 Posts
Default

Quote:
Originally Posted by nfortino
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.
really good question, if ya find something before me, feel free to post it, so I and a lot a ppl would have the possibility to take a look on it.

im sure we could find such papers somewhere in US' universities. Maybe Jeff would knows :)

later

Last fiddled with by junky on 2004-02-24 at 14:45
junky is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Good Carmichael Number construction algorithm? carpetpool Miscellaneous Math 3 2018-03-04 13:51
are blade servers good for number crunching? ixfd64 Hardware 11 2011-11-02 23:54
New York Plans to Make Gender Personal Choice ewmayer Soap Box 12 2006-11-09 14:40
http://www.nfsnet.org/downloads/nfsnet-04145-powerpc-MacOSX.tgz Death NFSNET Discussion 15 2004-06-22 07:35
Strength in number don't make right. Uncwilly Soap Box 5 2004-01-13 19:48

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

Thu Oct 22 06:39:37 UTC 2020 up 42 days, 3:50, 0 users, load averages: 1.35, 1.60, 1.44

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.