20040225, 17:48  #12 
Nov 2003
1D24_{16} Posts 
"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 :)" If you will send me a private note, with your email address, I will send a paper (Postscript) describing details of SNFS. 
20040301, 12:53  #13 
Jan 2004
7×19 Posts 
hey bob, im still waiting for your papers :)
thanks. 
20040302, 12:45  #14 
Sep 2002
Vienna, Austria
219_{10} Posts 
What about the C228 cofactor of 12^256+1?

20040302, 13:18  #15  
Nov 2003
2^{2}×5×373 Posts 
Quote:
too big for GNFS. 

20040303, 14:34  #16  
"William"
May 2003
New Haven
2^{3}×5×59 Posts 
Quote:


20040303, 16:21  #17  
"William"
May 2003
New Haven
4470_{8} Posts 
Quote:


20040304, 09:29  #18  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2×5,197 Posts 
Quote:
Actually, that's an oversimplification, but it's a good first cut. If you want more details, dig out Brian Murphy's thesis. An example may help. NFSNET is currently sieving the 201digit composite cofactor of 10^223+1. We are using the polynomials x^6+10 and 1  (10^37)*x which share a root 10^(37) modulo 10^223+1. The latter value is a 201digit number. Paul 

20040309, 16:24  #19  
Nov 2003
1D24_{16} Posts 
Quote:
and look at a 'typical' lattice point. (say (3x10^6, 3x10^6)) (choose another if you like) We have two polynomials. The corresponding norms at lattice point (b,a) are a + 10^37 b and a^6 + 10b^6. For our typical point, the norms are about 3x10^43 and 7x10^39. Note that the linear norm is larger. The product is about 2x10^82 If we were to use a quintic, the linear norm becomes about 3 x 10^51 while the algebraic norm shrinks to 2 x 10^33. The product is now about 6 x 10^84, i.e. larger. A septic would yield norms of about 3x10^38 and 2 x 10^46. Having equal norms would be optimal. The size of the root affects the norm of the linear polynomial. There is a yingyang effect. Reducing one norm increases the other and vice versa. We want the product to be as small as possible averaged over the sieve region. See my recent paper for a more detailed analysis. 

20040310, 15:48  #20  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·5,197 Posts 
Quote:
Bob, I agree with you (with the reservations noted in my original about the analysis only being a first cut) if the linear polynomial is of the form xm where m is the root. Note there is nothing in the NFS which requires a polynomial to be linear, though a linear polynomial is very frequently used because of the difficulty in finding good polynomials of higher degree which share a common root with other polynomial(s) in use. Neither is there any requirement that a linear polynomial by xm. I gave an explicit example where the root m is very large but the poynomial norms are quite small. That polynomial was x/m  1. I further note that Kleinjung's method of finding quintics for GNFS finds linear polynomials of the form ax+b where neither a nor b are equal to the value of the common root. I stand by my claim that (subject to the agreed disclaimer) that the size of the coefficients of the polynomials are much more important than the size of the root. By taking xm as your linear polynomial you are implicitly agreeing with me as in this particular case the root is a coefficient of a polynomial. I do, of course, agree that ideally the degrees and coefficients of the polynomials should be chosen that the norms are as close to each other as possible and as small as possible (again, subject to considerations which can be found in Murphy's thesis). Paul 

20050505, 02:34  #21 
"Jason Goatcher"
Mar 2005
6661_{8} Posts 
Somewhat offtopic: Would this Brian Murphy you keep mentioning happen to be a darkhaired fat dude with a winning smile? I knew a Brian Murphy that went to college here in Conway, AR, but I don't know his major. Could he be the same guy?

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 