7、整数分解的量子算法与基于整数分解的密码学
整数分解的量子算法与基于整数分解的密码学
1. 整数分解算法概述
整数分解是将一个整数分解为其素因数的过程。目前存在多种整数分解算法，如$\rho$-方法、试除法、数域筛法（NFS）等，但这些算法大多效率不高，无法在多项式时间内完成分解。
1.1 $\rho$-算法
$\rho$-算法是一种用于整数分解的算法，其核心步骤如下：
1. 初始化：选择一个种子和一个生成器。
2. 迭代计算：
- 计算$y_i = x_{2i} = f(f(y_{i - 1}))$。
- 同时计算$d = \gcd(x_i - y_i, n)$。
3. 因子判断：如果$1 < d < n$，则$d$是$n$的一个非平凡因子，输出$d$，并进入步骤5。
4. 再次搜索：如果对于某个$i$有$x_i \equiv y_i \pmod{n}$或者$i \geq p_t$，则返回步骤1，选择新的种子和生成器并重复。
5. 退出：终止算法。
该算法的复杂度猜想如下：设$p$是整除$n$的素数，且$p = O(\sqrt{p})$，则$\rho$-算法找到$n$的素因子$p$的期望运行时间为$O(\sqrt{p}) = O(\sqrt{p} (\log n)^2) = O(n^{1/4} (\log n)^2)$。
与试除法相比，$\rho$-算法有所改进，因为试除法需要$O(p) = O(n^{1/4})$次除法才能找到$n$的一个小因子$p$。但$\rho$-算法的一个缺点是其运行时间只是一个猜想的期望值，不是严格的界限。