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)

[edit] Is definition of string pseudoprime correct ?

The main article has: "A strong probable prime to base a is called a strong pseudoprime to base a."

Surely a pseudoprime (for some criterion) is a composite number which passes the criterion. The word 'composite' is missing from this definition. My understanding is that "probable prime" menas a number that passes the criterion; it is very likely to be a prime, but if proved composite is then a pseudoprime for that criterion.

[This is the first time I have ever added to Wikipedia - I thought it better to raise a 'talk' comment rather than wade in and edit the page].

Jsryork 12:16, 18 April 2007 (UTC) jsryork