23岁学生推翻乘法古老猜想，数学家仍在探寻最快乘法方法！

数学乘法运算的未解之谜

小学生计算一位数乘法靠背诵乘法表，计算三位数乘法则需用到算法。几千年来，数学家认为将数字堆叠相乘是最快的乘法方法，然而1960年，一位23岁的年轻人打破了这一认知，引发了至今未解的谜团。

这个谜团对数字世界至关重要，因为乘法是计算机的基础运算，加密技术、机器人技术、人工智能、音频处理等任务都涉及乘法，大规模运算时，简单运算也会成为瓶颈，效率提升将产生全球性经济影响。

小学乘法算法的瓶颈

小学算法中，运算量与数字位数的平方成正比。计算机科学家用大O符号表示步骤数，小学算法需要O( _n_ ²)步，数字位数翻倍，计算工作量变为四倍；位数变为一千倍，工作量变为一百万倍。

卡拉楚巴算法的突破

自古以来，数学家怀疑O( _n_ ²)是乘法运算的固有速度极限，苏联数学教授安德烈·柯尔莫哥洛夫正式提出此猜想。但仅一周后，23岁的学生阿纳托利·卡拉楚巴就证明他错了。有趣的是，证明论文由柯尔莫哥洛夫撰写，以卡拉楚巴为第一作者发表。

卡拉楚巴用加法替代乘法，以计算12 × 34为例，传统方法需四次乘法，他的方法通过巧妙代数技巧，只需三次乘法。对于更大数字，如1234 × 5678，原本需16次一位数乘法，用他的方法只需9次。该算法运行时间约为O( _n_ ^1.585)，比O( _n_ ²)快得多。

卡拉楚巴算法已融入日常软件，Python在数字达到约630位十进制数时会采用该算法。

寻找乘法终极速度极限

卡拉楚巴算法引发了寻找乘法终极速度极限的竞赛，2019年，数学家大卫·哈维和乔里斯·范德霍芬提出新算法，运行时间为O( _n_ × log _n_ )，增长速度极慢。

不过，该算法像卡拉楚巴算法一样，只有在数字极其巨大时才领先，属于“银河算法”。即便有此限制，它仍是里程碑式的成就，理论上创造了最快乘法方法记录，也可能为实践中以O( _n_ × log _n_ )步运行的算法铺平道路。如今，理论计算机科学家怀疑O( _n_ × log _n_ )是最快速度，但正式证明仍是该领域的难题，历史也提醒我们，猜想可能被推翻。那么，乘法运算的最快速度究竟是多少呢？