[RC5] Big prizes for finding prime numbers.
ctodd at magiclink.com
Tue Apr 13 01:28:14 EDT 1999
-----BEGIN PGP SIGNED MESSAGE-----
On Tue, 06 Apr 1999 19:22:54 +0100, Martin Harvey wrote:
>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 :-)
ISBN 0-262-03141-8 (MIT Press)
ISBN 0-07-013143-0 (McGraw-Hill)
>Takeoff is optional.
>Landing (sooner or later) is mandatory.
-----BEGIN PGP SIGNATURE-----
-----END PGP SIGNATURE-----
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5