指数同余方程

Shor 离散对数算法告诉我们：有限域乘法群中的单个离散对数问题——给定 $f$ 与 $f^x$，求 $x$——可以在 $\mathrm{poly}(\log q)$ 时间内解决。但是，一旦两个指数通过加法耦合在一起，问题会重新变难。本词条研究有限域 ${\mathbb{F}}_q$ 上的指数同余方程 (exponential congruence)

$$a{f}^x+b{g}^y=c,a,b,c,f,g\in {\mathbb{F}}_q^{\times },$$

其中 $a,b,c,f,g$ 已知，要求的是指数对 $(x,y)$。本词条将完整推导 van Dam 与 Shparlinski 的量子算法：先用乘法特征和证明”解一定出现在一个较窄的矩形条带中”，再把 Shor 离散对数包装成一个可相干调用的判定器，交给 Grover 搜索 与振幅放大去找到解。最终的最坏情形运行时间为 $\tilde{O}(q^{3/8})$，相对论文中给出的经典 $\tilde{O}(q^{9/8})$ 算法，在 $q$ 的指数幂上获得三次方改进（$9/8\to 3/8$）；但请注意，它仍然不是输入长度 $\log q$ 的多项式时间算法。

阅读本词条需要：有限域与循环群的基本概念，量子傅里叶变换与相位估计（作为 Shor 算法的内部，不需要重新推导），以及 Grover 搜索与振幅放大的结论。全课约定 $\tilde{O}(\cdot )$ 隐藏 $\log q$ 的多项式因子，$\lesssim$、$\gtrsim$ 在比较时忽略 $\mathrm{polylog}q$ 因子。

1. 问题背景：为什么两个指数会变难

1.1 从离散对数到指数同余

先回忆离散对数问题。设 ${\mathbb{F}}_q^{\times }$ 是 $q$ 元有限域的乘法群（它是 $q-1$ 阶循环群，这是有限域的标准事实），$f\in {\mathbb{F}}_q^{\times }$ 给定。离散对数问题是：给定 $z\in ⟨f⟩$，求 $x$ 使得 $f^x=z$。Shor 算法把它化为周期查找，配合量子傅里叶采样在 $\mathrm{poly}(\log q)$ 时间内求解——这是量子计算最著名的指数级加速之一。

现在看指数同余方程 $a{f}^x+b{g}^y=c$。如果两个未知数中有一个被固定，问题立刻退化：

• 固定 $y$，移项得 $f^x=a^{-1}(c-b{g}^y)$，这是一个以 $f$ 为底的离散对数；
• 固定 $x$，移项得 $g^y=b^{-1}(c-a{f}^x)$，这是一个以 $g$ 为底的离散对数。

也就是说，“单指数”的版本在量子计算机上是容易的。困难来自两个指数的真正耦合：加法 $a{f}^x+b{g}^y$ 把两个循环群的乘法结构混在一起。量子傅里叶采样擅长处理的是”周期函数""阿贝尔群结构”，而映射 $(x,y)\mapsto a{f}^x+b{g}^y$ 的等值集合 $\{(x,y):a{f}^x+b{g}^y=c\}$ 一般不构成群，也不具有可以直接傅里叶采样的周期结构。因此，既有的 HSP 机器无法直接吞下这个问题。

这个问题为什么值得研究？至少有三层动机。第一，它是检验”量子加速边界”的天然试金石：单离散对数有多项式时间量子算法，而稍加耦合之后，最好的量子算法仍然要花费关于 $q$ 的指数时间——指数幂从经典的 $9/8$ 降到 $3/8$，是一个实质但不彻底的改进，画出了当前技术的边界。第二，指数同余与某些半直积群上的隐子群问题 (hidden subgroup problem, HSP) 密切相关：如果能以 $\mathrm{poly}(\log q)$ 时间求解此类同余，就能为相应的 HSP 提供新的多项式时间量子算法；van Dam–Shparlinski 的论文明确讨论了这层联系，同时也明确指出他们的结果没有解决那个 HSP 所需的多项式时间子程序——这是本词条第 7 节要再次强调的保留条款。第三，指数同余的解数估计本身是解析数论中的经典问题，乘法特征和（Gauss 和、Weil 界一路的技术）在其中扮演核心角色；本词条可以看到这套经典工具如何与 Grover 搜索拼接成量子算法。

1.2 经典算法的瓶颈

经典计算机如何处理这个问题？朴素的办法是穷举：遍历所有候选的 $y$，对每个 $y$ 计算 $z=a^{-1}(c-b{g}^y)$，然后判断 $z$ 是否落在子群 $⟨f⟩$ 中、若落在其中则求出离散对数 $x$。瓶颈在第二步：经典模型下没有多项式时间的离散对数算法。用通用群算法（如 Shanks 的大步小步法）在以 $f$ 为底、阶为 $s$ 的群中做一次成员判定兼离散对数，需要 $\tilde{O}(\sqrt{s})$ 次群运算，最坏情形 $s\approx q$ 时单次检查的代价就是 $\tilde{O}(q^{1/2})$。这个 $\sqrt{s}$ 不是偶然的：在只使用群运算黑箱的通用群模型中，离散对数有 $\Omega (\sqrt{s})$ 的下界，因此大步小步在通用意义下已是最优——除非利用 ${\mathbb{F}}_q^{\times }$ 的具体表示（如指数演减法），否则经典每次候选检查都甩不掉这个平方根因子。

