对于因子分解量子算法的一些简单思考

参考：Quantum Computation and Quantum Information (10th Anniversary Edition) - Michael A. Nielsen & Isaac L. Chuang

本学期选修了 “密码学中的量子计算” 研讨课，中途涉及到对Shor因子分解算法的理解。书中的描述有多处存在问题（或本人没理解到位），这里列举一些我自己的思考。

因子分解算法的思路

因子分解问题（Factoring Problem）

给定正整数 N=∏i=1mpiαiN = \prod\limits_{i = 1}^{m}p_i^{\alpha_i} ，对其进行素因子分解。

经典筛法的核心策略：找两个正整数 z<y<Nz < y < N，让它们满足 z2≡y2(modN)z^2\equiv y^2 \pmod{N}（平方同余关系）。（当然这里仅考虑 gcd⁡(z,N)=gcd⁡(y,N)=1\gcd(z, N) = \gcd(y, N) = 1 的情况，否则 NN 就直接被 zz，yy 分解了。）

z2≡y2(modN)  ⟺  (y−z)⋅(y+z)≡0(modN)z^2 \equiv y^2 \pmod{N} \iff (y - z)\cdot (y + z) \equiv 0 \pmod{N}

这意味着只要 y−z>1y - z > 1 且 y+z≠Ny + z \neq N，那么就有 h=gcd⁡(y−z,N)h = \gcd(y - z, N) 为 NN 的一个非平凡因子。

这时对其做一些简单的变换：

  • 考虑 gcd⁡(y,N)=1\gcd(y, N) = 1：

z2≡y2(modN)  ⟺  (zy−1)2≡1(modN)z^2 \equiv y^2 \pmod{N} \iff \left(zy^{-1}\right)^2 \equiv 1 \pmod{N}

  • 设 x=zy−1x = zy^{-1}：

x2≡1(modN)x^2 \equiv 1\pmod{N}

(x−1)(x+1)≡0(modN)(x - 1)(x + 1)\equiv 0 \pmod{N}

即得到下述 Statement：

Statement 1：对正整数 NN，方程 x2≡1(modN)x^2\equiv 1\pmod{N} 的解 xx 满足 2⩽x⩽N−12\leqslant x \leqslant N - 1，则 gcd⁡(x−1,N)\gcd(x - 1, N) 和 gcd⁡(x+1,N)\gcd(x + 1, N) 之中至少有一个是 NN 的非平凡因子。（x=2x = 2时，x−1=1x-1 = 1；x=N−2x = N-2时，x+1=N−1x +1=N-1。）

这时问题就变成了，我们怎么去找到这样的一个关系呢？

  • How to Find?（注：因子22的检测是平凡的，因此下面均考虑 NN 为奇数。）
  • 欧拉定理？（xφ(N)≡1(modN)x^{\varphi(N)}\equiv 1\pmod{N}） ⇒\Rightarrow Nope！ 我们无法计算 φ(N)\varphi(N)！
  • 我们可以使用量子傅里叶变换求取元素的阶！（解决元素求阶问题）⇒\Rightarrow 我们可以计算使得 xr≡1(modN)x^r\equiv 1\pmod{N} 最小的 rr ！（元素 xx 在模 NN 意义下的阶 r=ordN(x)r = \text{ord}_N(x)。）
  • If we are FORTUNATE，恰有 2∣r2\mid r，那么就有

(xr2−1)⋅(xr2+1)≡0(modN)\left(x^{\frac{r}{2}} - 1\right)\cdot \left(x^{\frac{r}{2}} + 1\right)\equiv 0\pmod{N}

  • If we are MORE FORTUNATE，恰有

xr2+1≢0(modN)  ⟺  xr2≢−1(modN)x^{\frac{r}{2}} + 1 \not\equiv 0\pmod{N} \iff x^{\frac{r}{2}} \not\equiv -1\pmod{N}

  • 那么检查 gcd⁡(xr2+1,N)\gcd\left(x^{\frac{r}{2}} + 1, N\right) 以及 gcd⁡(xr2−1,N)\gcd\left(x^{\frac{r}{2}} - 1, N\right) 其中谁为非平凡因子即可！

