section_path: Computational methods/Primality testing versus primality proving
section_name: Primality testing versus primality proving
paragraph_text: Primality testing versus primality proving
  
  Some of the fastest modern tests for whether an arbitrary given number n {\displaystyle n} is prime are probabilistic (or Monte Carlo) algorithms, meaning that they have a small random chance of producing an incorrect answer. For instance the Solovay–Strassen primality test on a given number p {\displaystyle p} chooses a number a {\displaystyle a} randomly from 2 {\displaystyle 2} through p − 2 {\displaystyle p-2} and uses modular exponentiation to checkwhether a (p − 1) / 2 ± 1 {\displaystyle a^{(p-1)/2}\pm 1} is divisible by p {\displaystyle p}. If so, it answers yes and otherwise it answers no. If p {\displaystyle p} really is prime, it will always answer yes, but if p {\displaystyle p} is composite then it answers yes with probability at most 1/2 and no with probability at least 1/2. If this test is repeated n {\displaystyle n} times on the same number,the probability that a composite number could pass the test every time is at most 1 / 2 n {\displaystyle 1/2^{n}}. Because this decreases exponentially with the number of tests, it provides high confidence (although not certainty) that a number that passes the repeated test is prime. On the other hand, if the test ever fails, then the number is certainly composite. A composite number that passes such a test is called a pseudoprime.
  
  In contrast, some other algorithms guarantee that their answer will always be correct: primes will always be determined to be prime and composites will always be determined to be composite.For instance, this is true of trial division.The algorithms with guaranteed-correct output include both deterministic (non-random) algorithms, such as the AKS primality test, and randomized Las Vegas algorithms where the random choices made by the algorithm do not affect its final answer, such as some variations of elliptic curve primality proving. When the elliptic curve method concludes that a number is prime, it provides primality certificate that can be verified quickly. The elliptic curve primality test is the fastest in practice of the guaranteed-correct primality tests, but its runtime analysis is based on heuristic arguments rather than rigorous proofs. The AKS primality test has mathematically proven time complexity, but is slower than elliptic curve primality proving in practice. These methods can be used to generate large random prime numbers, by generating and testing random numbers until finding one that is prime;when doing this, a faster probabilistic test can quickly eliminate most composite numbers before a guaranteed-correct algorithm is used to verify that the remaining numbers are prime.
  
  The following table lists some of these tests. Their running time is given in terms of n {\displaystyle n}, the number to be tested and, for probabilistic algorithms, the number k {\displaystyle k} of tests performed. Moreover, ε {\displaystyle \varepsilon } is an arbitrarily small positive number, and log is the logarithm to an unspecified base. The big O notation means that each time bound should be multiplied by a constant factor to convert it from dimensionless units to units of time; this factor depends on implementation details such as the type of computer used to run the algorithm, but not on the input parameters n {\displaystyle n} and k {\displaystyle k}.