量子离散对数算法

阐述

问题

给定乘法群 $G$ 和其中的群元 $a,b$，找到整数 $k$ 使得 $b^k=a$。

我们将只考虑群是模质数同余的乘法群的情况，该情况下 $g$ 是生成元当且仅当 $g^{p-1}\equiv 1$。

$$g^{x} \equiv h(\bmod P)$$

算法

构造算符

$$\left.\left.U_{g}:|y(\bmod P)\rangle \rightarrow \mid g y \bmod P\right)\right\rangle$$

它具有本征值 $e^{-2\pi i k/(p-1)}$ 和相有的本征态

$$\left|v_{k}\right\rangle=\frac{1}{\sqrt{P-1}}\left(|1\rangle+e^{2 \pi k i \frac{1}{P-1}}|g\rangle+e^{2 \pi i k \frac{2}{P-1}}\left|g^{2}\right\rangle+e^{2 \pi i k \frac{3}{P-1}}\left|g^{3}\right\rangle+\ldots e^{2 \pi i k \frac{P-2}{P-1}}\left|g^{P-2}\right\rangle\right)$$

1. 使用初始态$|1\rangle=\frac{1}{\sqrt{P-1}} \sum_{k=0}^{P-2}\left|v_{k}\right\rangle$
2. 进行相位估计，得到 $\frac{1}{\sqrt{P-1}} \sum_{k=0}^{P-2}\left|v_{k}\right\rangle \sum_{\theta_{k}^{(j)}} \alpha_{j}\left|\theta_{k}^{(j)}\right\rangle$
3. 测量得到某个 $v_k$ 和 $k$
4. 由于 $v_k$ 也是 $U_h$ 的本征值，可以用它来测量得到 $kx\mod p$
5. 找到 $k$ 的逆元，从而计算 $x$

实例

性质

相关内容

量子离散对数算法可以快速计算离散对数，所以对 Diffie-Hellman 密钥交换协议产生了威胁。

参考文献

• Discrete logarithm