元素求阶问题的求解在后续内容再进行介绍，下面我们看看怎么将因子分解问题一步一步真正地去调用元素求阶问题来解决，这里面有不少细节值得讨论。

现在出现了一个新的问题：我们怎么获得有着满足这样关系的阶 rr 的 xx ？

或者说我们均匀随机选取一个 xx ，它有多大概率满足下述条件？

  • 2∣r2\mid r
  • xr2+1≢0(modN)  ⟺  xr2≢−1(modN)x^{\frac{r}{2}} + 1 \not\equiv 0\pmod{N} \iff x^{\frac{r}{2}} \not\equiv -1\pmod{N}

这里我们首先排除一个情况，即均匀选取了一个 xx，很巧合的是它恰好与 NN 有非平凡公因子，这样其实问题就直接解决了。但是很显然，这个概率实在是太小了！如，对于 N=p⋅qN = p\cdot q，p∼q∼Np\sim q\sim\sqrt{N}，这样的概率的量级为 1p∼1N\frac{1}{p}\sim\frac{1}{\sqrt{N}}！（注：超级大乐透中奖概率 ∼1225\sim\frac{1}{2^{25}}，气运之子快去买彩票吧。）

下面我们就仅考虑 gcd⁡(x,piαi)=1\gcd(x, p_i^{\alpha_i}) = 1 的情况了。

接下来我们将要证明下面这个 Statement：

Statement 2：均匀随机选取一个 x∈(Z/NZ)×x \in \left(\mathbb{Z}/N\mathbb{Z}\right)^{\times} ，它满足：

  • 2∣r2\mid r
  • xr2+1≢0(modN)  ⟺  xr2≢−1(modN)x^{\frac{r}{2}} + 1 \not\equiv 0\pmod{N} \iff x^{\frac{r}{2}} \not\equiv -1\pmod{N}

的概率满足

Pr⁡x←U((Z/NZ)×)(2∣ordN(x) ∧ xr2≢−1(modN)){=0m=1⩾1−12m−1m⩾2\Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\mid \text{ord}_N(x)\ \wedge\ x^{\frac{r}{2}} \not\equiv -1\pmod{N} \right) \begin{cases} = 0 & m = 1\\\geqslant 1 - \dfrac{1}{2^{m - 1}} & m\geqslant 2\end{cases}

注：这里的结论与参考书中的结论略有不同，参考书中的结论我不是很推得过去，按理说大抵的确是有问题的。。。

上述的 Statement 2 保证了我们是足够幸运的！

It turns out that we are FORTUNATE!

现在我们解决以下问题：

均匀随机选取一个 x∈(Z/NZ)×x \in \left(\mathbb{Z}/N\mathbb{Z}\right)^{\times} ，它有多大概率满足：

  • 2∣r2\mid r
  • xr2+1≢0(modN)  ⟺  xr2≢−1(modN)x^{\frac{r}{2}} + 1 \not\equiv 0\pmod{N} \iff x^{\frac{r}{2}} \not\equiv -1\pmod{N}

即计算：

Pr⁡x←U((Z/NZ)×)(2∣r ∧ xr2≢−1(modN))\Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\mid r\ \wedge\ x^{\frac{r}{2}} \not\equiv -1\pmod{N} \right)

这里其实有一个直觉就是，感觉我们去求这个事件的反面会更简单一点，即计算：

Pr⁡x←U((Z/NZ)×)(2∤r ∨ xr2≡−1(modN))\Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\nmid r\ \vee\ x^{\frac{r}{2}} \equiv -1\pmod{N} \right)

接下来的任务就是一步一步地研究方程 xr≡1(modN)x^r \equiv 1\pmod{N}了。

根据中国剩余定理，我们显然有：

