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! -===
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
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
-----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-----
participants (6)
-
Dan McGuirk -
Eli Brandt -
Frank Vernaillen -
Jeremy Cooper -
Matthew J Ghio -
Phil Karn