mersenneforum.org  

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

 
 
Thread Tools
Old 2005-05-12, 02:02   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Question

Quote:
Originally Posted by dleclair
AMD64 3400?! Now who is cheating? My machines are practically steam-powered by comparison. No, just kidding, but they are mere Athlon 2500's.



It's by no means certain that NFSNET will do 2^760+1 but even if we don't then we've done a small favour to whoever eventually takes it on.

I'm willing to coordinate a search so we're not searching the same ranges.

If there are others who are interested in participating, let me know.

Jes, perhaps you and I can settle on some parameters to use and start dividing up the search space. I have no experience selecting parameters for a number this large so advice from you or anyone else is heartily welcome.

-Don
Actually, the *really* interesting question is whether the number would be
faster with SNFS or GNFS. SNFS lets us take advantage of the algebraic
factor 2^152+1, but requires a quartic, which is sub-optimal for numbers
this size.
R.D. Silverman is offline  
Old 2005-05-12, 09:00   #13
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22·29 Posts
Thumbs up

Quote:
Originally Posted by dleclair
Jes, perhaps you and I can settle on some parameters to use and start dividing up the search space.
OK. In february the ggnfs NFS suite started using the Kleinjung poly tool. That code was sent to Chris Monico by Kleinjung and is thus a fairly new code. The poly selection code had a file with suggested parameters from Kleinjung:

Code:
Each lines contains the values:
nbit nprimes a5max normmax normmax1 normmax2 murphye e
...

350 4 100000 6e15 2e14 2e12 1e-09 1.69e-09
360 4 200000 1.5e16 5e14 5e12 7.5e-10 1.13e-09
370 4 200000 4e16 1.5e15 1.5e13 5e-10 7.75e-10
380 4 500000 8e16 4e15 3e13 3.5e-10 5.02e-10
390 4 500000 3e17 1e16 1e14 2.5e-10 3.53e-10
400 4 500000 9e17 3e16 2.5e14 2e-10 2.89e-10
410 4/5 2000000 3e18 1e17 7e14 1.4e-10 1.71e-10
420 5 2000000 1e19 3e17 2e15 9e-11 1.10e-10
430 5 2000000 3e19  9e17  5e15 5e-11 7.12e-11
440 5 2000000 1e20  2.5e18  1.5e16 3e-11 5.26e-11
450 5 2000000 4e20 7e18 4e16 2e-11 3.16e-11
460 6 10000000 1e21 2e19 1e17 1.8e-11 2.14e-11
470 6 10000000 4e21 6e19 3e17 1e-11 1.63e-11
480 6 10000000 1.5e22 2e20  9e17 7e-12 9.14e-12
490 ? ? 5e22  5e20  2.5e18
500 7 100000000 1.5e23 1.5e21 7e18 3e-12 >3.44e-12
510 ? ? 5e23  4e21  2e19
520 ? ? 2e24  1.5e22  5e19
530 ? ? 6e24  4e22  1.5e20
540 ? ? 2e25  1e23  4e20
I just interpolated these values to get the values I used. I would like to suggest the following values: npr=7, normmax=4.7e23, normmax1=4e21, normmax2=1.7e19 and MurphyE=3e-12, as our number is 508 bits.

Don, Please just assign an a5 range for me as you see fit. Currently I have some machines sieveing for 3,437-, but I can start searching when they are done sieving.


--
Cheers,
Jes

Last fiddled with by JHansen on 2005-05-12 at 09:02
JHansen is offline  
Old 2005-05-12, 19:30   #14
dleclair
 
dleclair's Avatar
 
Mar 2003

7·11 Posts
Default

Hi Bob,

Quote:
Actually, the *really* interesting question is whether the number would be
faster with SNFS or GNFS. SNFS lets us take advantage of the algebraic
factor 2^152+1, but requires a quartic, which is sub-optimal for numbers
this size.
Using the (only) trick I know I get a quadratic and a linear:

f(x) = x^2 - x - 1
g(x) = 2^152*x-2^304-1
x=(2^152+1/2^152)

Clever selection of polynomials is certainly not my forte and I've probably missed something.

Any tips?

Here is PARI code to show the process I used to reach the quadratic and linear:

Code:
x^608 - x^456 + x^304 - x^152 + 1

y=x^152

y^4 - y^3 + y^2 - y + 1

(y^4 + y^2) - (y^3 + y) + 1

(y^4 + y^2) - (y^3 + y) + 1

( (y^4 + y^2) - (y^3 + y) + 1 ) / y^2