xr≡1(modN)  ⟺  xr≡1(mod∏i=1mpiαi)⇒xr≡1(modpiαi)∀i∈[m]x^r\equiv 1\pmod{N} \iff x^r\equiv 1\pmod{\prod\limits_{i = 1}^mp_i^{\alpha_i}} \Rightarrow x^r\equiv 1\pmod{p_i^{\alpha_i}} \forall i\in [m]

记 ri=ordpiαi(xi)r_i = \text{ord}_{p_i^{\alpha_i}}(x_i)，即 xri≡1(modpiαi)x^{r_i}\equiv 1\pmod{p_i^{\alpha_i}}。显然：

ri∣rr_i \mid r

因为我们研究的是 rr 的奇偶性，因此我们考虑在 2-adic 上进行分析。

记 v2(n)∈Nv_2(n)\in\mathbb{N} 满足 2v2(n)∣n2^{v_2(n)}\mid n且 2v2(n)+1∤n2^{v_2(n)+1}\nmid n，也记 2v2(n)∥n2^{v_2(n)}\parallel n。

此时将事件 2∤r ∨ xr2≡−1(modN)2\nmid r\ \vee\ x^{\frac{r}{2}} \equiv -1\pmod{N} 拆成两半就有（注意 v2(ri)⩽v2(r)v_2(r_i)\leqslant v_2(r)）：

  • 若 2∤r2\nmid r，则

2∤r⇒2∤ri  ⟺  v2(ri)=v2(r)=0, ∀ i∈[m]2\nmid r \Rightarrow 2\nmid r_i\iff v_2(r_i) = v_2(r) = 0,\ \forall\ i\in[m]

  • 若 2∣r2\mid r 且 xr2≡−1(modN)x^{\frac{r}{2}}\equiv -1\pmod{N}，则

xir2≡−1(modpiαi)⇒ri∤r2, ∀ i∈[m]  ⟺  v2(ri)=v2(r), ∀ i∈[m]x_i^{\frac{r}{2}}\equiv -1\pmod{p_i^{\alpha_i}} \Rightarrow r_i\nmid \dfrac{r}{2},\ \forall\ i\in[m] \iff v_2(r_i) = v_2(r),\ \forall\ i\in[m]

In conclusion,

2∤r ∨ xr2≡−1(modN)⇒v2(ri)=v2(r), ∀ i∈[m]2\nmid r\ \vee\ x^{\frac{r}{2}} \equiv -1\pmod{N} \Rightarrow v_2(r_i) = v_2(r),\ \forall\ i\in[m]

注意到中国剩余定理：

xr≡1(mod∏i=1mpiαi)⟷1−1{x1r≡1(modp1α1)⋮xmr≡1(modpmαm)x^r\equiv 1\pmod{\prod\limits_{i = 1}^mp_i^{\alpha_i}} \stackrel{1-1}{\longleftrightarrow} \begin{cases} x_1^r\equiv 1\pmod{p_1^{\alpha_1}}\\ \qquad\vdots\\ x_m^r\equiv 1\pmod{p_m^{\alpha_m}}\\ \end{cases}

这里的 x∈Z/NZx \in \mathbb{Z}/N\mathbb{Z} 与 (x1,⋯ ,xm)∈∏i=1m(Z/piαiZ)(x_1, \cdots, x_m)\in \prod\limits_{i=1}^m \left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right) 是一一对应的。

特别地，对于 x∈(Z/NZ)×x \in \left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}，不难证明此时 x∈(Z/NZ)×⟷1−1(x1,⋯ ,xm)∈∏i=1m(Z/piαiZ)×x \in \left(\mathbb{Z}/N\mathbb{Z}\right)^{\times} \stackrel{1-1}{\longleftrightarrow} (x_1, \cdots, x_m)\in \prod\limits_{i=1}^m \left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}

不难证明 r≡ri(modφ(piαi)),∀i∈[m]r \equiv r_i\pmod{\varphi(p_i^{\alpha_i})}, \forall i\in [m]，即：

