Probable prime

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare. In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare. Fermat's test for compositeness, which is based on Fermat's little theorem, works as follows: given an integer n, choose some integer a that is not a multiple of n; (typically, we choose a in the range 1 < a < n − 1). Calculate an − 1 modulo n. If the result is different from 1, then n is composite. If the result is 1, then n is likely to be prime; n is then called a probable prime to base a. A weak probable prime to base a is an integer that is a probable prime to base a, but which is not a strong probable prime to base a (see below). 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, up to 25 × 109, there are 11,408,012,595 odd composite numbers, but only 21,853 pseudoprimes base 2.:p. 1005 The number of odd primes in the same interval is 1,091,987,404. Probable primality is a basis for efficient primality testing algorithms, which find application in cryptography. These algorithms are usually 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<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 as tested is hence at most Pk, 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 numbers; but it is true for more refined notions of probable primality, such as strong probable primes (P = 1/4, Miller–Rabin algorithm), orEuler probable primes (P = 1/2, Solovay–Strassen algorithm).