Knuth Volume 2 Page 379
Hello, I have a little question about some math algorithms. People have talked in alt.security.pgp about the Miller Test and the Miller-Rabin Test. I am getting ready to improve PGP's testing of potential prime numbers and have been looking for a good algorithm. After reading some in Knuth Volume 2, I have come across Algorithm P on page 379. Is this algorithm in fact the Miller-Rabin Test ??? Thanks, Tom Rollins <trollins@debbie.telos.com>
Tom Rollins wrote:
I am getting ready to improve PGP's testing of potential prime numbers and have been looking for a good algorithm.
Heh, I thought this same thing a few months ago. As it turns out, Miller-Rabin and a modified Lucas test has already been coded up for the next release of PGP.
After reading some in Knuth Volume 2, I have come across Algorithm P on page 379. Is this algorithm in fact the Miller-Rabin Test ???
I don't have a copy of this handy, or I'd tell you. Basically, Miller-Rabin is similar Fermat except you continue testing and divide by two. The quick, dirty, and ugly explanation ;) -- Karl L. Barrus: klbarrus@owlnet.rice.edu 2.3: 5AD633; D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 2.6: 088C8F21; 97 73 9E 8B 98 3E DD B5 E8 97 64 7E 20 95 60 D9 "One man's mnemonic is another man's cryptography" - K. Cooper
participants (2)
-
Karl Lui Barrus -
trollins＠debbie.telos.com