[RC5] Big prizes for finding prime numbers.
Matthew Gabeler-Lee
msg2 at po.cwru.edu
Sun Apr 4 01:50:15 EST 1999
I'm not up on the names of prime number finding algorithms, but in a book I got a
while ago (The New Turing Omnibus by A. K. Dewdney), it presents an algorithm for
finding probable primes. It uses the concept of a "witness to the compositeness
of n." Such a number w is any number for which (w^(n-1))%n != 1 (% being the
modulus operator as defined in C/C++) or, for some integer k, (n-1)/(2^k) is an
integer and 1 < gcd(w^n - 1, n) < n where gcd is the greatest common denominator
function. Furthermore, for any composite (non prime) number n, more than half
the numbers in {2, 3, ... , n-1} are witnesses to the compositeness of n. One
can compute in polynomial time whether a number w is a witness to the
compositeness of n. If one checks m potential witnesses, the probability of
missing a witness (and falsely reporting a prime) is 1-(1/2)^m. By this
algorithm, on a computer that was probably on the class of a 486 (judging by the
hardware he references elsewhere, and by the publication date), the author was
able to find that 2^400 - 593 was prime with a probability of 1-10^(-400) in a
few minutes! While one would probably need to prove that a number was prime,
this could, in very short order, determine where distributed.net should place its
efforts, and thus save it quite a bit of time.
Jeff Woods wrote:
> 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.
--
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