Primality test

Primality testing is the computational problem of deciding whether a given whole number is prime, that is, whether it has no divisors other than one and itself. The simplest approach is trial division, which checks the number against possible divisors up to its square root, but far faster methods exist for large inputs. Some tests, such as the elliptic curve and AKS families, prove that a number is prime, while others, such as the Miller-Rabin test, can only prove that a number is composite and are better described as compositeness tests. Unlike integer factorisation, a primality test generally does not return the prime factors, and testing is comparatively easy because its running time is polynomial in the size of the input, while factorisation is thought to be a hard problem. The problem matters in cryptography, which depends on finding very large primes.