mersenneforum.org  

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

 
 
Thread Tools
Old 2004-02-25, 17:48   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 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 :)"

If you will send me a private note, with your email address, I will send
a paper (Postscript) describing details of SNFS.
R.D. Silverman is offline  
Old 2004-03-01, 12:53   #13
junky
 
junky's Avatar
 
Jan 2004

7×19 Posts
Default

hey bob, im still waiting for your papers :)

thanks.
junky is offline  
Old 2004-03-02, 12:45   #14
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

21910 Posts
Default

What about the C228 cofactor of 12^256+1?
wpolly is offline  
Old 2004-03-02, 13:18   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by wpolly
What about the C228 cofactor of 12^256+1?
It is too big. The C277 for 12,256+ is too big for SNFS and the C228 is
too big for GNFS.
R.D. Silverman is offline  
Old 2004-03-03, 14:34   #16
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by xilman
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.
Does the root need to be small, too? If yes, then it's probably rare for such a polynomial and root to exist because there are only 10^81 combinations of coefficients and roots versus 10^217 possibe modulo values. If the root can be as large as N, then there are probably many such polynomials although it may be difficult to find one of them.
wblipp is offline  
Old 2004-03-03, 16:21   #17
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44708 Posts
Default

Quote:
Originally Posted by wblipp
Does the root need to be small, too?
A bit more musing shows me the root can probably be large. It not, then the highest possible value for the polynomial is about 1072. so the only way to make the modular value zero would be to make the polynomial value zero, which would mean that (x-r) is a factor of the polynomial. Since it's trivial to create such polynomials as (x-r) times anything, it's unlikely such polynomials are of any use.
wblipp is offline  
Old 2004-03-04, 09:29   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×5,197 Posts
Default

Quote:
Originally Posted by wblipp
A bit more musing shows me the root can probably be large. It not, then the highest possible value for the polynomial is about 1072. so the only way to make the modular value zero would be to make the polynomial value zero, which would mean that (x-r) is a factor of the polynomial. Since it's trivial to create such polynomials as (x-r) times anything, it's unlikely such polynomials are of any use.
The root can be any size you like. What's important is the size of the coefficients of the polynomials.

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 201-digit 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 201-digit number.


Paul
xilman is offline  
Old 2004-03-09, 16:24   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Thumbs up

Quote:
Originally Posted by xilman
The root can be any size you like. What's important is the size of the coefficients of the polynomials.

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 201-digit 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 201-digit number.


Paul
Actually Paul, the size of the root does matter. Let's use your example
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
ying-yang 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.
R.D. Silverman is offline  
Old 2004-03-10, 15:48   #20
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·5,197 Posts
Default

Quote:
Originally Posted by Bob Silverman
Actually Paul, the size of the root does matter. Let's use your example
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
ying-yang 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.

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 x-m 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 x-m. 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 x-m 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
xilman is offline  
Old 2005-05-05, 02:34   #21
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

66618 Posts
Default

Somewhat off-topic: Would this Brian Murphy you keep mentioning happen to be a dark-haired 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?
jasong 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 04:40.

Thu Dec 3 04:40:49 UTC 2020 up 52 mins, 0 users, load averages: 1.25, 1.19, 1.20

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.