Schönhage-Strassen算法

Schönhage-Strassen算法是1971年由Arnold Schönhage和Volker Strassen提出的基于FFT的大整数乘法算法，将时间复杂度降至 $O(N\log N\log\log N)$。该算法利用卷积定理，将大整数视为以基数为变量的多项式展开，通过快速数论变换（NTT，FFT在有限域上的同构变体）在频域进行点乘后逆变换，实现超大整数的高效乘法。

应用场景

• 密码学：RSA加密、椭圆曲线数字签名
• 科学计算：逼近圆周率π的千万位
• 素数搜索：GIMPS项目寻找创纪录的大素数

算法步骤

1. 多项式求值：利用NTT在 $O(N\log N)$ 时间内计算出频域投影向量
2. 频域点乘：在频域坐标系中以 $O(N)$ 线性时间复杂度逐点相乘
3. 系数插值还原：执行逆变换（IFFT），提取出精确的最终超大整数乘积