( (y^2 + 1) - (y^1 + y^-1) + y^-2 )

y^2 + 1 - y^1 - y^-1 + y^-2

y^2 + y^-2 - (y^1 + y^-1) + 1

z=y+y^-1

y^2 + y^-2 - z + 1

z^2= (y^2 + y^-2 + 2)

z^2 - 2 - z + 1

z^2 - z - 1

n=(2^760+1)/(2^152+1)

f(x) = x^2 - x - 1
g(x) = 2^152*x-2^304-1

m=(2^152+1/2^152)

f(m)%n
g(m)%n
-Don
dleclair is offline  
Old 2005-05-12, 19:53   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by dleclair
Hi Bob,



Using the (only) trick I know I get a quadratic and a linear:

f(x) = x^2 - x - 1
g(x) = 2^152*x-2^304-1
x=(2^152+1/2^152)

<snip>

-Don

2^760 + 1 = x^5 + 1 with x = 2^152. But x^5+1 =
(x+1)(x^4-x^3+x^2-x+1)

So just use x - M and x^4-x^3+x^2-x+1 with M = 2^152

It is best NOT to convert the reciprocal quartiic into a quadratic in (x+1/x)
because doing so blows up the coefficients on the linear side by too much.
R.D. Silverman is offline  
Old 2005-05-13, 04:07   #16
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
Originally Posted by xilman
... clearing the base-2 tables to 768 bits.
Kazumaro Aoki just broke the c221 cofactor of 2,751+ into c221 = p55.c166 with ECM.
geoff is offline  
Old 2005-05-13, 06:38   #17
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

42228 Posts
Default

Quote:
Originally Posted by R.D. Silverman
2^760 + 1 = x^5 + 1 with x = 2^152. But x^5+1 =
(x+1)(x^4-x^3+x^2-x+1)

So just use x - M and x^4-x^3+x^2-x+1 with M = 2^152

It is best NOT to convert the reciprocal quartiic into a quadratic in (x+1/x)
because doing so blows up the coefficients on the linear side by too much.
How about M=2^76+2^-76 and the polys x^4-5x^2+5, 2^76x-2^152-1? Does eliminating the odd powers in the polynomial help? Does increasing the linear coefficient of the linear polynomial hurt much? Just curious...

Greg
frmky is offline  
Old 2005-05-13, 08:25   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×3×11×83 Posts
Default

Quote:
Originally Posted by geoff
Kazumaro Aoki just broke the c221 cofactor of 2,751+ into c221 = p55.c166 with ECM.
Hmm.

So we won't get a >p100 penultimate factor any more, but it's still worth finishing with SNFS.

Luckily the cofactor is still composite, or we would have spent quite some time having run the survey sieving to no avail.


Paul
xilman is offline  
Old 2005-05-13, 10:56   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

Quote:
Originally Posted by frmky
How about M=2^76+2^-76 and the polys x^4-5x^2+5, 2^76x-2^152-1? Does eliminating the odd powers in the polynomial help? Does increasing the linear coefficient of the linear polynomial hurt much? Just curious...

Greg
They would be roughly equivalent. However, the cyclotomic poly would
have a higher density of small primes that split completely. This would
make norms slightly more likely to be smooth.
R.D. Silverman is offline  
Old 2005-07-05, 03:28   #20
junky
 
junky's Avatar
 
Jan 2004

7·19 Posts
Default

Quote:
Originally Posted by JHansen


Ahh, that's cheating! I just let my home PC (AMD64 3400) loose before I went to bed, and those polynomials were found when I got up 7 hours later.

Jes
Can i ask if you're running that machine for standard NFSnet? i presume, can i know which computerid is that machine? i'd like to see their stats, cause im planning to buy a similar machine (AMD64 3500+) and i'd like to compare with my p4-2.8GhZ, 800FSB.
Thanks.
junky is offline  
Old 2009-03-15, 04:22   #21
flouran
 
flouran's Avatar
 
Dec 2008

72·17 Posts
Default

Quote:
Originally Posted by JHansen View Post
and those polynomials were found when I got up 7 hours later.
Sorry to be off-topic, but you are so lucky that you sleep 7 hours. I normally get 3-5 hours of sleep.

Last fiddled with by flouran on 2009-03-15 at 04:22
flouran is offline  
 

Thread Tools


All times are UTC. The time now is 13:07.


Mon Oct 25 13:07:03 UTC 2021 up 94 days, 7:36, 0 users, load averages: 1.16, 1.19, 1.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.