Talk:Probable prime

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)

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

Comparing pseudoprime counts with composite numbers

The beginning of this article says, "For a fixed base a, it is unusual for a composite number to be a probable prime (that is, a pseudoprime) to that base. For example, there are only 21853 pseudoprimes base 2 that are less than 25*10^9 (see page 1005 of [1]) and 1091987405 primes less than 25*10^9."

The second sentence has nothing to do with the first: it compares pseudoprimes with primes, not with composites. The relevant comparison is the number of pseudoprimes compared to the number of composite numbers (say, up to 25*10^9). Even more relevant is the number of pseudoprimes compared to the number of odd composites because it's easy to determine whether or not an even number is prime.

In Mathematica notation,

Floor[n/2] - 1 = number of odd integers <= n, excluding 1 (1 is neither prime nor composite)

PrimePi[n] - 1 = number of odd primes <= n

Floor[n/2] - 1 - (PrimePi[n] - 1) = number of odd composites <= n

With n = 25*10^9, the result is that there are 11408012595 odd composite numbers up to 25*10^9, but only 21853 pseudoprimes base 2. So, only about .00019% of odd composites up to 25*10^9 are pseudoprimes base 2. MathPerson (talk) 21:06, 30 March 2017 (UTC)

Seeing no comments, I put this into the first part of the article.

Johasouerp to coumiila Agreed banikcoumilla johasouerport

Jouwelrana 0200019508794 2400:C600:338A:90CB:1:0:4DE4:E106 (talk) 18:38, 3 May 2023 (UTC)

probable misprint

@PrimeHunter: there should be a misprint soon after "21,853 pseudoprimes base 2". thanks. 151.29.149.29 (talk) 20:09, 18 February 2024 (UTC)

It looks right to me. What do you think is wrong? PrimeHunter (talk) 21:39, 18 February 2024 (UTC)

Because I read ":1005" at the exponent. I suppose that it is the corruption of a reference.@PrimeHunter: 151.29.149.29 (talk) 23:27, 18 February 2024 (UTC)

It's a correct reference using {{rp}} to specify page 1005. The same reference is used several times with different page numbers. Another time, please describe the alleged problem from the beginning. I spent time checking everything. PrimeHunter (talk) 00:07, 19 February 2024 (UTC)

Thanks again. Excuse me, but I am too aged to remain updated with these conventions.151.29.149.29 (talk) 07:30, 19 February 2024 (UTC)