把”候选数 $\times$ 单次离散对数代价”与下文将要推导的数论引理结合起来，van Dam–Shparlinski 给出的经典算法最坏时间为 $\tilde{O}(q^{9/8})$。这个 $9/8$ 本身就是一个参数平衡的结果：候选集合的宽度随 $s$ 增大而变窄，而单次判定的 $\sqrt{s}$ 随 $s$ 增大而变贵，最坏情形出现在两者顶住的临界点上。我们先把这个数当作经典基准记住，第 5.3 节会逐项重现它的推导，并看清量子算法的 $q^{3/8}$ 究竟改进了哪几个因子。

1.3 算法概览

量子算法由三个部件拼接而成，每个部件各司其职：

1. 阶查找：用 Shor 算法求出 $s=\mathrm{ord}(f)$、$t=\mathrm{ord}(g)$，把搜索范围限定为 $s\times t$ 的基本周期矩形；
2. 特征和引理（纯数论，经典证明）：证明当 $s$ 不太小时，解必定出现在 $y$ 轴方向宽度约为 $q^{3/2}{s}^{-1}$ 的窄条带内，从而把搜索空间从 $t$ 压缩到 $r\ll t$；
3. Grover 搜索：把”固定 $y$、求离散对数、验证等式”做成相干预言机，在压缩后的候选集上做平方根加速搜索。

三个部件中，只有第 3 步是”搜索加速”，第 1 步是”参数确定”，而第 2 步负责完备性——保证搜索范围之外确实没有遗漏的解。这个分工在第 3 节和第 5 节会反复出现。

2. 搜索空间由元素阶决定

记

$$s=\mathrm{ord}(f),t=\mathrm{ord}(g),$$

即 $f$、$g$ 在乘法群 ${\mathbb{F}}_q^{\times }$ 中的阶：$s$ 是使 $f^s=1$ 成立的最小正整数，$t$ 同理。由循环群的基本事实，$s\mid (q-1)$ 且 $t\mid (q-1)$。

指数函数以阶为周期：对任意整数 $x$，$f^{x+s}=f^x{f}^s=f^x$。因此，如果 $(x,y)$ 是解，那么 $x\mathrm{mod}s$ 与 $y\mathrm{mod}t$ 的代表元也给出一个解；反过来，每个解的指数在模 $s$、模 $t$ 意义下唯一。于是我们只需考虑

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

称这个 $s\times t$ 的整数矩形为基本周期矩形。搜索空间的大小从”无限”变成 $st$，而 $st\le (q-1{)}^2$。

阶 $s,t$ 本身如何得到？用 Shor 的阶查找子程序（与因数分解中完全相同的部分）：对乘法算子 $|z⟩\mapsto |fz\mathrm{mod}q⟩$ 做相位估计，以 $\mathrm{poly}(\log q)$ 的时间求出 $s$；同理求出 $t$。这一步的代价被 $\tilde{O}(\cdot )$ 吸收，后文不再计入。由于方程关于 $(a,f,x)$ 与 $(b,g,y)$ 对称（交换两组变量的角色，方程形状不变），以下不妨设 $s\ge t$。

接下来是关键的一步约化。固定某个 $y\in \{0,\dots ,t-1\}$，方程等价于

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

记右端的值为 $z_y:=a^{-1}(c-b{g}^y)$。分两种情况：

• 若 $z_y$ 属于循环子群 $⟨f⟩=\{1,f,f^2,\dots ,f^{s-1}\}$，那么离散对数方程 $f^x=z_y$ 在 $\{0,\dots ,s-1\}$ 中有唯一解 $x$（因为 $f$ 的阶恰好是 $s$，映射 $x\mapsto f^x$ 在这个区间上是单射），Shor 离散对数算法可以在 $\mathrm{poly}(\log q)$ 时间内求出它；
• 若 $z_y\notin ⟨f⟩$（包括 $z_y=0$ 的情形，因为 $⟨f⟩$ 中的元素都是非零的），则这个 $y$ 不可能对应任何解。

因此我们可以定义一个判定函数

