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.
Simple methods The simplest primality test is trial division: given an input number, n {\displaystyle n} , check whether it is divisible by any prime number between 2 and n {\displaystyle {\sqrt {n}}} (i.e., whether the division leaves no remainder). If so, then n {\displaystyle n} is composite. Otherwise, it is prime. All divisors p ≥ n {\displaystyle p\geq {\sqrt {n}}} , must have a divisor n p ≤ n {\displaystyle {\frac {n}{p}}\leq {\sqrt {n}}} , and a prime divisor q {\displaystyle q} of n p {\displaystyle {\frac {n}{p}}} , and therefore looking for prime divisors at most n {\displaystyle {\sqrt {n}}} is sufficient. For example, consider the number 100, whose divisors are these numbers:
1, 2, 4, 5, 10, 20, 25, 50, 100. When all possible divisors up to n {\displaystyle n} are tested, some divisors will be discovered twice. To observe this, consider the list of divisor pairs of 100:
… excerpt ends here. Continue reading the full article.
