Probable prime

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&ndash;Rabin algorithm), or Euler probable primes (P = 1/2, 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. ==Variations==

An Euler probable prime to base a is an integer that is indicated prime by the somewhat stronger theorem that for any prime p, a(p−1)/2 equals (\tfrac{a}{p}) modulo p, where (\tfrac{a}{p}) is the Jacobi symbol. An Euler probable prime which is composite is called an Euler&ndash;Jacobi pseudoprime to base a. The smallest Euler-Jacobi pseudoprime to base 2 is 561. There are 11347 Euler-Jacobi pseudoprimes base 2 that are less than 25·109. The Fermat test may alternatively be improved by using the fact that the only square roots of 1 modulo a prime are 1 and −1. Write n = d · 2s + 1, where d is odd. The number n is a strong probable prime (SPRP) to base a if: : a^d\equiv 1\pmod n,\; or : a^{d\cdot 2^r}\equiv -1\pmod n\text{ for some }0\leq r\leq s-1. \, A composite strong probable prime to base a is called a strong pseudoprime to base a. Every strong probable prime to base a is also an Euler probable prime to the same base, but not vice versa. There are also Lucas probable primes, which are based on Lucas sequences. A Lucas probable prime test can be used alone. The Baillie–PSW primality test combines a Lucas test with a strong probable prime test. Example of testing for a strong probable prime To test whether 97 is a strong probable prime base 2: • Step 1: Find d and s for which 96=d\cdot 2^s, where d is odd • Beginning with s=0, d would be 96 • Increasing s, we see that d=3 and s=5, since 96=3\cdot 2^5 • Step 2: Choose a, 1 . We will choose a = 2. • Step 3: Calculate a^d \bmod n, i.e. 2^3 \bmod 97. Since it isn't congruent to 1, we continue to test the next condition • Step 4: Calculate 2^{3\cdot 2^r} \bmod 97 for 0 \leq r . If it is congruent to 96, 97 is probably prime. Otherwise, 97 is definitely composite • r=0: 2^3 \equiv 8 \pmod{97} • r=1: 2^6 \equiv 64 \pmod{97} • r=2: 2^{12} \equiv 22 \pmod{97} • r=3: 2^{24} \equiv 96 \pmod{97} • Therefore, 97 is a strong probable prime base 2 (and is therefore a probable prime base 2), and it is in fact prime. ==See also==