> The EFF (Electronic Frontier Foundation) is offering prizes up to $250,000
> for finding huge prime numbers.
No problem with that...
> The first prize is $50,000 for finding a
> prime number larger than 1 million decimal digits,
We ought to find one of these sooner or later. In fact I think we are
already "overdue". OK, we *don't* know the true distribution of
Mersenne primes with more than a million decimal digits (if indeed
there are any ... though this seems very likely, it isn't proved!)
> the highest prize is
> $250,000 for finding a prime number larger than 1 billion decimal digits.
Good luck to anyone who wants to chase after this!
LL testing of Mersenne numbers seems to offer the best chance of
success, however there are some other types of numbers (e.g.
Proth numbers) which can be tested almost as quickly (in
principle).
The trouble is that, since testing a 1 million digit Mersenne number
takes a few days on a system which is "fast" by current standards,
a 1 billion digit number is going to take A Long Long Time. Using
64-bit floating-point arithmetic the transform size is going to be
1000 times as large, i.e. 160M as opposed to 160K, and the
memory required will be huge, you will need gigabytes of RAM to
store the work vectors. Assuming that your 160M transform is as
efficient as the existing code, and that you can execute it without
page faulting all over the place, it will still take 1000 times as long
to compute each iteration, i.e. a couple of minutes per iteration on
a fastish Pentium II system. With about 3 billion iterations to
compute, that works out at approx. 6 billion minutes = 100 million
hours = 4 million days = 10,000 years to complete the test.
(Forgive me for using single digit precision ... I'm trying to make a
point rather than an exact computation)
The EFF's $250,000 would seem to be safe enough from Prime95!
To really attack the problem, you'd need a great many very fast
processors (possibly specialised hardware), and a variant of the
FFT enabling each iteration to be distributed across the processors
in a massively parallel manner. It probably isn't impossible to
construct such a system, but, on the other hand, at the moment it
would most likely cost a great deal more than $250,000, and would
still take a very long time to test M(~3 billion). It would probably be
cost-effective, instead of rushing into hardware now, to wait a few
years (with the money in the bank earning interest, instead of in
rapidly-self-obsoleting silicon) then buy much more powerful
hardware with the (bit more) money in your pocket, and still finish
the computation sooner.
I see the EFF "prize" as being an incentive for research groups
(probably noone else, except the Chudnovskys, if they don't count
as "professional researchers") could mount a realistic challenge at
the current time) to develop hardware, which would be applicable to
other tasks. There may be an "ulterior motive" - if that sort of
computing power was available to government agencies, messages
encrypted using strong techniques and 1024 bit keys would be
about as hard to read as plain text...
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
