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