[RC5] Big prizes for finding prime numbers.

Martin Harvey martin at aziraphale.demon.co.uk
Tue Apr 6 20:22:54 EDT 1999

Matthew Gabeler-Lee wrote:
> 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.

That sounds like Pollard's Rho algorithm to me. The algorithm turns out
to be very simple (about 5 or 6 lines), at least when multiplying
numbers that the CPU can handle natively... for decent sized primes, one
has to use the fast fourier transform to multiply the numbers, and it
gets a lot more complicated. The proof of why it works is quite
complicated if one wants a rigorous justification. More info can be
found in "Introduction to Algorithms" by Cormen Leiserson & Rivest,
published by Addison Wesley (soryy I don't have the ISBN to hand). Note
that just like all books that say "An Introduction to", it's about three
feet thick, and hideously complicated :-)


Martin Harvey.
Takeoff is optional.
Landing (sooner or later) is mandatory.

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