大整数的因数分解问题是计算复杂性理论与密码学中的经典难题。尽管目前尚未证明该问题属于 NP 完全问题，但已知在经典计算模型下，对于一般大整数的因数分解尚不存在多项式时间算法。当前最有效的经典算法是广义数域筛法（General Number Field Sieve，GNFS），其时间复杂度为亚指数级，在处理大整数时仍需巨大的计算资源。

这种“正向计算容易、逆向计算困难”的不对称性——即两个大素数相乘非常高效，而从得到的大合数恢复原始素因子在经典计算条件下极为困难——构成了现代公钥密码体系安全性的核心基础。以 RSA（Rivest–Shamir–Adleman）算法为例，其安全性正依赖于大整数因数分解在经典计算模型下的困难性，使攻击者无法在可接受时间内从公钥推导出私钥，从而保障信息传输与存储的安全。

然而，Shor 于 1994 年提出的量子算法表明，在理想量子计算模型下，大整数因数分解可以在多项式时间内完成。该算法将因数分解问题转化为求模指数函数的周期问题，并利用量子并行性与量子傅里叶变换（Quantum Fourier Transform，QFT）高效求解周期，从而突破了经典计算模型下的复杂度限制。这一结果从根本上动摇了基于因数分解困难性的传统公钥密码体系，并直接推动了后量子密码学的发展。

具体来说，对于任意待分解的大于 1 的正整数 N，选择与 N 互素的正整数 a 即

\gcd(a, N) = 1

定义模运算函数：

f(x) = a^x \bmod N

由于

f(0) = 1 \bmod N = 1

易证（其实不易证，要用到群论），该函数为周期函数。因此，存在最小正整数 r，使得

a^r \bmod N= 1

此时的 r 即为该函数的周期。因此，有

a^r - 1 \equiv 0 \pmod{N}

即

(a^{r/2}+1)(a^{r/2}-1) \equiv 0 \pmod{N}

因此，对于 r 为偶数时，可知两者中至少有一项与 N 具有非平凡公因子，即：

\gcd(a^{r/2}\pm 1,\, N) \in (1, N)

因为 gcd 可基于欧几里得算法在经典计算机上于多项式时间内实现，因此由此可有效计算 N 的因子。

但在经典计算机上，寻找周期 r 仍需指数时间，相当于暴力破解；而 Shor 算法利用量子并行和 QFT 可在多项式时间内求解 r，从而彻底破解了传统计算机基于大数因式分解的加密算法基础。

对于任意的正整数 x，根据二进制展开，有：

x = 2^0 x_0 + 2^1 x_1 + 2^2 x_2 + \cdots + 2^{t-1} x_{t-1},
\quad x_k \in \{0,1\}.

因此，

a^x
= a^{2^0 x_0}\cdot a^{2^1 x_1}\cdot a^{2^2 x_2}\cdots a^{2^{t-1} x_{t-1}} = \prod_{k=0}^{t-1} a^{2^k x_k}

利用模乘的可分解性：

(a \bmod N) \, (b \bmod N) \equiv ab \pmod N

可得到：

a^x \bmod N
= \prod_{k=0}^{t-1} \left(a^{2^k x_k} \bmod N\right) \bmod N

由于 xn 取值为 0 或 1，有：

a^{2^k x_k} = \begin{cases} 1, & x_k = 0\\ a^{2^k}, & x_k = 1 \end{cases}

这正对应量子计算中的受控幂次乘法操作。对于初始化为 1 的目标寄存器，可表示为：

\ket{x_k}\ket{1} \xrightarrow{\text{C-}U_k} \ket{x_k}\ket{a^{2^k x_k} \bmod N}

其中，C-U_k 表示基于控制比特 x_k 对目标寄存器进行幂次模运算。对任意 x：

\ket{x}\ket{1} \xrightarrow{\text{C-}U} 
\bigotimes_{k=0}^{t-1} \big( \ket{x_k} \ket{a^{2^k x_k} \bmod N} \big)

量子计算机可同时对所有 x 并行操作。若将控制比特通过 Hadamard 门置于均匀叠加态，则量子态为：

\frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} \ket{x}\ket{a^x \bmod N}

如前所述，模运算函数为周期函数，量子叠加态形成间距为 r 的周期性结构。通过 QFT（关于 QFT 的计算细节），可将周期性模式转换为频域峰值，从而测量得到频率信息 k，满足：

\frac{k}{Q} \approx \frac{s}{r}

随后可通过最简分数近似法求得周期 r ，进而求得 N 的非平凡因子，实现大整数的快速分解。