Compositeness without factors

How can a number be proved not prime by someone who cannot name a single factor of it?

Suppose I hand you a 600-digit number and tell you, with confidence, that it is not prime. You ask which number divides it. I say I have no idea, and that nobody on earth could tell you within your lifetime. Is my claim empty? It sounds like claiming a house has an intruder while insisting no room contains one.

It is not empty, and the gap between those two claims — composite and here is a factor — is where modern cryptography actually lives.

Begin with what a proof of compositeness would have to do. It must rule out primality. It need not exhibit the alternative. So ask: is there any property that every prime has, which can be checked without dismantling the number?

There is one, and it is old. Fermat's little theorem: if p is prime and a is not a multiple of p, then a raised to the power p-1 leaves remainder 1 on division by p. Notice what this gives us logically. It is a one-way implication. Prime implies the remainder is 1. So if the remainder is not 1, the number is not prime — and that conclusion is certain, not probable.

Try it small, where you can check every step. Take n = 15 and a = 2. Then 2 to the 14th is 16384. Divide by 15: 15 x 1092 = 16380, leaving remainder 4. Four is not one. Therefore 15 is composite — proved. And look at what we now hold: the number 4, which tells us nothing whatever about 3 and 5. We knew the factors of 15 anyway, but the proof did not use them and did not produce them.

Is the computation feasible for a 600-digit number? Yes, and this is the second half of the trick. Raising to a huge power looks hopeless, but by repeated squaring you reach the exponent in roughly the number of its binary digits — about 2,000 squarings for a 600-digit exponent, each on numbers reduced modulo n so they never grow. Factoring the same number defeats every known method. The two tasks are wildly different in cost, though they concern the same number.

Now the honest complication. What if the remainder is 1? Then the number passed, and we have learned very little — some composites impersonate primes. Worse than that: there are composites that pass for every base coprime to them. The smallest is 561 = 3 x 11 x 17. These are the Carmichael numbers, and there are infinitely many, so no amount of retrying rescues the plain Fermat test.

What was too weak in it? We only asked whether the final result is 1. We threw away everything on the way. Repair it by watching the intermediate steps: write n - 1 as a power of two times an odd number, and square upward from that odd exponent. Here is the extra fact we get to use: modulo a prime, the only square roots of 1 are +1 and -1. So if the sequence of squarings ever arrives at 1 from something that is neither, n cannot be prime.

Run 561 through it. Here 560 = 16 x 35, so start at 2 to the 35th, which is 263 mod 561. Square repeatedly: 166, then 67, then 1. We reached 1 from 67, and 67 is neither 1 nor 560. So 561 is composite — caught by exactly the evidence the Fermat test discarded. (This particular route is unusually generous: since 67 squared minus 1 is divisible by 561, the greatest common divisor of 66 and 561 hands you the factor 33. The Fermat witness case, the one that returned 4 for n = 15, hands you nothing at all.)

Three things are easy to run together here.

First, the asymmetry of the evidence. A failure is a proof of compositeness; a pass is only an absence of evidence. Call the base that produces a failure a witness. The number 4 above is a witness against 15, and it certifies compositeness while certifying nothing about structure.

Second, what "probably prime" means, and what it does not. For the strengthened test, at most one quarter of bases can lie for any odd composite above 9, so k independent random bases leave a failure chance of at most one in 4 to the k. That is a statement about the test's randomness, not about the number, which is either prime or not. And it is an upper bound on a worst case: for large random candidates the true error is far smaller. This is the honest limit of the piece — the proof of the one-quarter bound is a group-theoretic count I am not going to fake, and the intuition that "most bases work" is not itself an argument, because Carmichael numbers show that a plausible-looking test can have no working bases at all.

Third, deterministic tests do exist — AKS proves primality outright in polynomial time — but remain slower in practice, so the probabilistic test is what runs. Note that the neighbouring explanation of public-key encryption rests on factoring being hard. That is a different difficulty, and RSA key generation lives precisely in the gap: you must find and certify large primes cheaply while their product stays unfactorable.

• Why Carmichael numbers exist at all, and Korselt's criterion that characterises them.
• How the AKS algorithm proves primality deterministically, and why it is still rarely used.
• What a primality certificate looks like — a short proof that a number is prime, checkable by a sceptic.

Every term the collection defines is gathered in the glossary.