Mathematicians still don’t know the fastest way to multiply numbers | Scientific American

July 13, 2026<br>6 min read<br>Add Us On GoogleAdd SciAm<br>Mathematicians still don&rsquo;t know the fastest way to multiply numbers

A 23-year-old student overturned an ancient conjecture about one of math&rsquo;s simplest operations

By Jack Murtagh edited by Jeanna Bryner

Justin Lewis/Getty Images

Love math? Sign up for our weekly newsletter Proof PositiveEnter your email<br>I agree my information will be processed in accordance with the Scientific American and Springer Nature Limited Privacy Policy. We leverage third party services to both verify and deliver email. By providing your email address, you also consent to having the email address shared with third parties for those purposes.<br>Sign Up

Elementary school students might memorize their times tables for single-digit numbers, but memorization won&rsquo;t cut it when the teacher asks for three-digit multiplication. This requires an algorithm: students are taught to stack one number atop another and multiply each digit of the bottom number by each digit of the top one. For millennia, mathematicians believed this to be the fastest multiplication method, until a 23-year-old made a shocking discovery in 1960, which led to a mystery that remains unsolved to this day.<br>This mystery is critical to anyone who partakes in the digital world because multiplication is a foundational operation for computers. Encryption, robotics, artificial intelligence, audio processing and pretty much everything else we task silicon chips with involves multiplication, sometimes of huge numbers many times over. At this scale, even a simple operation becomes a bottleneck, and any extra efficiency has global economic consequences.<br>To understand the nature of that bottleneck, observe how the grade-school algorithm handles growth. When you multiply two two-digit numbers, you perform four single-digit multiplications. If you bump that up to a three-digit pair of numbers, you do nine single-digit multiplications. The workload scales with the square of the number of digits (n2, where n is the number of digits in the numbers being multiplied). When analyzing an algorithm like this, computer scientists don&rsquo;t measure speed in seconds, because that depends on the hardware. Instead they count the computational steps. They also ignore minor bookkeeping details, such as the time it takes to carry a one when multiplying. When numbers get large enough, those lower-level operations cease to matter, entirely eclipsed by the more intensive operations involved. Computer scientists denote the number of steps using what&rsquo;s called Big O notation: the grade-school algorithm, for example, takes O(n2) steps, which is read as &ldquo;order n squared.&rdquo; Broadly speaking, if the numbers are twice as long, the algorithm takes four times as much computational work to execute. If the numbers are a thousand times as long, it takes a million (1,000 squared) times as much work.<br>On supporting science journalism<br>If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.<br>Since antiquity, mathematicians have suspected that O(n2) was an inherent speed limit for multiplication. The celebrated Soviet math professor Andrey Kolmogorov posed the O(n^2) speed limit as a formal conjecture and mentioned it during a 1960 seminar at Moscow State University. Whenever mathematicians propose a conjecture, they are planting a flag of sorts and waiting for others to either prove or disprove them. It took just a week for Anatoly Karatsuba, then a 23-year-old student in the audience, to return and prove Kolmogorov wrong. Kolmogorov was stunned. The result was published in the prestigious Proceedings of the USSR Academy of Sciences, but amusingly, Karatsuba didn&rsquo;t write it. Kolmogorov wrote the formal proof himself and submitted it for publication with Karatsuba listed as the lead author. Karatsuba only found out about the paper when he received the reprints in the mail.<br>Karatsuba&rsquo;s genius was realizing that you can trade expensive, time-consuming multiplications for cheap, fast additions. Adding two n-digit numbers takes only O(n) time because it entails a single sweep through the digits rather than a complete sweep through the top number for every digit of the bottom number, as in multiplication. To see how Karatsuba traded multiplication for addition, let&rsquo;s look at a small example. The method would be overly complicated for such a simple problem, but it saves a meaningful amount of time when numbers get larger.<br>In this simple example, let&rsquo;s calculate 12 &times; 34.<br>First, we split both numbers into their tens and ones digits. Assign a = 1 and b = 2 (for 12), and c = 3 and d = 4 (for 34). Algebraically, we can rewrite 12 &times; 34...