[RC5] Big prizes for finding prime numbers.
Jeff Woods
jeff at telix.com
Fri Apr 2 17:11:21 EST 1999
Each test of a potential prime number, using the standard Lucas-Lehmer test
for Mersenne numbers (which are the easiest such numbers that large to
test), takes about 3 weeks on a Pentium-II 233. That's for the $50,000
prize. As the size of the prime to test goes up, so does the FFT table
required, and thus, the time to test, which ALSO goes up since the number
of "keys" that need to be examined is a function of the size of the number.
E.g. The numbers are all in the format 2^p-1. Each such number
requires p-3 calculations, massive numbers done by Fast Fourier Transforms.
Thus, as p gets bigger, the time to test 2^p-1 gets bigger in a
faster-than-linear function, since not only does P increase, but the size
of each calculation increases, too.
A good example of the status of the search for such numbers, and the site
already focused on a "distributed" search, is at:
http://www.mersenne.org/status.htm
There are approximately 380,000 numbers that "could" be the one that pays
off that much money. That's 1,140,000 CPU-weeks, or about 21,923 CPU
years. If distributed.net focused on this for one year, it is a virtual
certainty that we (or mersenne.org) would find such a number and bank
$50,000. (This assumes there are such numbers that exist).
At 06:25 PM 4/1/99 -0500, you wrote:
>If we were to win either prize, it would certainly put enough in d.net's
>bank account to buy some new equipment or help out with Deep Crack (or
>whatever they called it). If someone could forecast how long it would
>take us to finish one of these contests, we could figure out whether
>it's worth putting rc5 on hiatus....
>
>-Gabe
>
>Jeff Gilchrist wrote:
>>
>> http://www.wired.com/news/news/technology/story/18863.html
>>
>> Here is an interesting story of the latest distributed computing contest.
>> The EFF (Electronic Frontier Foundation) is offering prizes up to $250,000
>> for finding huge prime numbers. The first prize is $50,000 for finding a
>> prime number larger than 1 million decimal digits, the highest prize is
>> $250,000 for finding a prime number larger than 1 billion decimal digits.
>>
>> The GIMPS project which is currently doing a distributed effort to find
>> Mersenne primes has found a 900,000 digit number so the next one they find
>> should be over the 1 million digit barrier.
>>
>> The actual EFF page that describes the contest is here:
>> http://www.eff.org/coop-awards/
>>
>> Maybe distributed.net would be interested in doing this as another project?
>>
>> --
>> -= Jeff Gilchrist =- E-mail: jeffg at cips.ca
>>
>> --
>> To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
>> rc5-digest subscribers replace rc5 with rc5-digest
>
>--
>To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
>rc5-digest subscribers replace rc5 with rc5-digest
>
>
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5
mailing list