From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Tue, 30 Aug 94 13:38:06 PDT
To: trollins@debbie.telos.com (Tom Rollins)
Subject: Re: Knuth Volume 2 Page 379
In-Reply-To: <9408301936.AA12752@debbie.telos.com>
Message-ID: <9408302037.AA13755@elf.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


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