Shor 分解算法
- Shor 分解算法是由 Peter Shor 提出的。
- 该算法表明，量子力学允许我们在多项式时间内完成分解，而使用经典算法通常需要指数级的时间。
- 这可能会对数据安全领域产生巨大的影响，因为该领域的安全性通常建立在大数质因数分解的难度之上。
- 虽然存在许多用于整数乘法的多项式时间算法（例如欧几里得算法），但目前尚不存在用于因数分解的经典多项式时间算法。
- 因此，Shor 提出了 Shor 分解算法，这是一种用于分解 L 位非质整数 N 的算法。
- 量子算法之所以远优于经典算法，是因为它们基于量子傅里叶变换。
- 在经典计算机上的运行时间是 O[exp (L1/3(log L)2/3)]，而在量子计算机上的运行时间则是 O(L3)。
- 所以，Shor 算法在原则上展示了量子计算机能够在多项式时间内分解非常大的数字。
Shor 算法依赖于：
- 模运算
- 量子并行性
- 量子傅里叶变换
算法概述如下：
给定一个奇合数 N，我们需要找到一个严格介于 1 和 N 之间的整数 d，使其能整除 N。
Shor 算法由以下两个部分组成：
- 将因数分解问题转化为寻找周期的问题。这一部分可以使用经典手段实现。
- 使用量子傅里叶变换来寻找周期（即量子周期查找），这部分负责实现量子加速，并利用了量子并行性。
在 Shor 算法中，输入是非质数 N，输出则是 N 的非平凡因子。
> INPUT (N) —> SHOR‘S ALGORITHM —> OUTPUT (N 的非平凡因子)
算法步骤： 它包含几个步骤，仅在步骤 2 中需要使用量子计算机。
- 选择任意随机数，假设为 r，满足 r < N，使得它们互为质数（互质）。
- 使用量子计算机来确定函数 fr, N(x) = rx mod N 的未知周期 p。
- 如果 p 是奇数，则返回步骤 1。否则，继续下一步。
- 既然 p 是偶数，那么 (rp/2 – 1)(rp/2 + 1) = rp – 1 = 0 mod N。
- 现在，如果 rp/2 + 1 = 0 mod N，则返回步骤 1。
- 如果 rp/2 + 1 != 0 mod N，则继续下一步。
- 计算 d = gcd(rp/2-1, N)。
- 我们所需的答案就是 ‘d‘。
经典部分（阶寻找问题）：
这是阶寻找问题的经典部分。给定 x 和 N，满足 x<N 且 gcd(x, N) = 1。x 的阶是使得 xy = 1(mod N) 的最小正整数 y。
- 选取一个随机数 n，满足 n < N。计算 gcd(n, N)。
- 这可以使用欧几里得算法来完成。
- 如果 gcd(n, N) != 1，则说明存在 N 的一个非平凡因子。如果 (x+p) = nx+p mod N = nxmod N = f(x)。
- 如果 r 是奇数，则返回步骤 1。
- 如果 np/2 = -1(mod N)，则返回步骤 1。
- gcd(np/2 +/- 1, N) 即为 N 的一个非平凡因子。
量子部分：
> 这是量子阶寻找部分。选择一个 2 的幂，令
> Q = 2L 使得 N2 <= Q <= 2N2
并考虑 f = {0, 1, 2, …, Q-1}
其中，f(y)=1/(Q)1/2 ∑x=0Q-1I f(x) I wxy 且 w = exp(2π i/Q)，即 Q 次单位根。
- 让我们通过一个例子来执行 Shor 算法：分解一个奇整数 N（设 N = 17）。
- 选择一个整数 Q，使得 N2 <= Q ≤ 2 N