Other

drummers-lowrise

Message boards : Generalized Fermat Prime Search : EFF offering \$150,000 prize for 1st 100M digit prime

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
GDB

Joined: 15 Nov 11
Posts: 298
ID: 119185
Credit: 4,068,931,952
RAC: 1,951,047

Message 109414 - Posted: 19 Aug 2017 | 14:07:01 UTC

Since EFF is offering \$150,000 prize for the 1st 100M digit prime, any chance of GFN-22 starting a 100M digit search soon?

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 14011
ID: 53948
Credit: 434,797,993
RAC: 849,502

Message 109415 - Posted: 19 Aug 2017 | 14:31:53 UTC - in response to Message 109414.

Since EFF is offering \$150,000 prize for the 1st 100M digit prime, any chance of GFN-22 starting a 100M digit search soon?

You might want to do some math and figure out how large b would need to be such that b^2^22+1 has more than 100 million digits. Keep in mind that Genefer won't be able to search beyond b=400,000,000. That's only 36 million digits.

____________
My lucky number is 75898524288+1

Rafael
Volunteer tester

Joined: 22 Oct 14
Posts: 912
ID: 370496
Credit: 551,992,413
RAC: 451,066

Message 109416 - Posted: 19 Aug 2017 | 14:38:23 UTC - in response to Message 109415.

Since EFF is offering \$150,000 prize for the 1st 100M digit prime, any chance of GFN-22 starting a 100M digit search soon?

You might want to do some math and figure out how large b would need to be such that b^2^22+1 has more than 100 million digits. Keep in mind that Genefer won't be able to search beyond b=400,000,000. That's only 36 million digits.

Also, n limited to 23, if I recall correctly. I remember OCL beta testing, an I think 23 was the max the program could handle (for whatever reason).

JeppeSN

Joined: 5 Apr 14
Posts: 1825
ID: 306875
Credit: 50,063,065
RAC: 13,866

Message 109417 - Posted: 19 Aug 2017 | 16:47:59 UTC - in response to Message 109415.

You might want to do some math and

If

b^(2^n) > 10^{99'999'999}

then

b > 10^{99'999'999 / 2^n}

We can create a table by plugging in:

n required b 22 694796579498971371357022.9 23 833544587589.0 24 912986.6 25 955.5 26 30.9

/JeppeSN

GDB

Joined: 15 Nov 11
Posts: 298
ID: 119185
Credit: 4,068,931,952
RAC: 1,951,047

Message 109422 - Posted: 20 Aug 2017 | 7:33:55 UTC

Do we know what is the max b GFN software can handle?

If the max b is something like 25, 26, or 27? Is it conceivable that we might start a 100M digit GFN within a year or two, and wouldn't we need to begin a manual sieve soon?

Honza
Volunteer moderator
Volunteer tester
Project scientist

Joined: 15 Aug 05
Posts: 1957
ID: 352
Credit: 6,146,998,179
RAC: 2,302,296

Message 109423 - Posted: 20 Aug 2017 | 7:59:36 UTC - in response to Message 109422.

Do we know what is the max b GFN software can handle?

If the max b is something like 25, 26, or 27? Is it conceivable that we might start a 100M digit GFN within a year or two, and wouldn't we need to begin a manual sieve soon?

In my opinion, this is far from reasonable. Let me elaborate...

There would be memory limit as well.
I can't remember exact numbers but today's GPUs are not up to the job.
Nor memory, nor performance...nor patience.

If n=21 now takes around single day to perform a test, and n=22 almost 4 (with pretty high b from days where n=22 was WR so there was extra incentive),
n=23 would be 16 days
n=24 ~64 days
n=25 ~256 days
n=26 ~1000 days
and n=27 around 10 years for a single test (!).
Almost all GPUs would die within 10 years of 24/7 running.
This is far from reasonable or sane.

Since we haven't found a single prime for n=20 yet (it would be Top12, n=21 Top6 and n=22 second largest know prime), there might be a problem finding any prime for n=24 and what about n=27 during next decade?

Let try to find any prime for n=20,21,22 in the meantime.

On a side note, being a bit more realistic, I'm pushing for GFNMega. There should be one about each b~250k based on historical finds.
____________
My stats

GDB

Joined: 15 Nov 11
Posts: 298
ID: 119185
Credit: 4,068,931,952
RAC: 1,951,047

