mersenneforum.org What's next?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2005-05-12, 02:02   #12
R.D. Silverman

Nov 2003

1D2416 Posts

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.

2005-05-12, 09:00   #13
JHansen

Apr 2004
Copenhagen, Denmark

22·29 Posts

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

2005-05-12, 19:30   #14
dleclair

Mar 2003

7·11 Posts

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

2005-05-12, 19:53   #15
R.D. Silverman

Nov 2003

164448 Posts

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) -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.

2005-05-13, 04:07   #16
geoff

Mar 2003
New Zealand

13×89 Posts

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.

2005-05-13, 06:38   #17
frmky

Jul 2003
So Cal

42228 Posts

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

2005-05-13, 08:25   #18
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×3×11×83 Posts

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

2005-05-13, 10:56   #19
R.D. Silverman

Nov 2003

22·5·373 Posts

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.

2005-07-05, 03:28   #20
junky

Jan 2004

7·19 Posts

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.

2009-03-15, 04:22   #21
flouran

Dec 2008

72·17 Posts

Quote:
 Originally Posted by JHansen 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

 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.