xr≡1(mod∏i=1mpiαi)⟷1−1{x1r1≡1(modp1α1)⋮xmrm≡1(modpmαm)x^r\equiv 1\pmod{\prod\limits_{i = 1}^mp_i^{\alpha_i}} \stackrel{1-1}{\longleftrightarrow} \begin{cases} x_1^{r_1}\equiv 1\pmod{p_1^{\alpha_1}}\\ \qquad\vdots\\ x_m^{r_m}\equiv 1\pmod{p_m^{\alpha_m}}\\ \end{cases}

这意味着，x←U((Z/NZ)×)  ⟺  (x1,⋯ ,xm)←U(∏i=1m(Z/piαiZ)×)x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)\iff (x_1,\cdots, x_m)\leftarrow U\left(\prod\limits_{i=1}^m \left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right) ，这里 xi,∀i∈[m]x_i,\forall i\in [m] 是相互独立选取的，从而 ri,∀i∈[m]r_i,\forall i\in [m] 也是相互独立的。

从而得到概率计算上的转化：

Pr⁡x←U((Z/NZ)×)(2∣r ∧ xr2≢−1(modN))=1−Pr⁡x←U((Z/NZ)×)(2∤r ∨ xr2≡−1(modN))=1−Pr⁡x←U((Z/NZ)×)(2∤r ∨ xr2≡−1(mod∏i=1mpiαi))⩾1−Pr⁡(x1,⋯ ,xm)←U(∏i=1m(Z/piαiZ)×)(v2(ri)=v2(r), ∀ i∈[m])=1−Pr⁡(x1,⋯ ,xm)←U(∏i=1m(Z/piαiZ)×)(v2(ri)=v2(r), ∀ i∈[m])=1−∏i=1mPr⁡xi←U((Z/piαiZ)×),i=1,⋯ ,m(v2(ri)=v2(r))={0m=11−∏i=2mPr⁡xi←U((Z/piαiZ)×),i=1,⋯ ,m(v2(ri)=v2(r1))m⩾2\begin{aligned} &\Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\mid r\ \wedge\ x^{\frac{r}{2}} \not\equiv -1\pmod{N} \right)\\ =&1 - \Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\nmid r\ \vee\ x^{\frac{r}{2}} \equiv -1\pmod{N} \right)\\ =&1 - \Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\nmid r\ \vee\ x^{\frac{r}{2}} \equiv -1\pmod{\prod\limits_{i = 1}^mp_i^{\alpha_i}} \right)\\ \geqslant& 1 - \Pr\limits_{(x_1,\cdots, x_m)\leftarrow U\left(\prod\limits_{i=1}^m \left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right)}\left(v_2(r_i) = v_2(r),\ \forall\ i\in[m] \right)\\ =& 1 - \Pr\limits_{(x_1,\cdots, x_m)\leftarrow U\left(\prod\limits_{i=1}^m \left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right)}\left(v_2(r_i) = v_2(r),\ \forall\ i\in[m] \right)\\ =& 1 - \prod\limits_{i=1}^m\Pr\limits_{x_i\leftarrow U\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right), i=1, \cdots,m}\left(v_2(r_i) = v_2(r) \right)\\ =&\begin{cases} 0 &m = 1\\\\ 1 - \prod\limits_{i=2}^m\Pr\limits_{x_i\leftarrow U\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right), i=1, \cdots,m}\left(v_2(r_i) = v_2(r_1) \right) &m\geqslant 2 \end{cases} \end{aligned}

注：我们在这里将r=ordN(x)r = \text{ord}_N(x)剥离开，因为 rr 总是与 rir_i 的选取有关，而 rir_i 之间是相互独立的。

下面我们的任务就是对 Pr⁡xi←U((Z/piαiZ)×)(v2(ri)=v2(r1))\Pr\limits_{x_i\leftarrow U\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right)}\left( v_2(r_i) = v_2(r_1) \right) 进行计算了。

这里需要第一个 Insight，就是原根存在定理：

