Primality test
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests. Products past 10 \times 10 are the reverse of products that appeared earlier. For example, 5 \times 20 and 20 \times 5 are the reverse of each other. Further, that of the two divisors, 5 \leq \sqrt{100} = 10 and 20 \geq \sqrt{100} = 10 . This observation generalizes to all n : all divisor pairs of n contain a divisor less than or equal to \sqrt{n} , so the algorithm need only search for divisors less than or equal to \sqrt{n} to guarantee detection of all divisor pairs. Also, 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by the Fundamental Theorem of Arithmetic. Therefore the algorithm need only search for prime divisors less than or equal to \sqrt{n} . For another example, consider how this algorithm determines the primality of 17. One has 4 , and the only primes \leq \sqrt{17} are 2 and 3. Neither divides 17, proving that 17 is prime. For a last example, consider 221. One has 14 , and the primes \leq \sqrt{221} are 2, 3, 5, 7, 11, and 13. Upon checking each, one discovers that \frac{221}{13} = 17 , proving that 221 is not prime. In cases where computing the list of primes \leq \sqrt{n} is not feasible, all numbers between 2 and \sqrt{n} can be simply (and slowly) checked for divisors. A simple improvement is to test divisibility by 2 and by just the odd numbers between 3 and \sqrt{n} , since divisibility by an even number implies divisibility by 2. This method can be improved further. Observe that all primes greater than 5 are of the form 6k + i for a nonnegative integer k and i \in \{1, 5\} . Indeed, every integer is of the form 6k + i for a positive integer k and i \in \{0, 1, 2, 3, 4, 5\} . Since 2 divides 6k, 6k + 2 , and 6k + 4 , and 3 divides 6k and 6k + 3 , the only possible remainders mod 6 for a prime greater than 3 are 1 and 5. So, a more efficient primality test for n is to test whether n is divisible by 2 or 3, then to check through all numbers of the form 6k + 1 and 6k + 5 which are \leq \sqrt{n} . This is almost three times as fast as testing all numbers up to \sqrt{n} . Generalizing further, all primes greater than p_{m} (the m th prime number) are of the form p_{m}\# \cdot k + i , where \{k, i \in \mathbb{Z} \mid 0 \leq i and p_{m}\# is the primorial – the product of the first m primes. For example, consider p_{3}\# = 2 \cdot 3 \cdot 5 = 30 . All integers are of the form 30k + i , where \{k, i \in \mathbb{Z} \mid 0 \leq i . Now, 2 divides 0, 2, 4, \dots, 28 , 3 divides 0, 3, 6, \dots, 27 , and 5 divides 0, 5, 10, \dots, 25 . Thus all prime numbers greater than 30 are of the form 30k + i for i \in \{1, 7, 11, 13, 17, 19, 23, 29\} . Of course, not all numbers of the form p_{m}\# \cdot k + i with i coprime to p_{m}\# are prime. For example, 19 \cdot 23 = 437 = 210 \cdot 2 + 17 = p_{4}\# \cdot 2 + 17 is not prime, even though 17 is coprime to p_{4}\# = 2 \cdot 3 \cdot 5 \cdot 7 . While \lim_{m \to \infty}\frac{\phi\left(p_{m}\#\right)}{p_{m}\#} = 0 , where \phi\left(m\right) is the Euler totient function, checking for divisibility by all primes that are less than p_{m}\# is still needed. Observations analogous to the preceding can be applied recursively, giving the Sieve of Eratosthenes. One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental m against all known primes \leq \sqrt m ). Then, before testing n for primality with a large-scale method, n can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped. A simple but inefficient primality test uses Wilson's theorem, which states that p is prime if and only if: (p - 1)! \equiv -1 \pmod{p} Although this method requires about p modular multiplications, rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods. if n = 341 and a = 2, then 2^{340} \equiv 1\pmod{341} even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of ). There are only 21853 pseudoprimes base 2 that are less than 2.5 (see page 1005 of ). This means that, for n up to 2.5 , if 2 n −1 (modulo n) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes. Some composite numbers (Carmichael numbers) have the property that a n − 1 is 1 (modulo n) for every a that is coprime to n. The smallest example is n = 561 = 3·11·17, for which a 560 is 1 (modulo 561) for all a coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographic algorithm.
Miller–Rabin and Solovay–Strassen primality test
The Miller–Rabin primality test and Solovay–Strassen primality test are more sophisticated variants, which detect all composites (once again, this means: for every composite number n, at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers a are witnesses of compositeness of n). These are also compositeness tests. The Miller–Rabin primality test works as follows: Given an integer n, choose some positive integer a s d = n − 1, where d is odd. If a^{d} \not\equiv \pm 1\pmod{n} and a^{2^rd} \not\equiv -1\pmod{n} for all 0 \le r \le s - 1, then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime. The Miller–Rabin test is a strong probable prime test (see PSW page 1004). The Solovay–Strassen primality test uses another equality: Given an odd number n, choose some integer a a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod n , where \left(\frac{a}{n}\right) is the Jacobi symbol, then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime. The Solovay–Strassen test is an Euler probable prime test (see PSW page 1003). For each individual value of a, the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, if n = 1905 and a = 2, then the Miller-Rabin test shows that n is composite, but the Solovay–Strassen test does not. This is because 1905 is an Euler pseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW ). The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm reduced the complexity to {{tmath|1=\mathsf{ {\color{Blue} ZPP} = RP \cap coRP} }}, which superseded Pratt's result. The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP (quasi-polynomial time), which is not known to be comparable with the classes mentioned above. Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the AKS primality test finally settled this long-standing question and placed PRIMES in P. However, PRIMES is not known to be P-complete, and it is not known whether it lies in classes lying inside P such as NC or L. It is known that PRIMES is not in AC 0 .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1377329406 under CC BY-SA 4.0; modifications have been made.