一句话定义：亚 n log n 整数乘法（Sub-n log n Integer Multiplication），指把两个 n 位二进制整数相乘的渐近复杂度压到 O(n log n) 以下的研究方向。n log n 是 2019 年被证明可达、又被普遍当作"自然下限"的那条线。
这道墙是怎么垒起来的
竖式相乘是 O(n²)。Karatsuba 用分治把它降到约 n^1.585；Toom–Cook 切成更多块，指数继续下降；1971 年 Schönhage–Strassen 用快速傅里叶变换（FFT）做到 O(n log n log log n），那个 log log n 的"尾巴"挂了近三十年；2007 年 Fürer 把尾巴压到 2^{O(log* n)}；2019 年 Harvey 与 van der Hoeven 给出 O(n log n)。
为什么 n log n 像终点？读入 n 位、写出 2n 位结果本身就要线性量级；再加上 FFT 类算法"变换—点乘—逆变换"的固定结构，n log n 看起来是这类方法的天花板。
| 方法 | 渐近复杂度 | 关键想法 |
|---|---|---|
| 竖式相乘 | O(n²) | 逐位乘、错位加 |
| Karatsuba | 约 n^1.585 | 三次乘法换一次 |
| Toom–Cook | n^{1+ε} 级 | 切成更多块 |
| Schönhage–Strassen | n log n log log n | 用 FFT 做卷积 |
| Fürer | n log n · 2^{O(log* n)} | 更省的多项式变换 |
| Harvey–van der Hoeven | O(n log n) | 优化变换与舍入 |
| 亚 n log n | 低于 O(n log n) | 换模型／摊销／特殊结构／代数归约 |
怎么压到下面
公开文献里能在 n log n 之下取得进展的，通常是四条路，且几乎都带条件：
1. 换算度量口径或计算模型——位复杂度、字复杂度、RAM 与多带图灵机上的 n 和 log n 含义不同，结论不能横比。
2. 摊销与预处理——同一个数要乘很多次时（密码学里的模幂就是典型），代价可以摊进预处理。
3. 限制输入结构——数字稀疏、位宽规整，或允许用别的表示形式输出。
4. 归约到别的代数问题——借矩阵乘法指数 ω、张量分解或群代数的结论反过来加速乘法。
所以看到"突破 n log n"的说法，先问三件事：哪种模型、哪种输入、单次还是摊销。细节以原始论文和后续复现为准。
别和谁混淆：别把亚 n log n 等同于"FFT 乘法"——后者本身就是 n log n log log n，是这道墙的一部分；也别和"快速矩阵乘法"混，那是另一个独立的指数问题，只是工具会互相借用。
对从业者的意义
- 密码学：RSA、椭圆曲线依赖大整数乘法和模幂，但决定密钥长度的是攻击算法与硬件常数，不是乘法的渐近指数。这类结果影响的是安全参数的成本模型，不会让你明天就换密钥。
- AI 算力：今天模型的瓶颈是低精度矩阵乘法，不是大整数乘法；但两者共享同一个思路——把乘法写成卷积，把卷积写成张量收缩，再想办法压指数。这解释了为什么"换代数结构"常常比"调常数"值钱。
- 理论计算机科学：n log n 是否真是下界、乘法与矩阵乘法能否互相加速，是复杂度理论里连着好几条主线的枢纽问题。
整数乘法每次提速，都不是把常数调小一点，而是换一种看待"乘法"的方式。