How Computers Multiply Thousand-Digit Numbers
Beyond the Wall of Digits
Reading
$1234 \times 5678$ can be settled with pencil and paper. But what about two thousand-digit numbers? Two million-digit ones? Records for computing $\pi$, and the security of the cryptography that protects everyday traffic, both rest on exactly this: multiplying absurdly large numbers. And yet an ordinary computer handles only about $20$ decimal digits at a time ($64$ bits).
So how does a machine with such a small box climb over the wall of digits so easily? This article looks at the ideas that tame enormous numbers, and then at the extraordinary primes people have chased with them.
Big Numbers Are Kept in Chunks
The idea is plain. If a number does not fit in one box, put it in many boxes. A multiprecision integer is cut into fixed-width chunks, called limbs in this field, and the sequence of limbs is held as an array. Just as we group long numbers with commas every three digits, a computer groups them every $64$ bits and packs one group into each slot of the array.
Once that is done, addition is exactly the schoolbook method. Add from the lowest limb upward and carry the overflow into the next limb. Subtraction works the same way. There are different conventions for the fine points, such as how the sign is stored and which direction the limbs run, but the idea is surprisingly familiar. Multiprecision Integer Representation covers the details.
The Wall That Multiplication Puts Up
Addition costs work proportional to the number of digits. Multiplication is the problem. In the schoolbook method, each digit of the top row is multiplied by every digit of the bottom row. For two $n$-digit numbers there are $n \times n$ digit pairs, so the work grows with the square of the digit count.
Going from $10$ digits to $100$ multiplies the work by $100$; going to $1{,}000$ digits multiplies it by $10{,}000$. Computing a million digits of $\pi$ this way quickly gets out of hand. For a long time everyone believed multiplication simply cost a square. Until a young man overturned it.
Aside: Feeling the Weight of a Square
Work proportional to the square means that a $10\times$ larger input costs $100\times$ more, written $O(n^2)$. The cleverer methods below bring this down to $O(n^{1.585})$, and further still to the $O(n\log n)$ class. A small difference in the exponent becomes an enormous difference once the digit counts get large. That gap is what makes algorithms fun.
The Magic of Divide and Conquer: Four Products Become Three
In $1960$, Anatoly Karatsuba, then still a student, showed at Kolmogorov's seminar that multiplication can be done faster than a square, in front of Kolmogorov himself, who had conjectured that the square was the best possible.
The trick goes like this. Split each of the two numbers into an upper and a lower half. Done naively, this needs four products: upper by upper, upper by lower, lower by upper, and lower by lower. Karatsuba slipped in a few additions and got the same result with only three products, turning one multiplication into much cheaper additions and subtractions.
Then each half is split in half again and the same trick applies. Splitting, splitting, and splitting again, this divide-and-conquer scheme drops the work from a square to $O(n^{1.585})$. A small saving of a single multiplication snowballs through the recursion, one of the most elegant reversals in computer science. Pushing the idea further gives Toom-Cook and NTT-based fast multiplication, which bring million-digit products into practical time.
And Then, Hunting Gigantic Primes
Once large numbers can be handled freely, people want larger game. Chief among the quarry are gigantic primes.
A prime of the form $2^p - 1$, one less than a power of two, is called a Mersenne prime. This shape admits a special and comparatively fast primality test, the Lucas-Lehmer test, which is why Mersenne primes dominate the record books. Today GIMPS, a distributed project, pools the spare compute of personal machines around the world to dig up new ones. It is the largest treasure hunt in history, and anyone can join.
One landmark is worth quoting. The prime $2^{136{,}279{,}841} - 1$, found in October $2024$, has $41{,}024{,}320$ decimal digits, more than forty million. Printing this single number on paper would fill dozens of books.
Techniques also grew for recognising a prime without dividing by anything. The Miller-Rabin test and its relatives, covered in Primality Testing, declare an enormous number "almost certainly prime" in a very short time. Rather than searching directly for a divisor, they test congruence relations that every prime must satisfy, looking for a witness that proves the number composite. Some composites slip through for particular bases, which is why the test is repeated with fresh bases, and why the verdict is only "almost certainly".
Aside: Easy to Build, Hard to Take Apart
Multiplying two large primes together takes an instant. Recovering those two primes from the product, that is integer factorization, becomes staggeringly hard as the digit count grows. This asymmetry, easy to build and hard to take apart, is the principle that makes RSA work. On today's web the key exchange itself has largely moved to elliptic-curve schemes, but RSA is still widely used for the signatures that prove you are talking to the right party. The machinery for handling enormous numbers quietly underwrites public-key cryptography and much of the computing infrastructure built on it.
Closing: A Big World in a Small Box
A machine with nothing but a $64$-bit box learned to cut numbers into chunks laid out in an array, to shave the cost of multiplication by divide and conquer, and finally to hunt down primes of forty million digits. The wall of digits yields, again and again, to a better algorithm. One by one, the plain intuition that "big numbers are slow" has been overturned.
If you want to see the mechanics behind that reversal, go on to the hands-on chapters. The intermediate level presents the four pillars that hold up giant integers: fast multiplication, fast division, modular arithmetic, and GCD.
Frequently Asked Questions
Q: How does a computer multiply integers with thousands of digits?
A: The number is cut into fixed-width chunks called limbs (for example $64$ bits each) and held as an array. Short numbers are multiplied exactly as in the schoolbook method, but that method grows with the square of the digit count. Large numbers are therefore split in half and recombined cleverly by Karatsuba's method, or handled by more advanced Toom-Cook and FFT/NTT based techniques, which cut the work substantially.
Q: Why do people search for such large primes?
A: There are several reasons. First, pure curiosity and the pursuit of records: distributed projects such as GIMPS connect personal computers worldwide to find new Mersenne primes. Second, applications: RSA and similar schemes rest on the fact that multiplying two large primes is easy while factoring the product is extremely hard. The technology for handling large primes underpins that cryptography.
Q: Is Karatsuba's method always faster than the schoolbook method?
A: No. Karatsuba trades multiplications for extra additions, subtractions and recursive calls. While the operands are small that overhead dominates, and plain schoolbook multiplication wins. Practical libraries set a threshold on the digit count and switch from schoolbook to Karatsuba there, and then on to Toom-Cook or NTT for still larger inputs.
References
- Karatsuba algorithm — Wikipedia: the $1960$ algorithm and the derivation of its $O(n^{\log_2 3})$ complexity.
- Mersenne prime — Wikipedia: numbers of the form $2^n - 1$, the Lucas-Lehmer test, and the history of the discoveries.
- GIMPS (Great Internet Mersenne Prime Search): the official site of the distributed project, including the largest known Mersenne prime $2^{136{,}279{,}841} - 1$ ($41{,}024{,}320$ digits, found in October $2024$).
- RSA cryptosystem — Wikipedia: the public-key scheme whose security rests on the difficulty of factoring large integers.