# [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