Message 109425 - Posted: 20 Aug 2017 | 11:52:19 UTC

Unless it was possible to split a 1000 day GFN run. into 1000 1-day GFN runs and merge the results?

Neo
Volunteer tester

Joined: 28 Oct 10
Posts: 710
ID: 71509
Credit: 91,178,992
RAC: 0

Message 109426 - Posted: 20 Aug 2017 | 12:25:00 UTC - in response to Message 109425.

Unless it was possible to split a 1000 day GFN run. into 1000 1-day GFN runs and merge the results?

GDB,

Neo

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 14011
ID: 53948
Credit: 434,797,993
RAC: 849,502

Message 109427 - Posted: 20 Aug 2017 | 12:57:50 UTC - in response to Message 109425.

Unless it was possible to split a 1000 day GFN run. into 1000 1-day GFN runs and merge the results?

Yes, but not in the way you meant, and not in a useful way.

It's technically possible to do what you're asking -- but they can't be run in parallel and then merged. The 1000 tasks need to be run sequentially, with the output of each task being uploaded from one task to the server and then downloaded to the next task. Essentially, it's the same as when you suspend a task, the state is saved in the checkpoint file, and then you restart from the checkpoint. Except now we're restarting the computation on another user's computer.

Bear in mind that the checkpoint file for a theoretical n=26 would be about 640 MB.

