PRIMES is in P
/ PRYMES /
Asking 'is this number prime?' sounds easy, but it hides a sharp subtlety about input size, and its history is one of the cleanest victories in complexity theory. The problem PRIMES is the decision problem: given a number N written in binary, answer yes if N is prime and no otherwise. The naive method, dividing N by every candidate up to its square root, takes about the square root of N steps, and since N is written in only about log N bits, that square-root-of-N count is exponential in the input size. So for a long time it was not clear whether primality testing was truly efficient.
The landmark resolution came in 2002, when Agrawal, Kayal, and Saxena gave the AKS algorithm, the first deterministic, unconditional, polynomial-time test for primality. It runs in time polynomial in the number of digits of N (a power of log N), settling that PRIMES is in P with no reliance on unproven number-theoretic conjectures and no coin-flipping. The core idea is an elegant polynomial identity: a number N (with a small technicality) is prime exactly when a certain congruence between polynomials, of the rough shape (x + a)^N being congruent to x^N + a modulo N and a small auxiliary polynomial, holds for enough values of a; checking this can be organised to run in polynomial time.
PRIMES in P is celebrated for what it teaches as much as for the result. It is the textbook example that input size means the number of digits, not the value, so 'try every divisor' is exponential, not linear. It also draws a fine line worth remembering: testing whether N is prime is in P, but FACTORING N (finding its prime divisors) is a different and apparently much harder problem, not known to be in P, and its presumed hardness underwrites modern cryptography. Knowing a number is composite is not the same as being able to split it.
Take a 1000-bit number N (about 300 decimal digits, the size used in cryptography). Trial division would need roughly the square root of N, about 2^500 steps, utterly hopeless. AKS decides primality in time polynomial in 1000 bits, eminently doable. Yet factoring that same N into its prime parts has no known polynomial algorithm, which is why such numbers protect secrets.
Trial division is exponential in the digit count; AKS is polynomial, so PRIMES is in P, while FACTORING stays apparently hard.
PRIMES in P (deciding primality) is NOT the same as FACTORING being easy; finding prime factors is a separate problem with no known polynomial algorithm, and its assumed hardness underlies much of cryptography.