原根存在定理（部分）：对奇素数 pip_i，正整数 αi\alpha_i，(Z/piαiZ)×\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times} 为循环群。

从而我们可以设 (Z/piαiZ)×\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times} 生成元为 gig_i。进一步就有 xi=x(modpiαi)=giki(modpiαi)x_i = x\pmod{p_i^{\alpha_i}} = g_i^{k_i}\pmod{p_i^{\alpha_i}}，ri=ordpiαi(xi)r_i = \text{ord}_{p_i^{\alpha_i}}(x_i)，立即就有：

gikiri≡xiri≡1(modpiαi),ri∣r,ri∣φ(piαi)=piαi−1(pi−1)g_i^{k_ir_i}\equiv x_i^{r_i}\equiv 1\pmod{p_i^{\alpha_i}} ,\quad r_i\mid r ,\quad r_i \mid \varphi\left(p_i^{\alpha_i}\right) = p_i^{\alpha_i-1}(p_i - 1)

由熟知结论：

ri=φ(piαi)gcd⁡(φ(piαi),ki)r_i = \dfrac{\varphi(p_i^{\alpha_i})}{\gcd\left( \varphi(p_i^{\alpha_i}), k_i \right)}

根据 ordpiαi(gi)=φ(piαi)\text{ord}_{p_i^{\alpha_i}}(g_i) = \varphi\left(p_i^{\alpha_i}\right) 计算得到：

v2(ri)=v2(pi−1)−min⁡(v2(pi−1),v2(ki))v_2(r_i) = v_2(p_i - 1)- \min\left(v_2(p_i - 1), v_2(k_i)\right)

而 xi∈(Z/piαiZ)×⟷1−1ki∈Z/piαi(pi−1)Zx_i\in \left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times} \stackrel{1-1}{\longleftrightarrow} k_i\in \mathbb{Z}/p_i^{\alpha_i}(p_i - 1)\mathbb{Z}，从而需要第二个 Insight：

  • xi∈QNR((Z/piαiZ)×)  ⟺  2∤ki  ⟺  v2(ki)=0  ⟺  v2(ri)=v2(pi−1)x_i\in \text{QNR}\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right) \iff 2\nmid k_i \iff v_2(k_i)=0 \iff v_2(r_i) = v_2(p_i - 1) →\rightarrow 概率 1/21/2
  • xi∈QR((Z/piαiZ)×)  ⟺  2∣ki  ⟺  v2(ki)⩾1  ⟺  v2(ri)<v2(pi−1)x_i\in \text{QR}\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right) \iff 2\mid k_i \iff v_2(k_i) \geqslant 1 \iff v_2(r_i) < v_2(p_i - 1) →\rightarrow 概率 1/21/2

对于 i⩾2i\geqslant 2，r1r_1（特别地 v2(r1)v_2(r_1)）都是一个客观存在的值（相互独立），因此只需要考虑对 v2(r1)v_2(r_1) 的具体大小进行讨论即可：

Pr⁡xi←U((Z/piαiZ)×)(v2(ri)=v2(r1)){⩽12v2(r1)<v2(pi−1)=12v2(r1)=v2(pi−1)=0v2(r1)>v2(pi−1)\begin{aligned} \Pr\limits_{x_i\leftarrow U\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right)}\left( v_2(r_i) = v_2(r_1) \right) \begin{cases} \leqslant \dfrac{1}{2} &v_2(r_1) < v_2(p_i - 1)\\\\ =\dfrac{1}{2} &v_2(r_1) = v_2(p_i - 1)\\\\ = 0 &v_2(r_1) > v_2(p_i - 1) \end{cases} \end{aligned}

即：

Pr⁡xi←U((Z/piαiZ)×)(v2(ri)=v2(r1))⩽ 12,i=2,⋯ ,m\Pr\limits_{x_i\leftarrow U\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right)}\left( v_2(r_i) = v_2(r_1) \right) \leqslant\ \frac{1}{2},\quad i=2,\cdots, m