Even if we wanted to do this (it's utterly ridiculous and makes the process slower, not faster, since you need to wait for wingmen at each step), the server doesn't have that kind of disk space and we can't afford the bandwidth.

____________
My lucky number is 75898524288+1

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 14011
ID: 53948
Credit: 434,797,993
RAC: 849,502

Message 109428 - Posted: 20 Aug 2017 | 13:14:29 UTC

GDB,

When GIMPS surpassed our GFN-22 search, meaning any prime we found in GFN-22 would fail to be the new largest known prime number, we investigated opening up GFN-23 so we could continue to search for the world's largest prime.

It was decided that was impractical at this time.

If searching n=23 for a prime in the high 20 million digit range was deemed impractical, then searching even higher n values for the 100 million digit prime is exponentially more impractical.

Unless something very significant changes with regard to either hardware or software, I don't expect us to be searching for a 100M digit prime any time soon. "Soon" in this context, means the next decade or two. Bear in mind that we've been searching n=22 for over 5 years and we're only now begin to talk about whether n=23 is reasonable. Realistically speaking, a 100M digit search would be run at n=25. We're a long ways from running an n=25 search.
____________
My lucky number is 75898524288+1

JeppeSN

Joined: 5 Apr 14
Posts: 1825
ID: 306875
Credit: 50,063,065
RAC: 13,866

Message 109429 - Posted: 20 Aug 2017 | 15:54:45 UTC

The most likely candidate for the award mentioned, is some Mersenne prime found by the Great Internet Mersenne Prime Search (GIMPS), just like the two previous prizes. It will take a long time before they reach the relevant sizes. But it will most probably take even longer before other projects can. GIMPS has special rules for how they share the money when (if) they can claim the next EFF award. /JeppeSN

GDB

Joined: 15 Nov 11
Posts: 298
ID: 119185
Credit: 4,068,931,952
RAC: 1,951,047

Message 109434 - Posted: 20 Aug 2017 | 18:09:31 UTC

I'd probably put my money on the software being modified to either speedup or allow splitting over the next 10 years. Is there a link to the GFN software source somewhere?

Honza
Volunteer moderator
Volunteer tester
Project scientist

Joined: 15 Aug 05
Posts: 1957
ID: 352
Credit: 6,146,998,179
RAC: 2,302,296

Message 109454 - Posted: 21 Aug 2017 | 6:21:40 UTC - in response to Message 109434.

I'd probably put my money on the software being modified to either speedup or allow splitting over the next 10 years. Is there a link to the GFN software source somewhere?

In Source code repositories, try Genefer link.
____________
My stats

Mr. Cool

Joined: 20 Jan 11
Posts: 160
ID: 82236
Credit: 758,564,854
RAC: 135,223

Message 109455 - Posted: 21 Aug 2017 | 7:24:54 UTC

Hi everyone.

Will quantum computers ever help us find larger and larger prime numbers? Or are they only useful at factoring numbers?

Thanks

axn
Volunteer developer

Joined: 29 Dec 07
Posts: 285
ID: 16874
Credit: 28,027,106
RAC: 0

Message 109484 - Posted: 22 Aug 2017 | 2:13:46 UTC - in response to Message 109428.

Realistically speaking, a 100M digit search would be run at n=25.

N=25 is _too big_ for a 100M search. N=24 would be the optimal. You have the huge range of 912986 < b <= 400m, which ranges from 100m digits to about 144m digits. N=25 will double the sizes and therefore make it 8 times harder to find a prime (except for a small patch at the beginning).

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 14011
ID: 53948
Credit: 434,797,993
RAC: 849,502

Message 109493 - Posted: 22 Aug 2017 | 12:45:19 UTC - in response to Message 109484.

Realistically speaking, a 100M digit search would be run at n=25.

N=25 is _too big_ for a 100M search. N=24 would be the optimal. You have the huge range of 912986 < b <= 400m, which ranges from 100m digits to about 144m digits. N=25 will double the sizes and therefore make it 8 times harder to find a prime (except for a small patch at the beginning).

True, I was assuming we'd run a normal search starting at the bottom of the b range. It could be done as you describe. Of course, if n=23 is impractical today, then n=24 is also impractical. Furthermore, running n=24 at such a high b would necessitate running one of the slower transforms.

Today, the software doesn't support running tests that large. Could it be changed to do so? Maybe. If the software supported those tests, could we run a 100M digit search? Yes. There's nothing stopping us, as a project, from doing so. Would we want to? Probably not. N=22 itself was a longshot, with a much more mundane goal, by comparison: Finding the worlds largest known prime number. We still haven't found an n=22. Nor an n=21. Nor an n=20. There's no proof any GFN primes exist that are that large. We would be searching for something that might not exist, and even if it does, will be exceptionally difficult to find. Chances are the energy costs for running the computers involved in that search will exceed the prize money long before a prime is found.
____________
My lucky number is 75898524288+1

Chara34122

Joined: 11 Feb 17
Posts: 95
ID: 490242
Credit: 19,956,127
RAC: 8,789

Message 112261 - Posted: 12 Dec 2017 | 1:50:10 UTC

Of course when(if) GFN-23 starts, I'll try it. But it reminds me standart FN-33 number (over 2500000000 digits) in some way. I even can't imagine what to do with this.

GDB

Joined: 15 Nov 11
Posts: 298
ID: 119185
Credit: 4,068,931,952
RAC: 1,951,047

Message 112262 - Posted: 12 Dec 2017 | 2:49:20 UTC - in response to Message 109493.

Since we might want to run GFN-23 within 5-10 years, doesn't that mean we should start running N=23 manual sieves now? So, we can have a decent amount of sieving done before we start running GFN-23?

JimB
Honorary cruncher

Joined: 4 Aug 11
Posts: 920
ID: 107307
Credit: 989,270,184
RAC: 150,909

Message 112274 - Posted: 12 Dec 2017 | 16:25:47 UTC - in response to Message 112262.

Since we might want to run GFN-23 within 5-10 years, doesn't that mean we should start running N=23 manual sieves now? So, we can have a decent amount of sieving done before we start running GFN-23?

There are no plans to run GFN 23 that I know of. So we're not going to be sieving it.

GDB

Joined: 15 Nov 11
Posts: 298
ID: 119185
Credit: 4,068,931,952
RAC: 1,951,047

Message 112275 - Posted: 12 Dec 2017 | 17:53:32 UTC

Since N=23 sieve isn't currently feasible, and N=21 sieve is close to being shutoff, why not reopen poorly sieved N=22?

Rafael
Volunteer tester

Joined: 22 Oct 14
Posts: 912
ID: 370496
Credit: 551,992,413
RAC: 451,066

Message 112277 - Posted: 12 Dec 2017 | 18:06:32 UTC - in response to Message 112275.

Since N=23 sieve isn't currently feasible, and N=21 sieve is close to being shutoff, why not reopen poorly sieved N=22?

Nov 1 2017, By JimB
Every six months I reevaluate the sieving levels, GFN16 will almost certainly reopen at that time. GFN19, GFN20 and GFN22 certainly will. For purposes of the computation, I look at what we'll check with genefer over the next five years. I think that makes a lot of sense, especially now that we have to appeal to users for money to keep the servers hosted.

Message boards : Generalized Fermat Prime Search : EFF offering \$150,000 prize for 1st 100M digit prime