长乘法还真是一种漫长的算法呢。两个数相乘很简单，对吧？我们在小学就会学习长乘法，类似的方法可以追溯到几千年前，至少到古苏美尔人和古埃及人时代。但这真的是求两个大数的乘积的最好方法吗？在长乘法中，我们必须用第一个数的每一位与第二个数的每一位相乘。如果两个数均有 N 位，总共就是 N^2 次相乘。约 1956 年，著名苏联数学家 Andrey Kolmogorov 猜测这就是两数相乘的最佳办法。
换句话说，无论你如何安排，运算的工作量至少是 N^2 量级。位数翻倍意味着工作量增至四倍。Kolmogorov 认为，如果简便方法可能存在的话，一定早就被发现了。这是“诉诸无知”逻辑谬论的极好的例子。没过几年，Kolmogorov 的猜想就被证明是大错特错。1960 年，23 岁的俄罗斯数学系学生 Anatoly Karatsuba 发现了一种代数技巧，能够减少需要相乘的次数。
例如，运用 Karatsuba 的方法，将两个四位数相乘只用做 9 次乘法，而不是 4^2 = 16 次。他的方法在位数翻倍时工作量只增至三倍，与传统方法相比，在数字更大时展现了巨大的优势。对于 1000 位的数字，Karatsuba 的方法需要的乘法运算次数只有长乘法的大约 17 分之一。但究竟为什么要把这么大的数字相乘呢？事实上，这样的乘法有大量相关应用。
最明显并且最具经济效益的一个应用方向就是密码学。每次你在网络上使用加密交流时，比如登录银行网站或进行网络搜索的时候，你的设备会执行大量乘法，其中涉及上百位甚至上千位的数字。在这个过程中，你的设备很可能就使用了 Karatsuba 的技巧。这都是软件生态系统的一部分，能让使我们的网页尽快加载出来。在一些保密等级更高的应用中，数学家还必须应对更庞大的数字，位数达到上百万、十亿甚至万亿。
对于这样的数字，甚至连 Karatsuba 的算法都太慢了。1971 年，德国数学家 Arnold Schönhage 和 Volker Strassen 带来了一个真正的突破。他们解释了如何使用当时刚刚发表的快速傅里叶变换（FFT）高效地将巨大数字相乘。现在，他们的方法已被数学家经常应用来处理数十亿位的数字。FFT 是 20 世纪最重要的算法之一。
它在日常生活中最常见的应用就是数字音频：每当你听 MP3、音乐流媒体或数字电台时，在台后进行音频解码的正是 FFT。在 1971 年的论文中， Schönhage 和 Strassen 也提出了一个引人注目的猜想。他们的猜想的前半部分是：有可能通过最多 Nlog (N)（即 N 的自然对数的 N 倍）次量级的基本运算来将 N 位数相乘。
他们自己的算法并未完全实现这个目标，它所需的运算次数是理论最小值的 log (log N)（N 对数的对数）倍。然而，直觉让他们怀疑漏掉了什么东西，Nlog (N) 应该是可行的。自 1971 年起的几十年来，一些研究者已经对 Schönhage 和 Strassen 的算法进行了改进。
尤其是 Martin Fürer，他在 2007 年设计的一种算法已经极其接近难以达到的 Nlog (N) 量级。他们猜想的第二部分，也是更为困难的部分是：Nlog (N) 应该是基本的运算速度极限。也就是说，不可能有乘法算法能实现比这更少的运算次数。
几周前，Joris van der Hoeven 和我发表了一篇研究论文，描述了一种新的乘法算法，终于触及了 N log (N) 这个“圣杯”，解决了 Schönhage–Strassen 猜想中“简单”的部分。这篇文章还未经过同行评审，所以需要谨慎看待。在数学界，研究成果常常在经历同行评审之前就被传播开来。
我们的算法没有采用一维 FFT 方法（自 1971 年起关于这一问题的所有研究工作都依靠这种方法），而是使用了多维 FFT 方法。这方法本身并不新，广泛使用的 JPEG 图片格式就依靠二维 FFT 方法，三维FFT方法在物理和工程中也有很多应用。在我们的论文中，我们使用了 1729 维的 FFT 方法。这很难想象，但在数学上并不比二维情况麻烦。
这项新算法目前还很难得到实际运用，因为我们文章中的证明只适用于大得出奇的数字。即使把每一位数字都写在一个氢原子上，可观测的宇宙中也几乎没有足够的空间写下它们。另一方面，我们希望通过进一步的改进，能让算法适用于只有数十亿或万亿位的数字。如果能实现这个目标，它将很可能成为计算数学家的工具包中必不可少的装备。
如果 Schönhage–Strassen 猜想完全正确，那么理论上，这项新算法已到了路的尽头，不可能做得更好了。就我个人而言，如果猜想最终是错误的，那么我也会非常惊讶。但我们不应忘记发生在 Kolmogorov 身上的事情。数学有时会给人带来惊喜。