从而 m⩾2m \geqslant 2 时：

Pr⁡x←U((Z/NZ)×)(2∣r ∧ xr2≢−1(modN))⩾ 1−∏i=1mPr⁡xi←U((Z/piαiZ)×)(v2(ri)=v2(r))⩾1−12m−1\begin{aligned} \Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\mid r\ \wedge\ x^{\frac{r}{2}} \not\equiv -1\pmod{N} \right) &\geqslant\ 1 - \prod_{i=1}^m\Pr\limits_{x_i\leftarrow U\left(\left(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\right)^{\times}\right)}\left( v_2(r_i) = v_2(r) \right)\\ &\geqslant 1 - \frac{1}{2^{m - 1}} \end{aligned}

现在剩下 m=1m = 1 的情况了。事实上我们注意到 2∣r2\mid r 时：

(xr2−1)⋅(xr2+1)≡0(modp1α1)\left( x^{\frac{r}{2}} - 1\right)\cdot\left( x^{\frac{r}{2}} + 1\right) \equiv 0\pmod{p_1^{\alpha_1}}

若 xr2+1≢0(modp1α1)x^{\frac{r}{2}} + 1\not\equiv 0\pmod{p_1^{\alpha_1}}，由阶的极小性同样有 xr2−1≢0(modp1α1)x^{\frac{r}{2}} - 1\not\equiv 0\pmod{p_1^{\alpha_1}}，此时：

p1∣gcd⁡(xr2+1,xr2−1)=gcd⁡(xr2+1,2)⇒p1∣2p_1\mid \gcd\left(x^{\frac{r}{2}} + 1, x^{\frac{r}{2}} - 1\right) = \gcd\left(x^{\frac{r}{2}} + 1, 2\right) \Rightarrow p_1 \mid 2

显然矛盾。

综上所述，

Pr⁡x←U((Z/NZ)×)(2∣ordN(x) ∧ xr2≢−1(modN)){=0m=1⩾1−12m−1m⩾2\Pr\limits_{x\leftarrow U\left(\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}\right)}\left( 2\mid \text{ord}_N(x)\ \wedge\ x^{\frac{r}{2}} \not\equiv -1\pmod{N} \right) \begin{cases} = 0 & m = 1\\\geqslant 1 - \dfrac{1}{2^{m - 1}} & m\geqslant 2\end{cases}

前面做了哪些假设：

  • 提前去除 NN 的偶数素因子 22；
  • NN 为某个素因子幂的情况需要单独讨论；
  • 重点考虑选取的 xx 满足 gcd⁡(x,N)=1\gcd(x, N) = 1 的情况。

中间涉及了哪些计算：

  • 偶素数因子检测
  • 素数幂检测算法
  • 辗转相除法
  • 元素求阶算法
\begin{algorithm}
\caption{\textbf{大整数开根算法}}
\begin{algorithmic}
\State \textbf{输入：} 正整数 $N$，开根次数 $k$
\State \textbf{输出：} $[\sqrt[k]{N}]$
\State $a \gets 0,\ b \gets 1$
\While{$b^k < N$} \Comment{倍增法找上界，$O(\log N)$轮}
    \State $a \gets b$
    \State $b \gets 2b$
\EndWhile
\If{$b^k = N$} \Comment{恰好开尽}
    \State \Return $b$
\EndIf
\While{$a + 1 < b$} \Comment{二分查找，$O(k)$轮}
    \State $m \gets \lfloor (a + b) / 2 \rfloor$
    \If{$m^k \leqslant N$} \Comment{快速幂判定，$O(\log k \cdot \log^2 N)$}
        \State $a \gets m$
    \Else
        \State $b \gets m$
    \EndIf
\EndWhile
\State \Return $a$ \Comment{总复杂度 $O(k\log k \cdot \log^2 N)$}
\end{algorithmic}
\end{algorithm}
 2025-11-22   Math   Quantum  

下一篇