# 指数同余方程：离散对数子程序与 Grover 搜索的三次方加速

Shor 算法能在多项式时间内解单个离散对数，但两个指数通过加法耦合后，问题会重新变难。考虑有限域 $\mathbb F_q$ 上的方程

$$
af^x+bg^y=c,
\qquad a,b,c,f,g\in\mathbb F_q^\times.
$$

本课推导 van Dam--Shparlinski 算法：先用特征和证明“解一定出现在一个较窄矩形中”，再把 Shor 离散对数包装成 Grover 判定器。最终最坏时间为 $\widetilde O(q^{3/8})$，相对其文中经典 $\widetilde O(q^{9/8})$ 算法获得指数幂上的三次方改进，但仍不是输入长度 $\log q$ 的多项式时间。

## 1. 搜索空间由元素阶决定

记

$$
s=\operatorname{ord}(f),\qquad
t=\operatorname{ord}(g).
$$

只需考虑

$$
0\le x<s,\qquad0\le y<t,
$$

因为指数分别以 $s,t$ 为周期。量子阶查找可在 $\operatorname{poly}(\log q)$ 时间得到 $s,t$。以下不妨设 $s\ge t$。

固定 $y$ 后，方程等价于

$$
f^x=a^{-1}(c-bg^y).
$$

右侧若属于循环子群 $\langle f\rangle$，Shor 离散对数就能求出唯一的 $x\in\{0,\ldots,s-1\}$；否则该 $y$ 没有解。因此可以定义可逆量子子程序

$$
S(y)=
\begin{cases}
1,&\exists x:af^x+bg^y=c,\\
0,&\text{否则}.
\end{cases}
$$

每次 $S(y)$ 的成本关于 $\log q$ 为多项式。直接 Grover 搜索全部 $t$ 个 $y$ 需 $\widetilde O(\sqrt t)$，最坏可到 $q^{1/2}$；还需要数论结构进一步缩小范围。

## 2. 特征和给出的“短边必有解”引理

令 $N(r,s)$ 表示满足

$$
0\le x<s,\qquad0\le y<r
$$

的解数，其中 $r\le t$。用乘法特征的正交关系表示“某元素属于 $\langle f\rangle$”，再对截断序列 $g^0,\ldots,g^{r-1}$ 使用特征和界，可得

$$
N(r,s)=\frac{rs}{q-1}+O(q^{1/2}\log q).
$$

主项是随机模型下的期望解数；误差项衡量乘法子群与加法平移之间的不均匀性。选择

$$
r=\left\lceil Cq^{3/2}s^{-1}\log q\right\rceil
$$

并取足够大的常数 $C$，若 $r\le t$，则主项压过误差，保证前 $r$ 个 $y$ 中至少有一个解。若 $r>t$，引理不给存在性，但完整的 $t$ 个候选本来就已经较少，可以全部交给量子搜索。

这个步骤至关重要：Grover 只加速一个已经确定的候选集合，不能自己证明集合外没有解。特征和界负责完备性，量子搜索负责找到见证。

## 3. 两种分支的复杂度推导

### 情形 A：$r\le t$

Grover 搜索 $y\in\{0,\ldots,r-1\}$ 的成本为

$$
\widetilde O(\sqrt r)
=\widetilde O(q^{3/4}s^{-1/2}).
$$

又因 $s\ge t\ge r$，

$$
s^2\ge sr\gtrsim q^{3/2},
$$

所以 $s\gtrsim q^{3/4}$，代回得到

$$
\widetilde O(q^{3/8}).
$$

### 情形 B：$r>t$

搜索全部 $t$ 个候选需 $\widetilde O(\sqrt t)$。由 $t<r$ 得

$$
st<sr\lesssim q^{3/2}\operatorname{polylog}q.
$$

同时 $t\le s$，故

$$
\sqrt t\le(st)^{1/4}
=\widetilde O(q^{3/8}).
$$

两种分支合起来即可在 $\widetilde O(q^{3/8})$ 时间内找解，或确定整个周期矩形中无解。

## 4. 一个小例子

在 $\mathbb F_7$ 中取

$$
a=b=1,quad f=3,quad g=2,quad c=5.
$$

$3$ 的阶为 6，$2$ 的阶为 3。固定 $y=1$ 时，

$$
a^{-1}(c-bg^y)=5-2=3.
$$

离散对数子程序求解 $3^x=3$，返回 $x=1$，所以 $(x,y)=(1,1)$，并直接验证

$$
3^1+2^1=5\pmod7.
$$

在大域中，算法不是顺序尝试 $y$；它把“计算 $g^y$、检查子群成员关系、求离散对数、验证等式”全部做成相干子程序，再由振幅放大选择成功分支。

## 5. 更强承诺与平均情形

若 $s,t$ 很大，特征和公式不仅保证存在解，还给出许多解。带有 $m$ 个标记项的 Grover 搜索成本从 $\sqrt r$ 降为 $\sqrt{r/m}$，论文得到

$$
\widetilde O\bigl(q^{1/2}(st)^{-1/4}\bigr)
$$

一类参数化界。对除 $o(q)$ 个目标 $c$ 外的典型情形，还能用平均平方估计把最坏 $q^{3/8}$ 改进为 $q^{1/3}$。

这些是不同输入承诺下的结论，不能把最好参数区间的复杂度写成无条件最坏界。特别地，所有这些算法对输入长度 $\log q$ 仍为指数时间；论文也明确没有解决相关半直积群 HSP 所需的多项式时间子程序。

## 6. 小结与习题

- 阶查找把搜索域限制为 $s\times t$ 的基本周期矩形。
- 特征和界把至少一个解压进宽为 $r$ 的条带。
- Shor 离散对数构成判定器，Grover 在 $y$ 上做平方根加速。
- $q^{9/8}\to q^{3/8}$ 是关于 $q$ 的三次方指数改进，不是关于 $\log q$ 的多项式算法。

1. 证明固定 $y$ 时，在 $0\le x<s$ 中至多有一个解。
2. 完整写出 $r\le t$ 分支从 $\sqrt r$ 到 $q^{3/8}$ 的不等式链。
3. 若 $f$ 是 $\mathbb F_q^\times$ 的生成元，说明除右侧为零外，为什么任意固定 $y$ 都能用一次离散对数求出 $x$。
4. 解释为什么特征和引理负责算法的“无漏解”，Grover 本身不负责。

## 参考文献

- Zoo 编号 111：Wim van Dam 与 Igor E. Shparlinski, [Classical and Quantum Algorithms for Exponential Congruences](https://arxiv.org/abs/0804.1109).
- Peter Shor, [Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer](https://doi.org/10.1137/S0097539795293172).