The cost of multiplying big numbers
Multiplying two n-digit numbers the way you learned in school — multiply each digit of one by each digit of the other and add up the shifted rows — costs Theta(n^2) single-digit operations. For the small numbers a CPU handles in one instruction this is invisible, but cryptography routinely multiplies numbers with thousands of digits, and there n^2 starts to bite. The previous guide built fast modular exponentiation on top of multiplication; here we ask the deeper question of how fast a single multiplication can itself be.
The first crack in the n^2 wall came from Karatsuba's algorithm, a divide-and-conquer idea you met in the recurrences rung. Split each number into a high half and a low half; the naive split needs four half-size multiplications, giving T(n) = 4 T(n/2) + O(n), which the master theorem solves back to Theta(n^2) — no gain. Karatsuba's trick is an algebraic identity that computes the same product with only THREE half-size multiplications, turning the recurrence into T(n) = 3 T(n/2) + O(n) and the running time into Theta(n^(log2 3)), about Theta(n^1.585). A genuine win, and a clean reminder that fewer subproblems, not just smaller ones, is what bends a recurrence.
Multiplication is really convolution
To reach the fastest method we change how we see a number. Write the digits of a number as the coefficients of a polynomial: 1234 in base 10 is the polynomial A(x) = 4 + 3x + 2x^2 + 1x^3 evaluated at x = 10. Multiplying two numbers is then multiplying two polynomials and finally evaluating at the base (carrying as needed). And multiplying polynomials is exactly the operation called convolution: the coefficient of x^k in the product is the sum of a_i * b_j over all i + j = k. Done directly, that double sum is again Theta(n^2) — every coefficient of one polynomial meets every coefficient of the other.
Here is the pivot that unlocks everything. A polynomial of degree below n is pinned down by its values at n distinct points just as faithfully as by its n coefficients — two ways to describe the same object. And in value form, multiplication is trivial: if you know A and B at the same points, the product C = A*B at each point is just the single number A(point) * B(point). So multiplying two polynomials given by their values at 2n points costs only O(n) multiplications, not O(n^2). The catch, of course, is getting into and out of value form cheaply. That conversion is the whole game.
The FFT: evaluation in O(n log n)
Evaluating a degree-(n-1) polynomial at n arbitrary points naively costs O(n^2). The Fast Fourier Transform wins by choosing the points with surgical care: the n complex roots of unity, the points spaced evenly around the unit circle, the solutions of x^n = 1. These points have a magical self-similar structure. Split A(x) into its even-indexed and odd-indexed coefficients, A(x) = E(x^2) + x*O(x^2). Because squaring the n roots of unity yields exactly the n/2 roots of unity for the half-size problem, evaluating A at all n points reduces to evaluating two half-size polynomials at n/2 points and combining in O(n) — the very shape of a divide-and-conquer recurrence.
T(n) = 2 T(n/2) + O(n) ==> T(n) = O(n log n) (master theorem, case 2)
The return trip — recovering coefficients from values, called the inverse FFT — is almost the same computation run with the roots of unity conjugated and a final division by n, so it is also O(n log n). Now assemble the full multiplication: FFT both polynomials to value form, multiply the values pointwise in O(n), then inverse-FFT back to coefficients. The total is O(n log n) + O(n) + O(n log n) = O(n log n), decisively beating both Theta(n^2) and Karatsuba's Theta(n^1.585) for large enough inputs.
Testing primality without factoring
Now the second hero of this guide. Given a number n with hundreds of digits, is it prime? The obvious method — trial-dividing by every integer up to sqrt(n) — needs about sqrt(n) divisions, which is exponential in the number of digits and utterly hopeless for cryptographic sizes. We need a primality test whose cost grows with the digit count, not with n itself. The surprising fact is that we can decide primality far faster than we can factor — proving n is composite never requires producing a factor.
The foundation is Fermat's little theorem: if n is prime, then for every base a not divisible by n, a^(n-1) is congruent to 1 modulo n. Read it as a test. Pick a base a, compute a^(n-1) mod n using fast modular exponentiation in O(log n) multiplications, and check whether the result is 1. If it is NOT 1, the theorem's contrapositive fires: n is definitely composite, and a is a witness to that fact. This is the same logic as a Monte Carlo fingerprint check — a cheap necessary condition that, when violated, gives a certain rejection.
But the converse fails, and honesty demands we say how. Some composite numbers pass the Fermat check for a particular base — and a rare, nasty class called Carmichael numbers pass it for EVERY base coprime to n, so no amount of base-picking exposes them by the plain Fermat test. Miller-Rabin patches exactly this hole by checking a stronger condition.
Miller-Rabin and what its answer really means
Miller-Rabin sharpens the test with a fact about square roots. Modulo a prime, the only square roots of 1 are +1 and -1; a composite modulus can have extra 'rogue' square roots, and finding one is an iron-clad proof of compositeness. Write n - 1 = d * 2^s with d odd. Then instead of jumping straight to a^(n-1), the test computes a^d and repeatedly squares it, watching the sequence a^d, a^(2d), a^(4d), ..., a^(n-1) for a forbidden pattern — a value that becomes 1 without the step before it being -1.
- Factor out twos: write n - 1 = d * 2^s with d odd, then pick a random base a in the range 2 to n - 2.
- Compute x = a^d mod n by fast modular exponentiation. If x is 1 or n - 1, this base reports 'probably prime' and we stop for this base.
- Otherwise square x up to s - 1 times. If it ever becomes n - 1, the base reports 'probably prime'. If it reaches 1 without first hitting n - 1, we found a rogue square root: a is a witness and n is DEFINITELY composite.
- Repeat with several independent random bases. If every base reports 'probably prime', declare n probably prime; one witness anywhere declares it composite.
Read the two outcomes asymmetrically, because they are not symmetric. A 'composite' verdict is always correct: a genuine witness is a mathematical proof, no luck involved. A 'probably prime' verdict is the one carrying risk — a composite can fool a single random base, but the theorem behind Miller-Rabin guarantees that at least three-quarters of the bases in 1 to n-1 are witnesses for any composite (Carmichael numbers included). So a composite survives one random round with probability at most 1/4, and survives k independent rounds with probability at most (1/4)^k. Run 30 rounds and the chance of wrongly calling a composite prime is below 4^(-30), smaller than the chance of a hardware fault.
This is a Monte Carlo algorithm with one-sided error: fast and deterministic in time, but its answer can be wrong only in the 'prime' direction, and only with a probability you dial down as low as you like by spending more rounds. Each round is O(log n) modular multiplications, so even hundreds of digits are checked in a blink — which is precisely how systems generate the large primes that RSA depends on. Worth a caveat: a deterministic polynomial-time test (AKS) does exist, settling that primality is in class P, but Miller-Rabin's speed keeps it the practical workhorse everywhere it matters.