38、多项式算术、线性生成序列及其应用

多项式算术、线性生成序列及其应用

1. 多项式算术在整数分解中的应用

在整数分解问题上，传统的试除法分解一个大正整数 $n$ 的时间复杂度为 $n^{1/2 + o(1)}$。而利用 $Z_n[X]$ 中的快速多项式算术，能得到一个简单、确定性且严谨的算法，其时间复杂度为 $n^{1/4 + o(1)}$。之前讨论的分解算法，虽速度更快，但要么是概率性的，要么是确定性但基于启发式的。

假设我们可以用 $M(\ell)$ 次 $Z_n$ 中的运算来完成长度至多为 $\ell$ 的 $Z_n[X]$ 中多项式的乘法，其中 $M$ 是一个表现良好的复杂度函数，且 $M(\ell) = \ell^{1 + o(1)}$。下面来看两个相关的问题：
-问题 (a)：设 $\ell$ 为正整数，对于 $i = 1, \cdots, \ell$，定义 $a_i := \prod_{j = 0}^{\ell - 1} (i\ell - j) \bmod n$。利用快速多项式算术，可以在 $\ell^{1 + o(1)} \text{len}(n)^{O(1)}$ 时间内计算出所有的整数 $a_1, \cdots, a_{\ell}$。
-问题 (b)：基于问题 (a) 的结果，可以用一个确定性算法在 $n^{1/4 + o(1)}$ 时间内分解 $n$。

此外，在多项式算术领域，还有一些其他有趣的结论：
- Brent 和 Kung 的算法可以用 $O(\ell^{(\omega + 1)/2})$ 次 $R$ 中的运算解决特定问题，其中 $\omega$ 是矩阵乘法的指数，且 $(\