Talk:Probable prime

From Wikipedia, the free encyclopedia

The paragraph on cryptography is misguided. Typical probabilistic primality testing algorithms (e.g. Rabin-Miller) detect all composites, including all sort of pseudoprimes. The probability distribution in question is not over the input numbers (prime/composite), but over an additional sequence of "coin tosses" the algorithm does. Thus, a statement like "the algorithm is correct with probability 3/4" does not mean it will miss 1/4 of composites; it means that for any given composite, if you run the algorithm independently multiple times, about 3/4 of the runs will detect the number as being composite. However, such algorithms often do use some notion of pseudoprimeness; typically, it works by choosing a random a, and testing the input for being base-a pseudoprime. EJ 09:56, 24 Aug 2004 (UTC)

I've added the link to Miller-Rabin primality test. Feel free to edit the article to fit (and also pseudoprime). I would, but I'm not sure how to reword everything. Elektron 19:55, 2004 Aug 30 (UTC)

OK. I hope the wording is more clear now. -- EJ 15:19, 1 Sep 2004 (UTC)