Prime Numbers

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.

Don't ask how I found it, I was just fooling around.  Now:
   Is there some way to reverse the formula so we can insert and integer 
and get a prime number out?  Let me know, I am over excited.

                   _  .  _ ___ _  .  _
===-|)/\\/|V|/\/\ (_)/_\|_|\_/(_)/_\|_| Stop by for an excursion into the-===
===-|)||| | |\/\/  mud.crl.com 8888 (_) Virtual Bay Area!                -===

Well, for the mathematically curious, here are a few other interesting
prime number theroms:

For any number n which is prime, (2^n)-1 is also prime (Mersenne's theorem).

For any number n (2^(2^n))+1 is prime. (I might have that wrong, I don't
remember exactly)

For any number n, if the square root of (n!)+1 is an integer, it is also
prime.  (This is interesting, but rather useless in practice)

On Mon, 11 Apr 1994, Matthew J Ghio wrote:

> Well, for the mathematically curious, here are a few other interesting
> prime number theroms:
> 
> For any number n which is prime, (2^n)-1 is also prime (Mersenne's theorem).
> 
> For any number n (2^(2^n))+1 is prime. (I might have that wrong, I don't
> remember exactly)
> 
> For any number n, if the square root of (n!)+1 is an integer, it is also
> prime.  (This is interesting, but rather useless in practice)
> 

This is not "quite true"

1)   for (2^n)-1 to be prime, it is indeed necessary that n is prime
     (if n=pq then 2^p-1 divides 2^n-1)
     however (2^n)-1 is not prime for all prime n

     prime numbers of the form 2^n-1 are called Mersenne primes
     there are some 30 known Mersenne primes for the moment
     (could send interested people a list of the ones I know--see also 
     Knuth, volume 2 for some interesting stuff about primes)

2) (2^(2^n))+1 is certainly not true for all n, though I don't know
   any particularly values for which it doesn't hold (I thought
   2^128+1 was NOT a prime)

   primes numbers who happen to be of the form (2^(2^n))+1 are called 
   Fermat primes. Some pretty large ones are known (could send a list...)

3) I don't know about the third stated formula

Hope this straightens things out...

Frank.Vernaillen@rug.ac.be

>    primes numbers who happen to be of the form (2^(2^n))+1 are called 
>    Fermat primes. Some pretty large ones are known (could send a list...)

Please do.  My recollection was that none existed above 65537.

   Eli   ebrandt@hmc.edu

-----BEGIN PGP SIGNED MESSAGE-----

Eli Brandt writes:
> >    primes numbers who happen to be of the form (2^(2^n))+1 are called 
> >    Fermat primes. Some pretty large ones are known (could send a list...)

> Please do.  My recollection was that none existed above 65537.

Well, according to "An Introduction to the Theory of Numbers" by G.H.
Hardy and E.M. Wright you're correct.  They say the largest n for which
the Fermat prime F_n has been found is F_4 = 2^(2^4)+1 = 65537.  Of
course, this book was written in 1938 so the situation could have
changed since then.

F_n is known to be composite for
	7<=n<=16, n=18, 19, 21, 23, 36, 38, 39, 55, 63, 73
and others.  Not a very successful conjecture for Fermat, I suppose...

- -- 
Dan McGuirk						  djm@asu.edu
 When cryptography is outlawed, pkog ofklsjr vija fhsl ciehgoabykze.

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQBVAgUBLat8kI6/chyd1nKpAQEqQQH/YUdds9T92d8jdeSdDYl3uiKS/otGARJe
YZ/GOjrf3fSQsCqQ2zBYSW30aX+zyJRhvxTu6B9h91IphZHPq6hKzw==
=4JUh
-----END PGP SIGNATURE-----

>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