### Re: FW: Fermat's primality test vs. Miller-Rabin

* Charlie Kaufman: The probability of a single run of Miller-Rabin or Fermat not detecting that a randomly chosen number is composite is almost vanishingly small. How do you chose a random integer, that this, based on which probability distribution? 8-) Anyway, one can show that for some fixed number, the probability that one run of the Miller-Rabin algorithm fails (i.e. reports potentially prime for a composite) does not exceed 1/4. Knuth gives a proof in an exercise in Volume 2 of The Art of Computer Programming, including an example that the 1/4 bound is pretty good. However, this answers a slightly different question. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### FW: Fermat's primality test vs. Miller-Rabin

(resending after bounce) -Original Message- From: Charlie Kaufman Sent: Tuesday, November 08, 2005 3:11 PM To: 'Travis H.'; 'cryptography@metzdowd.com' Subject: RE: Fermat's primality test vs. Miller-Rabin Is that the distinction that makes Miller-Rabin a stronger primality test? Yes. The Miller-Rabin test will fail to detect that a Carmichael number is composite 25% of the time. Thus, repeating the Miller-Rabin test many times gives ever greater confidence. Fermat's test will fail to detect that a Carmichael number is composite 100% of the time, so repeating it doesn't help (in the fringe case of a Carmichael number). In practice, the probability of randomly choosing a Carmichael number of size 250 bits is vanishingly small. The probability of a single run of Miller-Rabin or Fermat not detecting that a randomly chosen number is composite is almost vanishingly small. I've heard but not confirmed a figure of one failure in 20 million. I've never heard an estimate of the probability that two runs would fail to detect the composite. It couldn't be better than one failure is 20 million squared or worse than one in 80 million. --Charlie Kaufman -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Travis H. Sent: Tuesday, November 08, 2005 3:05 AM To: cryptography@metzdowd.com Subject: Fermat's primality test vs. Miller-Rabin In Practical Cryptography, Schneier states that the you can prove that when n is not a prime, a certain property of a mod n holds for at most 25% of possible values 1 a n. He later states that Fermat's test can be fooled by Carmichael numbers, and finally he basically says that Miller-Rabin is based on Fermat's test. It appears that Fermat's test can be fooled by Carmichael numbers, whereas Miller-Rabin is immune, but I'm not sure why. It appears that M-R tests that just before the squaring of a that produces a residue of 1, is the residue n-1. Apparently that's not true for most bases of Carmichael numbers. Is that the distinction that makes Miller-Rabin a stronger primality test? It's amazing how many words that took to state, and I didn't even specify the squaring process. -- http://www.lightconsulting.com/~travis/ -- We already have enough fast, insecure systems. -- Schneier Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]