What's next?

[R.D. Silverman]

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.

[JHansen]

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:

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

[dleclair]

Hi Bob,

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:

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

[R.D. Silverman]

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.

[geoff]

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.

[frmky]

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

[xilman]

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

[R.D. Silverman]

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.

[junky]

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.

[flouran]

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.