A
primality test is an
algorithm for determining whether an input number is
prime. Amongst 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 be called
compositeness tests instead of primality tests.