Karatsuba multiplication

The way you multiply two large numbers by hand — multiply every digit of one by every digit of the other and add — takes about n^2 single-digit multiplications for n-digit numbers, which is painfully slow for thousand-digit numbers in cryptography. Karatsuba's algorithm, found in 1960, was the first method to beat this, multiplying in about O(n^1.585) by a divide-and-conquer trick that trades one expensive multiplication for a few cheap additions.

Split each n-digit number in half: write x = a * 10^(n/2) + b and y = c * 10^(n/2) + d, where a,b,c,d are roughly n/2-digit numbers. The schoolbook product x*y = ac * 10^n + (ad + bc) * 10^(n/2) + bd needs FOUR half-size multiplications (ac, ad, bc, bd), giving T(n) = 4 T(n/2) + O(n) = O(n^2) — no gain. Karatsuba's insight is that the middle term ad + bc can be recovered from only ONE extra multiplication: compute p1 = ac, p2 = bd, and p3 = (a+b)(c+d); then ad + bc = p3 - p1 - p2. That is just THREE half-size multiplications, so T(n) = 3 T(n/2) + O(n). By the Master Theorem this solves to O(n^(log2 3)) = O(n^1.585).

Karatsuba is the entry point to fast arithmetic and a perfect illustration that the number of recursive calls (the a in a T(n/b)) is what really controls speed — dropping from 4 to 3 multiplications changes the exponent. It is used in big-integer libraries for medium-sized numbers, handing off to even faster FFT-based multiplication for the largest. The honest caveat: the extra additions and recursion overhead mean Karatsuba only wins above a crossover threshold (often hundreds of digits); for small numbers the plain O(n^2) method is faster, so libraries switch between them by size.