mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   NFSNET Discussion (https://www.mersenneforum.org/forumdisplay.php?f=17)
-   -   What's next? (https://www.mersenneforum.org/showthread.php?t=4002)

R.D. Silverman 2005-04-14 15:15

What's next?
 
Hi,

What's next after 11,212+? May I suggest 7,253- and 11,217-? (both easy)
7,253- has been among the first 5 holes in any table for the longest period
of time. It first appeared as a 5th hole back in July '98.

For a more ambitious project 2,719+ and 2,736+ would be nice. Along with
my doing 2,737+ and 2,749+ it would finish all base 2 numbers to 750 bits. :bounce:

xilman 2005-04-14 16:36

[QUOTE=R.D. Silverman]Hi,

What's next after 11,212+? May I suggest 7,253- and 11,217-? (both easy)
7,253- has been among the first 5 holes in any table for the longest period
of time. It first appeared as a 5th hole back in July '98.

For a more ambitious project 2,719+ and 2,736+ would be nice. Along with
my doing 2,737+ and 2,749+ it would finish all base 2 numbers to 750 bits. :bounce:[/QUOTE]The simple answer is that we haven't decided yet. We try not to reserve stuff too far in advance and the current project still has a few weeks to run.

I thought Jens Franke was going to do 7,253- but perhaps I misremembered. Sam is well overdue his normal schedule for reminding us who is doing what, so perhaps we should ask him for an update.

We don't want to do anything too easy or sieving takes too little time and administrative costs outweigh computational cost.

Perhaps a more significant benchmark would be to clear the base 2 tables to 768 bits.


Paul

R.D. Silverman 2005-04-14 17:49

[QUOTE=xilman]

<snip>

Perhaps a more significant benchmark would be to clear the base 2 tables to 768 bits.


Paul[/QUOTE]

I am all for that!!!! :banana: :bounce:

frmky 2005-04-14 21:36

If you're ever up for a change of pace, the 151 digit cofactor of the 200 digit number 100^99+99^100 is still up for grabs. ECM is complete at the 50 digit level, plus 400 curves at B1=100M. Plus, it'd be interesting to see whether SNFS or GNFS would be better here. Based on GGNFS experience, it seems that the linear SNFS polynomial, 99^20 x - 100^20 would make things difficult.

Greg

xilman 2005-04-15 09:07

[QUOTE=frmky]If you're ever up for a change of pace, the 151 digit cofactor of the 200 digit number 100^99+99^100 is still up for grabs. ECM is complete at the 50 digit level, plus 400 curves at B1=100M. Plus, it'd be interesting to see whether SNFS or GNFS would be better here. Based on GGNFS experience, it seems that the linear SNFS polynomial, 99^20 x - 100^20 would make things difficult.

Greg[/QUOTE]
That's an idea!

I seemed to have started something with the x^y+y^x prime-finding project. Andrey Kulsha found lots of primes and strong pseudoprimes and began the XYYXF project to factor numbers of this type. (100,99).c151 has been one of his most wanted numbers for a long time now.

I'll give it some thought.


Paul

akruppa 2005-04-24 16:22

[QUOTE=frmky]Based on GGNFS experience, it seems that the linear SNFS polynomial, 99^20 x - 100^20 would make things difficult.[/QUOTE]

I'm curious... what would be difficult about it? From first inspection, it looks to me like the norms on both sides will be well balanced, the algebraic poly has very nice root properties, the skewness on both sides is close to 1 and even the resultant has a couple of nice small factors. I haven't actually tried sieving, but in theory this one looks like a winner to me...

Alex

xilman 2005-05-08 20:08

[QUOTE=R.D. Silverman]I am all for that!!!! :banana: :bounce:[/QUOTE]
"That" being clearing the base-2 tables to 768 bits.

There are currently six unreserved numbers in this category.

I just asked Sam Wagstaff to reserve 2,751+,c221 (aka the 221-digit cofactor of 2^751+1) for our next project. It has a 221-digit cofactor and so there is a fair chance that we may find a record penultimate factor of well over a hundred digits.

We won't start this one until the current number has finished sieving, in perhaps 2-3 weeks.

Next in line is yet to be decided, but doing the 153-digit cofactor of 2^760+1 by GNFS has some attraction.


Paul

JHansen 2005-05-09 06:18

[QUOTE=xilman]Next in line is yet to be decided, but doing the 153-digit cofactor of 2^760+1 by GNFS has some attraction.[/QUOTE]

OK. It would be fun to see a NFSNET GNFS again, I think.

Here's the polynomials a quick run with Kleinjungs tools turned up:

[CODE]skew: 1496831.27
norm: 4.08e+021
c5: 1860300
c4: -22190654371344
c3: -8418423029876628259
c2: 41938613797493867472132508
c1: 9910997260157184158283808947544
c0: -10607495285858568709187938891462034824
alpha: -6.86
Y1: 508011226531636067
Y0: -155820412163502072585879250581
Murphy_E 3.22e-012
M: 6467723141847565045770368595275819653284432337188636474118541913625083684674764941908019832620889202048853768204112271553122703814378535845220148970745
[/CODE]

I used parameters I have extrapolated from the values TK gives in his examples: p=7, n=4.3e21, N=1.07e19 and e=2.25e-12

--
Cheers,
Jes

dleclair 2005-05-11 18:45

One, two, three, four,
I declare a polynomial war:

[code]
BEGIN POLY #skewness 338426.24 norm 2.48e+021 alpha -6.56 Murphy_E 3.24e-012
X5 98172960
X4 -82316491050132
X3 -7016882552064350507
X2 6195174028086183212875569
X1 -1253129843099006975317373181033
X0 -21601946848639065371631884401124337
Y1 14056738126231207
Y0 -70491898205291098614634360840
M 168917999881140384023064067094596474191250689613877026744649091136283195101878644780477580371903270124175189817678537257352051829549020009739469904899683
END POLY
[/code]

I'm searching with:

pol51m0b -v -v -b 2_760P -p 7 -n 5e22 -a 0 -A 400000

and

pol51opt -b 2_760P -n 4.3e21 -N 1.07e19 -e 2.8e-12 -v -v

I've actually distributed the search over a three machines and am not quite finished the entire range. I'm about three quarters done and the polynomials above are the best I've found so far.

Jes, what norm bound (-n) did you use for pol51m0b?

-Don

JHansen 2005-05-11 19:26

[QUOTE=dleclair]One, two, three, four,
I declare a polynomial war:[/QUOTE] :lol:

[QUOTE=dleclair]I'm searching with:

pol51m0b -v -v -b 2_760P -p 7 -n 5e22 -a 0 -A 400000

and

pol51opt -b 2_760P -n 4.3e21 -N 1.07e19 -e 2.8e-12 -v -v[/QUOTE] I used

pol51m0b.exe -b 2760P -v -v -p 7 -n 3.32E+023 -a 0 -A 3000

and

pol51opt.exe -b 2760P -v -v -n 4.30E+021 -N 1.07E+019 -e 2.28E-012


[QUOTE=dleclair]I've actually distributed the search over a three machines and am not quite finished the entire range. I'm about three quarters done and the polynomials above are the best I've found so far.[/QUOTE] Ahh, that's cheating! :smile: 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.

Also notice, that your polynomials only score 0.62% higher than mine. :flex:

--
Cheers,
Jes

dleclair 2005-05-11 19:42

[quote]
I just let my home PC (AMD64 3400) loose before
[/quote]

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

[quote]
I will gladly do a "real" poly search if you want me to?
[/quote]

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

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

[QUOTE=dleclair]AMD64 3400?! Now who is cheating? :razz: 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[/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.

JHansen 2005-05-12 09:00

[QUOTE=dleclair]Jes, perhaps you and I can settle on some parameters to use and start dividing up the search space.[/QUOTE]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

[/CODE]

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. :smile:


--
Cheers,
Jes

dleclair 2005-05-12 19:30

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.
[/quote]

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

[/code]

-Don

R.D. Silverman 2005-05-12 19:53

[QUOTE=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[/QUOTE]


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 2005-05-13 04:07

[QUOTE=xilman]... clearing the base-2 tables to 768 bits.[/QUOTE]
Kazumaro Aoki just broke the c221 cofactor of 2,751+ into c221 = p55.c166 with ECM.

frmky 2005-05-13 06:38

[QUOTE=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.[/QUOTE]

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... :smile:

Greg

xilman 2005-05-13 08:25

[QUOTE=geoff]Kazumaro Aoki just broke the c221 cofactor of 2,751+ into c221 = p55.c166 with ECM.[/QUOTE]
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 2005-05-13 10:56

[QUOTE=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... :smile:

Greg[/QUOTE]

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 2005-07-05 03:28

[QUOTE=JHansen]:lol:

Ahh, that's cheating! :smile: 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[/QUOTE]

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 2009-03-15 04:22

[QUOTE=JHansen;54342]and those polynomials were found when I got up 7 hours later.
[/QUOTE]
Sorry to be off-topic, but you are so lucky that you sleep 7 hours. I normally get 3-5 hours of sleep.


All times are UTC. The time now is 22:12.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.