From: Phil Karn <karn@qualcomm.com>
Date: Sun, 10 Apr 94 20:37:23 PDT
To: jeremy@crl.com
Subject: Re: Prime Numbers
In-Reply-To: <Pine.3.87.9404101801.A23956-0100000@crl.crl.com>
Message-ID: <199404110337.UAA02462@servo.qualcomm.com>
MIME-Version: 1.0
Content-Type: text/plain


>I found something interesting that I have not proven, but it has not 
>failed yet:

>The integer N is prime if:

>   2^N - 2
>  ---------
>      N              is an integer.

You seem to have rediscovered Fermat's Little Theorem, or something
very much like it. See page 203 of Schneier, which says:

	If m is a prime, and a is not a multiple of m, then Fermat's Little
	Theorem says

	a^(m-1) [is congruent to] 1 (mod m)

This seems to be the basis of most of the primality testing algorithms
I've been studying lately. For example, the FermatTest() function in
RSAREF computes 2^a mod a and compares the result to 2. This is done
only if the candidate prime has already been verified not to be a multiple
of 3, 5, 7 or 11.

PGP works a little harder. After verifying that the candidate prime is
not divisible by primes up into the 4-digit range (using a lookup
table the size of which is a compile-time option), it computes
Fermat's formula up to four times using the values 2, 3, 5 and 7 for
'a'.

The PGP source contains a comment that the Fermat test is much more than
50% effective at detecting composites, but gives no actual figures.
Can anyone comment on this?

I'm currently interested in prime generation because I'm working on a
Diffie-Hellman based IP security protocol (using RSAREF). As long as
the DH modulus is well chosen it can be relatively static and shared
by many people. Therefore I don't mind spending quite a bit of CPU
time on this if necessary to do a good job.

As I understand Brian LaMacchia's 1991 results on the discrete log
problem (see http://martigny.ai.mit.edu/~bal/field.ps), the prime
modulus p used with Diffie-Hellman should be well above 512 bits long
(I'm currently planning 1024) and (p-1)/2 should also be
prime. Anybody know of any more recent results?

Phil