The 60-Year-Old Puzzle: Nobody Knows Multiplication's True Speed Limit

For centuries, mathematicians assumed the grade-school method of multiplying numbers digit-by-digit—which scales as O(n²), quadrupling the work each time the digit count doubles—was the fastest possible. That belief was formalized as a conjecture by Soviet mathematician Andrey Kolmogorov in 1960, only to be demolished within a week by 23-year-old student Anatoly Karatsuba. His insight was to trade costly multiplications for cheap additions: by computing two products and reusing them, the middle term of a split multiplication can be found with one multiplication instead of two. Applied recursively, this four-for-three trade drops the cost to roughly O(n^1.585). Multiplying two 1,000-digit numbers takes a million single-digit multiplications the old way, but under 57,000 with Karatsuba’s method.

This is far from academic trivia. Multiplication underpins encryption, AI, audio processing, robotics, and essentially everything silicon does, often on enormous numbers, so any efficiency gain carries real economic weight. Karatsuba’s algorithm is baked into production software today: because its overhead only pays off at scale, Python uses grade-school multiplication for smaller values and switches to Karatsuba once integers reach roughly 630 decimal digits.

Karatsuba’s breakthrough kicked off a decades-long hunt for the ultimate speed limit of multiplication, which reached a milestone in 2019 when David Harvey and Joris van der Hoeven described an even faster method. Yet the fundamental question Kolmogorov’s failed conjecture opened remains unanswered: nobody has proven what the theoretically fastest multiplication algorithm actually is.