Primality test

A primality test is a mathematical algorithm used to determine if a specific number is prime. A prime number is a positive integer greater than 1 that has no divisors other than 1 and itself. These tests are essential in modern mathematics and computer science. They are used heavily in cryptography to secure digital communications. While integer factorization seeks to find the specific prime factors of a number, a primality test only identifies if the number is prime or composite. Factorization is considered a computationally difficult problem. In contrast, primality testing is comparatively easy because its running time is polynomial relative to the size of the input.

The most basic method is known as trial division. To use this, you divide the input number, n, by every prime number between 2 and the square root of n. If any of these divisions leave no remainder, the number is composite. If no such divisors are found, the number is prime. This works because every divisor pair of a number must contain at least one divisor less than or equal to its square root. For example, testing the number 221 requires checking primes up to 14. Since 13 divides 221, the number is proven to be composite. Testing 17 only requires checking 2 and 3, which proves 17 is prime.

Mathematicians have developed ways to make trial division more efficient. One method is to test divisibility by 2 and 3, then only check numbers of the form 6k ± 1. This is nearly three times faster than checking every number. Another strategy is to use a primality sieve, like the Sieve of Eratosthenes, to pre-compute a list of small primes. By checking a large number against a stored list of primes up to 200, you can quickly identify many composite numbers. This allows you to skip much more complex tests if a small prime factor is found immediately.

Some tests are categorized as heuristic tests. These methods appear to work well in practice, but they are unproven and are not technically considered true algorithms. An example is the Fermat primality test. This test uses the property that if n is prime, then a raised to the power of n minus 1 is congruent to 1 modulo n. If this equality fails, the number is definitely composite. However, some composite numbers, called pseudoprimes, can pass this test. Even more tricky are Carmichael numbers, like 561, which pass the Fermat test for every number coprime to them.

Probabilistic tests are more rigorous than heuristics because they provide provable bounds on error. These tests choose a random number, called a witness, to test against the input n. If the test fails, n is certainly composite. If the test passes, n is declared "probably prime." The probability of error decreases as you repeat the test with different random witnesses. For the Miller-Rabin test, at least half of all possible witnesses will detect a composite number. By repeating the test k times, the error probability drops to at most 2 to the power of negative k.

The Miller-Rabin and Solovay-Strassen tests are two highly regarded probabilistic methods. The Miller-Rabin test is a strong probable prime test that is very efficient. The Solovay-Strassen test uses the Jacobi symbol to check for primality. While the Solovay-Strassen test is useful, the Miller-Rabin test is generally considered more powerful. For instance, the number 1905 is an Euler pseudoprime to base 2, meaning Solovay-Strassen might not catch it, but Miller-Rabin will correctly identify it as composite. The Baillie-PSW test combines these ideas to create a test with no known counterexamples for numbers up to 2 to the 64th power.

Finally, there are deterministic tests that provide absolute certainty without probability. The elliptic curve primality test is one such method. It is an errorless algorithm that can produce a primality certificate to prove a number is prime. Although it is slower than probabilistic tests, it is mathematically definitive. In the future, the field may change with the rise of quantum computers. Using Shor's algorithm alongside the Pocklington primality test, quantum machines could potentially solve these problems much faster than classical computers can today.