Editing Probable prime (section)

==Properties==
Probable primality is a basis for efficient [[primality testing]] [[algorithm]]s, which find application in [[cryptography]]. These algorithms are usually [[randomized algorithm|probabilistic]] in nature. The idea is that while there are composite probable primes to base ''a'' for any fixed ''a'', we may hope there exists some fixed ''P''&lt;1 such that for ''any'' given composite ''n'', if we choose ''a'' at random, then the probability that ''n'' is pseudoprime to base ''a'' is at most ''P''. If we repeat this test ''k'' times, choosing a new ''a'' each time, the probability of ''n'' being pseudoprime to all the ''a''s tested is hence at most ''P<sup>k</sup>'', and as this decreases exponentially, only moderate ''k'' is required to make this probability negligibly small (compared to, for example, the probability of computer hardware error).

This is unfortunately false for weak probable primes, because there exist [[Carmichael number]]s; but it is true for more refined notions of probable primality, such as strong probable primes (''P''&nbsp;=&nbsp;1/4, [[Miller&ndash;Rabin primality test|Miller&ndash;Rabin algorithm]]), or
Euler probable primes (''P''&nbsp;=&nbsp;1/2, [[Solovay–Strassen primality test|Solovay&ndash;Strassen algorithm]]).

Even when a deterministic primality proof is required, a useful first step is to test for probable primality. This can quickly eliminate (with certainty) most composites.

A PRP test is sometimes combined with a table of small pseudoprimes to quickly establish the primality of a given number smaller than some threshold.