[RC5] Big prizes for finding prime numbers.

Chuck Todd 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)


>
>MH.
>
>--
>Martin Harvey.
>http://www.harvey27.demon.co.uk/mch24/
>Takeoff is optional.
>Landing (sooner or later) is mandatory.


   Chuck Todd
   


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: noconv

iQCVAwUBNxLyDhkrbp1p5jjhAQHcKAP9E+o67q+CuvjhA5gFYznHcD3xqHaY+IY4
bsBtN/npo6wHw78RHXLJ2APTuOU/hrfvobkEYUvWfza+tO8jCZzxPfAwC2dck7P8
nwauCHiQRzXI1/IaTfyt5fABlUKRxi1RdKyRC54+HJmtuw5GL57T5bsgEqYw/moE
30LsxPb31+M=
=5wKM
-----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 mailing list