number theory number theory
-----BEGIN PGP SIGNED MESSAGE----- All right, a number theory discussion!
The integer N is prime if: 2^N - 2 --------- N is an integer.
Well, this is false. The above formula is derived from Fermat's Little Theorem, or Euler's Generalization of Fermat's Little Theorem. a^(n-1) = 1 mod n, n prime, gcd(a,n) = 1 ==> a^n = n mod n a^n - n = kn, for k some integer (a^n - n)/n = k, for k some integer now sub in a = 2. However, the converse of this is not true (n isn't necessarily prime if it satifies the formula). Composities that satisfy this are called pseudoprimes. For example, for a = 2, n = 341 satisfies the relation, so 341 is a pseudoprime base 2. Now it works "most" of the time, and in fact one method of testing large integers for primality is to choose a whole bunch of a's and plug in n. If a^(n-1) mod n != 1, the number is composite and can be rejected. But, if a^(n-1) mod n == 1, you can only be 50% sure n is prime. (Roughly speaking; Phil Karn notes that the PGP docs indicate a 50%, I've seen proofs that this pseudoprime test fails 50% of the time, etc. But these are upper bounds; the real percentage seems much lower and I haven't seen a tighter bound on it). There is a "strong psuedoprime" test, in which failure occurs for at least 25% of integers in the range, thus the probability that a composite will pass is at most 25%. Even better is Lucas' test, but it runs a bit slow. However, you can be unlucky and pick a Carmichael number, which will pass the pseudoprime test for all bases relatively prime to n (for all a such that gcd(a,n) = 1). Ray Cromwell advises to choose n = 561, the smallest Carmichael number (an excellent choice!) Carmichael numbers exist, they are relatively rare, formulas exists for generating some of them... Eric Hughes mentions that 1729 is the next Carmichael number... not quite true. 1105 is the next Carmichael number. (But congrats Eric for even remembering the third one!) ;) Now, some other topics:
For any number n which is prime, (2^n)-1 is also prime (Mersenne's theorem).
Hm... some confusion here. A Mersenne prime is of this form (2^n) - 1 where n is prime, but not all number this formula generates are primes. Mersenne primes are related to perfect numbers. An example of a composite of this form: for n = 11, 2^11 - 1 = 2047 = 23 * 89
For any number n (2^(2^n))+1 is prime. (I might have that wrong, I don't remember exactly)
Well, no. These number are Fermat numbers, and while the first 5 (n=0 to n=4) but Euler showed that the Fermat number for n=5 is composite. As an aside, Fermat numbers satisfy the pseudoprime test.
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)
A couple of issues here: I think you may be remembering a different theorem, a consequence of Wilson's theorem. Wilson's theorem says: for any prime p, (p-1)! = -1 mod p The theorem I think you are referring to is: if P is the product of the remainders relatively prime to m, then P = +/- 1 mod m; +/- = plus or minus The congruence is +1 except in three cases: 1) m = 4 2) m = p^b (m is a power of an odd prime) 3) m = 2p^b (m is twice the power of an odd prime) I'm still trying to either prove or disprove your claim! Two followups relating the the original formula posted:
For any number a, 1<a<=n, n! mod a == 0; therefore, n!+1 mod a == 1. n!+1 is prime. Prime numbers don't have integral square roots.
Good analysis, except for the "n! + 1 is prime" part. The only thing you can say is n!+1 has no factors <= n. For example, n = 4, n!+1 = 25 = 5 * 5.
Well, it was quoted from memory, so it's possible that I made an error, but it seems to work as stated... For example : (4!+1)^(1/2)=5 (5!+1)^(1/2)=11 (7!+1)^(1/2)=71 I can't find a value which produces a result that is a non-prime integer. (Of course that doesn't prove that there isn't one.)
Still working on this... ;) -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLanNNYOA7OpLWtYzAQF10wP9GExbaoloiXqFe7AtXb/UzUHXhW3VDC1b mfD0RhgK2i0Dr05RW5FCvj/9i7Jxhrd3E26hTe5g4WckvIcvp+GWhE/5fkdtVMA9 THutX1ukGO/5qCxSRT4hVCeXStAz7tunkF3fcEQjPe8pSSvKxN8tw/wIZzclRDRx JDE4HYRhAz0= =OW8h -----END PGP SIGNATURE-----
Some anonymous agent wrote:
Eric Hughes mentions that 1729 is the next Carmichael number... not quite true. 1105 is the next Carmichael number. (But congrats Eric for even remembering the third one!) ;)
I suspect Eric's memory was influenced by his memories of last Saturday night, after the Cyperpunks meeting and after the Dave Emory lecture a half dozen of us saw that evening. We all decided to attend the midnight showing at the Stanford Theater of a new Indian film, "Rendezvous with Ramanujan," based of course on the famous Arthur C. Clarke novel, and directed by noted British director, G. H. Hardy (no relation to Norm Hardy). Our taxi had the license plate number "RSA-1729," which we took to be a pun about the next big factoring project. After all, 1729 is a rather unremarkable number. The taxi driver, an unemployed mathematician named Ted Streleski, was heard muttering, "Some squares, some cubes." --Klaus! von Future Prime (channeled by Tim May) -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."
What estimates exist for the density of large Carmichael numbers, say 1000 bits long? I.e., what's the probability of running into one by accident when generating primes by the usual technique of picking a random starting point and searching up until you find a number that passes seive or small factor tests and a few iterations of Fermat's test? Are other probability tests like Miller-Rabin any more provably likely to detect these? I'm currently playing with the Miller-Rabin test. Boy, is modular exponentiation a pig (at least the routine in RSAREF). Phil
The figure I have for the Carmichael numbers is x^(.1), where .1 is approximate. Ray has the exponent at 2/7. The exact one doesn't matter so much, because compared to the density of primes (x/ln x), these are both extremely small. The chance of picking a Carmichael number is very small. But that's not the relevant density. The problem with RSAREF's prime testing is that it will find pseudoprimes base 2. Carmichael numbers are pseudoprimes to any base, but that's unneeded for the RSAREF test. What is needed is the density of pseudoprimes base 2. I don't know that figure. I don't know that anybody does. I would really suggest that someone with access to Mathematica or Maple do an experiment to find out how many non-primes the RSAREF algorithm passes. Carmichael numbers do not, generally, pass the Miller-Rabin test. Some might; I'll bet it's an open question. Eric
If a^(n-1) mod n != 1, the number is composite and can be rejected. But, if a^(n-1) mod n == 1, you can only be 50% sure n is prime.
I should point out that the standard argument that picking 'k' different values for 'a' and then calculating the probability as (1/2)^k is fallacious. This would be true if the probabilities were independent, but they aren't. There was a paper on this about five years ago whose awareness has not been yet widespread. I no longer have the reference. For everybody that wants to really know about this, find out about the Miller-Rabin test.
(Roughly speaking; Phil Karn notes that the PGP docs indicate a 50%, I've seen proofs that this pseudoprime test fails 50% of the time, etc. But these are upper bounds; the real percentage seems much lower and I haven't seen a tighter bound on it).
The 50% figure is easy to show with some considerations about quadratic residues. Tightening the bound is much more difficult. Eric
participants (4)
-
catalyst-remailer＠netcom.com -
hughes＠ah.com -
Phil Karn -
tcmay＠netcom.com