$$S(y)=\{\begin{array}{ll}1,& \exists x\in \{0,\dots ,s-1\}:a{f}^x+b{g}^y=c,\\ 0,& \text{否则}.\end{array}$$

每次调用 $S(y)$ 的成本关于 $\log q$ 为多项式：一次模幂 $g^y$、一次域上的线性组合、一次 Shor 离散对数、一次验证。第 4.1 节会说明如何把它做成可相干调用的量子预言机，目前先把它当作”多项式代价的黑箱判定器”。

上面的”唯一性”观察还有一个计数层面的推论，后文会反复用到：每个 $y$ 至多贡献一个解。因此，对任何候选集合 $Y\subseteq \{0,\dots ,t-1\}$，矩形 $\{0,\dots ,s-1\}\times Y$ 中的解数恰好等于 $Y$ 中标记项的个数 $\#\{y\in Y:S(y)=1\}$。换句话说，下一节要估计的”条带中的解数” $N(r,s)$，正是 Grover 搜索框架里”标记项个数 $m$“的化身——第 7 节讨论多解加速时，这个对应关系会把数论估计与查询复杂度直接焊接起来。

有了 $S(y)$，最朴素的量子算法是：直接在 $y\in \{0,\dots ,t-1\}$ 上做 Grover 搜索，寻找使 $S(y)=1$ 的 $y$。成本为

$$\tilde{O}(\sqrt{t}).$$

但这还不够好：$t$ 最坏可以大到 $q-1$（例如 $g$ 是 ${\mathbb{F}}_q^{\times }$ 的生成元时），此时 $\sqrt{t}\approx q^{1/2}$，比我们的目标 $q^{3/8}$ 大得多（比较指数：$1/2=4/8>3/8$）。要再进一步，必须利用数论结构把候选集压缩到 $t$ 的真子集——这正是下一节的特征和引理。

3. 特征和与”短边必有解”引理

本节的目标：证明当 $s$ 不太小时，解必然出现在 $y$ 轴方向一个宽度远小于 $t$ 的条带内。整条推理链是经典的解析数论，不涉及任何量子计算；它的产出是一个存在性保证，供量子搜索使用。

3.1 乘法特征与子群成员关系的代数表达

我们需要一个代数工具来”数”满足条件的 $y$：对每个 $y$，要判断 $z_y=a^{-1}(c-b{g}^y)$ 是否属于子群 $⟨f⟩$。解析数论处理这类”子群成员关系”的标准工具是乘法特征 (multiplicative character)。

乘法特征 $\chi$ 是从 ${\mathbb{F}}_q^{\times }$ 到单位圆周 $\{w\in \mathbb{C}:|w|=1\}$ 的群同态，即 $\chi (uv)=\chi (u)\chi (v)$。由于 ${\mathbb{F}}_q^{\times }$ 是 $q-1$ 阶循环群，它的全部乘法特征也构成一个 $q-1$ 阶循环群（对偶群）：取定生成元后，特征就是 ${\xi }^k\mapsto {\omega }^{jk}$（$j=0,1,\dots ,q-2$），其中 $\omega$ 是 $q-1$ 次单位根。特征满足正交关系：对 $z\in {\mathbb{F}}_q^{\times }$，

$$\frac{1}{q-1}\sum _{\chi }\chi (z)=\{\begin{array}{ll}1,& z=1,\\ 0,& z\ne 1,\end{array}$$

其中求和取遍全部 $q-1$ 个乘法特征。（当 $z=1$ 时每一项都是 $1$；当 $z\ne 1$ 时，存在某个特征 ${\chi }_1$ 使 ${\chi }_1(z)\ne 1$，两边同乘 ${\chi }_1(z)$ 后求和集不变，于是和只能为 $0$。）我们约定 $\chi (0)=0$。

现在把正交关系”升级”为子群成员关系的指标函数。设 $s=\mathrm{ord}(f)$，并记

$$n:=\frac{q-1}{s},$$

即子群 $⟨f⟩$ 在 ${\mathbb{F}}_q^{\times }$ 中的指数（由于 $s\mid (q-1)$，$n$ 是整数）。商群 ${\mathbb{F}}_q^{\times }/⟨f⟩$ 是 $n$ 阶循环群。在所有乘法特征中，恰有 $n$ 个在 $⟨f⟩$ 上恒取 $1$——它们正是商群的全部特征（每个这样的特征只依赖于陪集 $z⟨f⟩$，而 $n$ 阶循环群恰有 $n$ 个特征）。把这 $n$ 个特征取出来，对任意 $z\in {\mathbb{F}}_q^{\times }$ 定义

$$1_{⟨f⟩}(z):=\frac{1}{n}\sum _{\begin{array}{c}\chi \text{在}⟨f⟩\text{ 上平凡}\end{array}}\chi (z).$$

这个和式就是子群成员关系的精确指标函数：若 $z\in ⟨f⟩$，则每一项 $\chi (z)=1$，和为 $n$，除以 $n$ 得 $1$；若 $z\notin ⟨f⟩$，则 $z$ 在商群中的像 $\bar{z}\ne 1$，和式等于商群上的正交关系 ${\sum }_{\hat{\chi }}\hat{\chi }(\bar{z})=0$，除以 $n$ 得 $0$。于是我们得到了一个完全代数的判据：

$$z\in ⟨f⟩⟺1_{⟨f⟩}(z)=1.$$

3.2 解数估计：主项与误差项

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

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

的解 $(x,y)$ 的个数，其中 $r\le t$ 是待定的条带宽度。由上节的讨论，固定 $y$ 时解的个数恰为 $1_{⟨f⟩}(z_y)$（属于子群恰对应唯一一个 $x$，否则为零），因此

$$N(r,s)=\sum _{y=0}^{r-1}{1}_{⟨f⟩}\left(a^{-1}(c-b{g}^y)\right)=\frac{1}{n}\sum _{\chi \text{在}⟨f⟩\text{ 上平凡}}\sum _{y=0}^{r-1}\chi \left(a^{-1}(c-b{g}^y)\right).$$

第二个等号只是把指标函数的定义代入并交换求和次序。现在这个双重和可以按特征分成两部分来估计。

主项：平凡特征 ${\chi }_0$。 ${\chi }_0$ 在所有非零元上取 $1$，所以内层和为 ${\sum }_{y=0}^{r-1}{\chi }_0(z_y)=r-\#\{y:z_y=0\}$。注意 $z_y=0$ 等价于 $c=b{g}^y$，在 $0\le y<r\le t$ 中至多发生一次（$g$ 的阶是 $t$，$g^y$ 在一个周期内两两不同）。所以平凡特征的贡献是

$$\frac{1}{n}\left(r+O(1)\right)=\frac{rs}{q-1}+O(1),$$

其中用了 $n=(q-1)/s$，即 $\frac{1}{n}=\frac{s}{q-1}$。后面的 $O(1)$ 会被最终误差项吸收，以下不再单独写出。

误差项：其余 $n-1$ 个非平凡特征。 对每个非平凡特征 $\chi$，内层和

$$T_{\chi }:=\sum _{y=0}^{r-1}\chi \left(c-b{g}^y\right)$$

是一个”沿几何序列 $g^y$ 取值”的不完全乘法特征和。解析数论对这类和有通用上界：完全和的平方根抵消（Weil 界的典型尺度）给出 $q^{1/2}$ 量级，把截断区间补全为完全和的标准技术再付出一个 $\log q$ 因子，合起来形如

$$\left|T_{\chi }\right|=O\left(q^{1/2}\log q\right),$$

且该界对所有非平凡 $\chi$ 一致成立。这里我们只做定性说明：$q^{1/2}$ 反映的是”随机 ±1 序列求和的平方根涨落”这一普遍现象（Weil 界说明代数族特征和确实达到随机行为的尺度），$\log q$ 是不完全和相对于完全和的技术性损失。

最后把两部分合并。非平凡特征共有 $n-1$ 个，每个权重 $1/n$，因此它们对 $N(r,s)$ 的总贡献的绝对值不超过

$$\frac{1}{n}\sum _{\chi \ne {\chi }_0}|T_{\chi }|\le \frac{n-1}{n}\cdot \underset{\chi \ne {\chi }_0}{\max }|T_{\chi }|=O\left(q^{1/2}\log q\right).$$

注意这里的要点：$1/n$ 这个平均因子使得误差项取决于单个特征和的最大值，而不是 $n$ 个特征和的总和——所以无论 $n$ 多大，误差项都保持在 $q^{1/2}\log q$ 的尺度。合起来我们得到解数渐近公式

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

公式的直观解读。 主项 $\frac{rs}{q-1}$ 正是随机模型下的期望解数：把 $z_y$ 想象成 ${\mathbb{F}}_q^{\times }$ 中的随机元素，它落在占比 $\frac{s}{q-1}=\frac{1}{n}$ 的子群 $⟨f⟩$ 中的概率是 $\frac{s}{q-1}$，$r$ 次独立尝试的期望命中数就是 $\frac{rs}{q-1}$。误差项 $O(q^{1/2}\log q)$ 则衡量真实序列 $c-b{g}^y$ 与随机模型的偏离——它来自乘法子群结构（$g$ 的幂）与加法平移（减 $c$、除以 $a$）之间的相互作用，而特征和界告诉我们：这种偏离至多是平方根量级的涨落，不会系统性地把解”排挤出”任何一段区间。

3.3 条带宽度的选取

渐近公式立刻给出一个存在性判据：只要主项压过误差项，$N(r,s)$ 就是正的，条带内必有解。具体地，设误差项 $O(q^{1/2}\log q)$ 中的隐含常数为 $C^{\prime }$。若我们能保证

$$\frac{rs}{q-1}\ge 2C^{\prime }{q}^{1/2}\log q,$$

那么

$$N(r,s)\ge \frac{rs}{q-1}-C^{\prime }{q}^{1/2}\log q\ge C^{\prime }{q}^{1/2}\log q>0,$$

条带中至少有一个解（事实上至少有主项一半那么多的解）。把上面的不等式解出 $r$：两边乘以 $\frac{q-1}{s}$，并用 $q-1<q$，只需

$$r\ge 2C^{\prime }\frac{(q-1)q^{1/2}\log q}{s},$$

取 $C=2C^{\prime }$，定义

$$r=\lceil C{q}^{3/2}{s}^{-1}\log q\rceil .$$

于是我们证明了本词条的核心数论事实：

Lemma（短边引理）. 设 $r=\lceil C{q}^{3/2}{s}^{-1}\log q\rceil$，其中 $C$ 是充分大的绝对常数。若 $r\le t$，则存在 $y\in \{0,\dots ,r-1\}$ 与 $x\in \{0,\dots ,s-1\}$ 满足 $a{f}^x+b{g}^y=c$。Q.E.D.

两种互补的情形。 这个引理是否给出存在性，取决于算出来的 $r$ 与实际周期 $t$ 的大小关系：

• 若 $r\le t$：引理适用，前 $r$ 个 $y$ 中必有解。搜索空间从 $t$ 压缩到 $r$；
• 若 $r>t$：引理不适用（它不排除”前 $t$ 个 $y$ 中无解”的可能），但此时 $t<r$ 本身就很小，完整的 $t$ 个候选已经不多，可以全部交给量子搜索。此时搜索整个基本周期矩形，不会有任何遗漏。

这个步骤至关重要，值得强调：Grover 搜索只能加速”在一个已经确定的候选集合中找解”，它不能自己证明集合之外没有解。 如果候选集合选小了，Grover 找到解固然好，找不到时我们无法断定原方程无解。特征和引理负责的正是这个完备性保证：要么把解压缩进宽度为 $r$ 的条带（情形 $r\le t$），要么确认完整候选集本身已经足够小（情形 $r>t$）。特征和界负责”无漏解”，量子搜索负责”找到见证”，两者缺一不可。

4. 量子算法

4.1 判定器 $S(y)$ 的相干实现

Grover 搜索要求预言机以相干方式工作：对叠加态 ${\sum }_y{\alpha }_y|y⟩$，一次调用就要同时算出所有 $S(y)$，而不能逐个测量。我们按标准的”计算—标志—相位翻转—反计算”模式实现 $S(y)$，分五步：

1. 计算 $g^y$：用平方-乘算法实现可逆模幂 $|y⟩|0⟩\mapsto |y⟩|g^y⟩$，需要 $O(\log t)=O(\log q)$ 次域乘法，总代价 $\mathrm{poly}(\log q)$；
2. 计算 $z_y=a^{-1}(c-b{g}^y)$：域上的乘法、减法都是可逆运算，代价 $\mathrm{poly}(\log q)$；
3. 相干离散对数：在 $z_y$ 上运行 Shor 离散对数线路（以 $f$ 为底），把所有测量推迟。线路输出一个候选对数 $\hat{x}$ 及工作区。关键点在于：Shor 算法的输出是可验证的——追加一个可逆比较器，计算标志比特 $b=[f^{\hat{x}}=z_y\wedge z_y\ne 0]$。若 $z_y\in ⟨f⟩$，Shor 算法以高概率给出正确的 $\hat{x}$，验证通过，$b=1$；若 $z_y\notin ⟨f⟩$，任何 $\hat{x}$ 都无法通过验证，$b=0$。因此 $b$ 正是 $S(y)$（误差概率见下）；
4. 相位翻转：对标志比特施加受控相位（或先制备 $|-⟩$ 做相位反冲），实现 $|y⟩\mapsto (-1{)}^{S(y)}|y⟩$；
5. 反计算：把第 1–3 步的线路逆向运行，清除工作区，只留下 $y$ 寄存器和已注入的相位。

两点技术说明。第一，Shor 离散对数是有界误差算法，单次成功概率为常数；把它独立重复 $O(\log \log q)$ 次并取验证通过的结果，可以把每次预言机调用的错误率压到 $1/\mathrm{poly}(q)$ 以下，对 Grover 迭代的总影响可以忽略，代价只是 $\mathrm{polylog}q$ 因子，被 $\tilde{O}(\cdot )$ 吸收。第二，搜索区间内标记项的数目 $m$ 事先未知（这正是问题的难点），因此不能用固定迭代次数的 Grover，而要用振幅放大一章中处理未知解数的版本（BBHT 式的指数增长尝试）：其成本为 $\tilde{O}(\sqrt{|Y|/m})$，其中 $Y$ 是搜索区间；最坏情形 $m\ge 1$ 时即 $\tilde{O}(\sqrt{|Y|})$。

4.2 整体流程

综合前面的所有部件，算法如下：

1. 阶查找：用 Shor 算法求 $s=\mathrm{ord}(f)$、$t=\mathrm{ord}(g)$。若 $s<t$，交换两组参数 $(a,f,x)\leftrightarrow (b,g,y)$ 的角色，使 $s\ge t$。代价 $\mathrm{poly}(\log q)$；
2. 计算条带宽度 $r=\lceil C{q}^{3/2}{s}^{-1}\log q\rceil$（纯经典算术）；
3. 分情形搜索：若 $r\le t$，令搜索区间 $Y=\{0,\dots ,r-1\}$；否则令 $Y=\{0,\dots ,t-1\}$。以 $S(y)$ 为预言机，在 $Y$ 上运行 BBHT 振幅放大搜索；
4. 输出：若搜索找到 $y$，再运行一次 Shor 离散对数求出 $x$ 并验证 $a{f}^x+b{g}^y=c$，输出 $(x,y)$；若搜索宣告无标记项，输出”无解”。

正确性由两方面的论证保证：当 $r\le t$ 时，短边引理保证 $Y$ 中必有标记项，振幅放大以高概率找到它；当 $r>t$ 时，$Y$ 覆盖整个基本周期矩形，搜索穷尽所有候选，找到即解、找不到即无解（至多受子程序有界误差影响，可忽略）。

5. 复杂度分析

现在逐项推导两种情形下的运行时间。搜索区间大小为 $|Y|$，每次预言机调用代价 $\mathrm{poly}(\log q)$，BBHT 搜索调用 $O(\sqrt{|Y|})$ 次（最坏情形），故总时间为 $\tilde{O}(\sqrt{|Y|})$，问题归结为估计 $\sqrt{|Y|}$。

5.1 情形 A：$r\le t$

搜索区间是条带，$|Y|=r$，成本为

$$\tilde{O}(\sqrt{r})=\tilde{O}\left(\sqrt{C{q}^{3/2}{s}^{-1}\log q}\right)=\tilde{O}\left(q^{3/4}{s}^{-1/2}\right),$$

其中第二步把常数 $C$ 和 $\sqrt{\log q}$ 吸收进 $\tilde{O}$。这个表达式里 $s$ 越小成本越高，所以我们需要 $s$ 的下界。由两条信息：

• $s\ge t\ge r$（第一条是约定，第二条是情形 A 的前提）；
• $r\ge C{q}^{3/2}{s}^{-1}\log q$（$r$ 的定义，上取整只会让它更大），即 $sr\gtrsim q^{3/2}$，

把第一条的 $r\le s$ 与第二条相乘的方向对齐：

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

两边开方得 $s\gtrsim q^{3/4}$。代回成本表达式——注意 $s^{-1/2}$ 关于 $s$ 递减，下界代入后得到上界：

$$q^{3/4}{s}^{-1/2}\lesssim q^{3/4}\cdot {\left(q^{3/4}\right)}^{-1/2}=q^{3/4}\cdot q^{-3/8}=q^{3/8}.$$

故情形 A 的成本为 $\tilde{O}(q^{3/8})$。直观地说：条带宽度 $r\approx q^{3/2}/s$ 随 $s$ 增大而变窄，而最坏情形出现在 $s$ 尽量小、但又被约束 $sr\gtrsim q^{3/2}$ 与 $r\le s$ 顶住的位置，解 $s\approx r\approx q^{3/4}$，此时 $\sqrt{r}\approx q^{3/8}$。

5.2 情形 B：$r>t$

搜索区间是整个周期边，$|Y|=t$，成本为 $\tilde{O}(\sqrt{t})$。由情形前提 $t<r$ 以及 $r$ 的定义（注意 $r>t\ge 1$ 意味着上取整不起主导作用，$r$ 与 $C{q}^{3/2}{s}^{-1}\log q$ 同阶）：

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

再由约定 $t\le s$，有 $t^2\le st$。于是

$$\sqrt{t}={\left(t^2\right)}^{1/4}\le (st{)}^{1/4}\lesssim {\left(q^{3/2}\right)}^{1/4}=q^{3/8},$$

polylog 因子照例被吸收。故情形 B 的成本同样是 $\tilde{O}(q^{3/8})$。

两种分支合起来：算法在 $\tilde{O}(q^{3/8})$ 时间内找到一组解 $(x,y)$，或确定整个基本周期矩形中无解。 这就是 van Dam–Shparlinski 的最坏情形量子界。

5.3 与经典算法的对比：三次方改进的来源

为了看清量子改进究竟来自哪里，我们用同一副骨架重建论文中的经典 $\tilde{O}(q^{9/8})$ 算法。骨架完全相同：阶已知（经典可用因数分解 $q-1$ 后逐个检验，代价被吸收）、短边引理相同、情形划分相同。唯一的差别在判定器 $S(y)$ 的代价：经典模型下，用 Shanks 大步小步法做子群成员判定兼离散对数需要 $\tilde{O}(\sqrt{s})$ 次群运算；而且经典没有振幅放大，搜索是逐项扫描。于是：

• 情形 A：扫描 $r$ 个候选，每个代价 $\sqrt{s}$，总成本

$$\tilde{O}\left(r\sqrt{s}\right)=\tilde{O}\left(q^{3/2}{s}^{-1}\cdot s^{1/2}\right)=\tilde{O}\left(q^{3/2}{s}^{-1/2}\right)\le \tilde{O}\left(q^{3/2}\cdot q^{-3/8}\right)=\tilde{O}\left(q^{9/8}\right),$$

其中最后一步同样用了情形 A 导出的 $s\gtrsim q^{3/4}$；

• 情形 B：扫描 $t$ 个候选，总成本 $\tilde{O}(t\sqrt{s})$。利用 $t\le s$ 给出的 $t\le (st{)}^{1/2}$（即 $t^{1/2}\le (st{)}^{1/4}$）：

$$t\sqrt{s}=(st{)}^{1/2}\cdot t^{1/2}\le (st{)}^{1/2}(st{)}^{1/4}=(st{)}^{3/4}\lesssim {\left(q^{3/2}\right)}^{3/4}=q^{9/8}.$$

对照量子版本，改进来自两个因子的叠加：搜索从逐项扫描 $O(|Y|)$ 变为振幅放大 $O(\sqrt{|Y|})$（平方根），单次判定从经典大步小步的 $\tilde{O}(\sqrt{s})$ 变为 Shor 算法的 $\mathrm{poly}(\log q)$（指数级）。两种情形中成本表达式的”主结构”——情形 A 的 $|Y|\cdot \sqrt{s}$ 与情形 B 的 $t\cdot \sqrt{s}$——被替换为 $\sqrt{|Y|}\cdot \mathrm{polylog}$ 与 $\sqrt{t}\cdot \mathrm{polylog}$，最终在 $q$ 的指数上体现为

$$\frac{9}{8}⟶\frac{3}{8},\frac{9/8}{3/8}=3,$$

即指数幂的三次方改进。必须强调的是这个改进的限度：输入 $a,b,c,f,g$ 用 $O(\log q)$ 个比特表示，而 $q^{3/8}=2^{(3/8){\log }_{2}q}$ 关于输入长度仍是指数时间。这与 Shor 算法对单个离散对数的多项式时间形成鲜明对比——加法耦合把问题从”多项式可解”推回了”指数可解但指数更小”的区间。

6. 一个小例子：${\mathbb{F}}_7$ 上的完整演算

渐近界的常数在 $q=7$ 这种玩具尺度上没有任何意义（短边引理里的 $C$ 是未指定的大常数），但算法的每个部件都可以完整地手工跑一遍。取

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

即求解 $3^x+2^y=5(\mathrm{mod}7)$。

第一步：阶查找。 ${\mathbb{F}}_7^{\times }=\{1,2,3,4,5,6\}$ 是 $6$ 阶循环群。逐次计算 $3$ 的幂：

$$3^0=1,3^1=3,3^2=2,3^3=6,3^4=4,3^5=5,3^6=1(\mathrm{mod}7),$$

所以 $s=\mathrm{ord}(3)=6$，$3$ 是生成元，$⟨3⟩={\mathbb{F}}_7^{\times }$。再算 $2$ 的幂：

$$2^0=1,2^1=2,2^2=4,2^3=1(\mathrm{mod}7),$$

所以 $t=\mathrm{ord}(2)=3$。基本周期矩形是 $0\le x<6$、$0\le y<3$，共 $18$ 个候选指数对。

第二步：逐 $y$ 运行判定器。 计算 $z_y=c-g^y=5-2^y\mathrm{mod}7$，并判断 $z_y\in ⟨3⟩$、求离散对数 $3^x=z_y$：

• $y=0$：$z_0=5-1=4$。查上面的幂表，$4=3^4$，故 $x=4$，$S(0)=1$；
• $y=1$：$z_1=5-2=3$。$3=3^1$，故 $x=1$，$S(1)=1$；
• $y=2$：$z_2=5-4=1$。$1=3^0$，故 $x=0$，$S(2)=1$。

三个候选全部命中，解为 $(x,y)\in \{(4,0),(1,1),(0,2)\}$。逐一验证：

$$3^4+2^0=4+1=5,3^1+2^1=3+2=5,3^0+2^2=1+4=5(\mathrm{mod}7).✓$$

第三步：对照解数公式。 条带取满整个周期 $r=t=3$ 时，公式的主项给出

$$N(3,6)\approx \frac{rs}{q-1}=\frac{3\times 6}{6}=3,$$

与实际解数 $3$ 完全吻合（当然在 $q=7$ 时误差项的渐近界无意义，这只是巧合级别的吻合，用来说明主项的含义）。

第四步：量子算法在这个例子上会做什么。 真实的算法不会顺序尝试 $y$：它先由相位估计求出 $s=6$、$t=3$；然后注意到 $s=q-1$（$f$ 是生成元），于是任意非零的 $z_y$ 必在 $⟨f⟩$ 中，判定器几乎总是回答 $1$；Grover/BBHT 在 $|Y|=3$ 个候选、$m=3$ 个标记项上以约 $\sqrt{3/3}=1$ 次查询级别的代价直接选中某个解，最后再跑一次离散对数输出 $(x,y)$。整个流程中”计算 $g^y$、检查子群成员关系、求离散对数、验证等式”都被做成相干子程序，由振幅放大选择成功分支——小例子里看不出加速，但线路结构与 $q$ 巨大时完全相同。

这个例子还演示了判定器退化的极端情形：当 $f$ 是生成元（$s=q-1$）时，子群成员检验形同虚设，问题实质上变成”$t$ 个候选中做搜索”，量子成本 $\tilde{O}(\sqrt{t})$ 直接就是好的。真正困难的情形是 $s,t$ 都远小于 $q$——那也正是特征和引理发挥压缩作用的舞台。

为了看清成员检验真正起筛选作用的样子，把同一个域上的底换成非生成元：取 $f=2$（阶 $s=3$，$⟨2⟩=\{1,2,4\}$）、$g=3$（阶 $t=6$），解 $2^x+3^y=6(\mathrm{mod}7)$。这里 $s<t$，正式的算法会交换两组参数使大阶在 $x$ 侧；为了演示 $y$ 侧筛选的力学，我们保持原状。逐 $y$ 计算 $z_y=6-3^y$：

• $y=0$：$z_0=6-1=5\notin \{1,2,4\}$，$S(0)=0$，这个 $y$ 被成员检验直接排除，根本不用求离散对数；
• $y=1$：$z_1=6-3=3\notin ⟨2⟩$，$S(1)=0$；
• $y=2$：$z_2=6-2=4\in ⟨2⟩$，且 $4=2^2$，得解 $(x,y)=(2,2)$：验证 $2^2+3^2=4+2=6✓$；
• $y=3$：$z_3=6-6=0$，$S(3)=0$（右端为零不可能有解）；
• $y=4$：$z_4=6-4=2=2^1$，得解 $(1,4)$：$2+3^4=2+4=6✓$；
• $y=5$：$z_5=6-5=1=2^0$，得解 $(0,5)$：$1+3^5=1+5=6✓$。

$6$ 个候选中 $3$ 个被判定器筛掉、$3$ 个命中；对照主项：$N(6,3)\approx \frac{6\times 3}{6}=3$，再次与实际吻合。在这个例子里”先筛后搜”的收益已经可见：Grover 只需要在判定器标记的项上放大振幅。

7. 更强承诺与平均情形（保留条款）

第 5 节的 $q^{3/8}$ 是无条件的最坏情形界。论文还在若干更强的输入承诺下给出更好的界，本节转述这些结果，并明确它们的适用边界。

多解承诺下的参数化界。 短边引理实际上给出的是解数估计而不只是存在性：当 $st$ 较大时，渐近公式应用于整个基本周期矩形（$r=t$）给出

$$N(t,s)=\frac{st}{q-1}+O\left(q^{1/2}\log q\right).$$

当 $st\gg q^{3/2}\log q$ 时，主项压过误差，矩形中有 $M\approx \frac{st}{q-1}\gg 1$ 个解。标记项为 $m$ 时振幅放大的成本是 $\sqrt{|Y|/m}$ 而非 $\sqrt{|Y|}$：沿 $y$ 方向搜索的成本为

$$\sqrt{\frac{t}{M}}=\sqrt{\frac{t(q-1)}{st}}=\sqrt{\frac{q-1}{s}}=\tilde{O}\left(q^{1/2}{s}^{-1/2}\right);$$

由对称性，沿 $x$ 方向搜索（固定 $x$、对 $y$ 求离散对数）成本为 $\tilde{O}(q^{1/2}{t}^{-1/2})$。取两个方向中较好的一侧（$s\ge t$ 时沿 $y$ 搜，代价更小），并用 $s\ge \sqrt{st}$：

$$\tilde{O}\left(q^{1/2}{s}^{-1/2}\right)\le \tilde{O}\left(q^{1/2}(st{)}^{-1/4}\right).$$

这就是论文中 $\tilde{O}(q^{1/2}(st{)}^{-1/4})$ 一类的参数化界：$st$ 越大（基本周期矩形越”密”地布满解），算法越快。注意它与最坏情形界的关系：这个界依赖”矩形中确有许多解”的承诺，当 $st\lesssim q$ 时期望解数不足 $1$，承诺失效，算法退回到第 5 节的分析。

平均情形。 对除 $o(q)$ 个之外的所有目标值 $c$，论文用关于 $c$ 的均方估计（把特征和对 $c$ 取平均，用第二矩控制典型偏离）证明：典型情形的条带宽度可以取得比最坏情形更窄，从而把 $q^{3/8}$ 改进为 $q^{1/3}$。均方估计的直觉是：Weil 型的逐点界必须覆盖最不利的 $c$，而”平均平方”只允许少数 $c$ 取到那么大的偏离，故典型界更紧。此处我们只陈述结论与直觉，均方技巧的完整展开超出本词条范围。

保留条款（务必牢记）。 以上是不同输入承诺下的结论，不能把最好参数区间的复杂度（如 $q^{1/3}$）写成无条件的最坏界——无条件最坏界仍是 $q^{3/8}$。其次，无论哪种承诺，所有这些算法关于输入长度 $\log q$ 都是指数时间。最后，论文明确说明：这些结果没有解决相关半直积群 HSP 所需的多项式时间指数同余子程序——该 HSP 的量子算法状态不因本结果而改变。指数同余能否在 $\mathrm{poly}(\log q)$ 时间求解，仍然开放。

8. 小结与习题

小结。

• 指数同余 $a{f}^x+b{g}^y=c$ 的困难来自两个指数经加法耦合；固定任一个变量，问题退化为一次离散对数，量子上是容易的。
• 阶查找把搜索域限制为 $s\times t$ 的基本周期矩形，其中 $s=\mathrm{ord}(f)$、$t=\mathrm{ord}(g)$，不妨 $s\ge t$。
• 乘法特征的正交关系把”子群成员关系”代数化，给出解数渐近公式 $N(r,s)=\frac{rs}{q-1}+O(q^{1/2}\log q)$；主项是随机模型的期望解数，误差项衡量乘法子群与加法平移之间的偏离。
• 取条带宽度 $r=\lceil C{q}^{3/2}{s}^{-1}\log q\rceil$ 使主项压过误差，得到短边引理：$r\le t$ 时前 $r$ 个 $y$ 中必有解。
• Shor 离散对数包装成相干判定器 $S(y)$，BBHT 振幅放大在 $y$ 上做平方根加速；两种情形分别给出 $\sqrt{r}$ 与 $\sqrt{t}$ 的界，统一为最坏 $\tilde{O}(q^{3/8})$。
• 相对同一骨架下经典判定器（大步小步 $\tilde{O}(\sqrt{s})$、逐项扫描）的 $\tilde{O}(q^{9/8})$，这是关于 $q$ 的三次方指数改进；但 $q^{9/8}\to q^{3/8}$ 不是关于 $\log q$ 的多项式算法，两类算法都是指数时间。

习题。

1. 证明：固定 $y$ 时，方程 $a{f}^x+b{g}^y=c$ 在 $0\le x<s$ 中至多有一个解。（提示：$x\mapsto f^x$ 在阶为 $s$ 的区间上是什么样的映射？）
2. 验证 3.1 节的指标公式：设 $\chi$ 取遍在 $⟨f⟩$ 上平凡的全部 $n=(q-1)/s$ 个乘法特征，证明 $\frac{1}{n}{\sum }_{\chi }\chi (z)$ 当 $z\in ⟨f⟩$ 时等于 $1$，当 $z\in {\mathbb{F}}_q^{\times }\setminus ⟨f⟩$ 时等于 $0$。（提示：把这些特征与商群 ${\mathbb{F}}_q^{\times }/⟨f⟩$ 的特征一一对应，再用正交关系。）
3. 完整写出情形 A（$r\le t$）从 $\tilde{O}(\sqrt{r})$ 到 $\tilde{O}(q^{3/8})$ 的不等式链，并指出每一步用到了哪条前提（$s\ge t$、$r\le t$、$r$ 的定义）。(模仿 5.1 节，但要求自己补全所有代数变形。)
4. 设 $f$ 是 ${\mathbb{F}}_q^{\times }$ 的生成元。说明：除 $z_y=0$（即 $c=b{g}^y$）外，任意固定的 $y$ 都能用一次离散对数求出唯一的 $x$，并解释此时整个算法的成本由什么决定。
5. 解释为什么特征和引理负责算法的”无漏解”（完备性），而 Grover 搜索本身不负责。具体地：如果跳过短边引理、直接在 $\{0,\dots ,\lfloor q^{3/8}\rfloor \}$ 上跑 Grover，算法的输出语义会出什么问题？
6. 在第 7 节的多解承诺 $M\approx \frac{st}{q-1}\gg 1$ 下，自行推导参数化界 $\tilde{O}(q^{1/2}(st{)}^{-1/4})$。（提示：在 $x$、$y$ 两个方向分别做带 $M$ 个标记项的振幅放大搜索，写出两个成本 $\sqrt{t/M}$ 与 $\sqrt{s/M}$，取较好的一侧，并用 $s\ge t$ 消元。）

参考文献

• Zoo 编号 111：Wim van Dam 与 Igor E. Shparlinski, Classical and Quantum Algorithms for Exponential Congruences.
• Peter Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch09-algebra-number-theory/exponential-congruences
• 内容遵循 CC BY-NC-SA 4.0 许可协议