指数同余方程：离散对数子程序与 Grover 搜索的三次方加速¶
Shor 离散对数算法告诉我们：有限域乘法群中的单个离散对数问题——给定 \(f\) 与 \(f^x\)，求 \(x\)——可以在 \(\operatorname{poly}(\log q)\) 时间内解决。但是，一旦两个指数通过加法耦合在一起，问题会重新变难。本课研究有限域 \(\mathbb F_q\) 上的指数同余方程 (exponential congruence)
其中 \(a,b,c,f,g\) 已知，要求的是指数对 \((x,y)\)。本课将完整推导 van Dam 与 Shparlinski 的量子算法：先用乘法特征和证明"解一定出现在一个较窄的矩形条带中"，再把 Shor 离散对数包装成一个可相干调用的判定器，交给 Grover 搜索 与振幅放大去找到解。最终的最坏情形运行时间为 \(\widetilde O(q^{3/8})\)，相对论文中给出的经典 \(\widetilde O(q^{9/8})\) 算法，在 \(q\) 的指数幂上获得三次方改进（\(9/8 \to 3/8\)）；但请注意，它仍然不是输入长度 \(\log q\) 的多项式时间算法。
阅读本课需要：有限域与循环群的基本概念，量子傅里叶变换与相位估计（作为 Shor 算法的内部，不需要重新推导），以及 Grover 搜索与振幅放大的结论。全课约定 \(\widetilde O(\cdot)\) 隐藏 \(\log q\) 的多项式因子，\(\lesssim\)、\(\gtrsim\) 在比较时忽略 \(\operatorname{polylog} q\) 因子。
本课知识点
从离散对数到指数同余——能写出指数同余方程 \(af^x+bg^y=c\) 并指明已知量与待求量，解释固定任一指数后问题退化为一次离散对数（量子上容易）、真正的困难来自两个指数的加法耦合。
基本周期矩形与判定器 \(S(y)\)——能由阶 \(s=\operatorname{ord}(f)\)、\(t=\operatorname{ord}(g)\) 把搜索域限定为 \(s\times t\) 的基本周期矩形，写出判定函数 \(S(y)\) 的定义并证明每个 \(y\) 至多贡献一个解。
乘法特征与子群成员指标——能用乘法特征的正交关系推导子群成员指标函数 \(\mathbf 1_{\langle f\rangle}(z)=\frac{1}{n}\sum_\chi\chi(z)\)，并验证它在子群内取 \(1\)、子群外取 \(0\)。
解数渐近公式——能把 \(N(r,s)\) 按"平凡特征主项 + 非平凡特征误差项"拆分，推导 \(N(r,s)=\frac{rs}{q-1}+O(q^{1/2}\log q)\)，并解释主项的随机模型含义与误差项为何只依赖单个特征和的最大值。
短边引理与完备性——能从"主项压过误差"的条件解出条带宽度 \(r=\lceil Cq^{3/2}s^{-1}\log q\rceil\)，并解释 \(r\le t\) 与 \(r>t\) 两种情形下"无漏解"保证如何分工。
相干判定器与振幅放大——能按"计算—标志—相位翻转—反计算"五步描述预言机 \(S(y)\) 的相干实现，解释标志比特为何恰好实现 \(S(y)\)，并说明为什么必须用未知解数（BBHT）版本的振幅放大。
复杂度分析与三次方改进——能推导两种情形的 \(\widetilde O(q^{3/8})\) 界，与同一骨架下经典的 \(\widetilde O(q^{9/8})\) 对照，比较"搜索平方根加速"与"判定器 \(\sqrt s\to\operatorname{polylog}\)"两个改进因子，并指出该结果仍是 \(\log q\) 的指数时间。
\(\mathbb F_7\) 小例子演算——能在 \(\mathbb F_7\) 上完整执行"阶查找—逐 \(y\) 判定—解数对照"的演算，并解释 \(f\) 为生成元时成员检验退化、成本由 \(\widetilde O(\sqrt t\,)\) 决定的极端情形。
1. 问题背景：为什么两个指数会变难¶
1.1 从离散对数到指数同余¶
先回忆离散对数问题。设 \(\mathbb F_q^\times\) 是 \(q\) 元有限域的乘法群（它是 \(q-1\) 阶循环群，这是有限域的标准事实），\(f\in\mathbb F_q^\times\) 给定。离散对数问题是：给定 \(z\in\langle f\rangle\)，求 \(x\) 使得 \(f^x=z\)。Shor 算法把它化为周期查找，配合量子傅里叶采样在 \(\operatorname{poly}(\log q)\) 时间内求解——这是量子计算最著名的指数级加速之一。
现在看指数同余方程 \(af^x+bg^y=c\)。如果两个未知数中有一个被固定，问题立刻退化：
固定 \(y\)，移项得 \(f^x=a^{-1}(c-bg^y)\)，这是一个以 \(f\) 为底的离散对数；
固定 \(x\)，移项得 \(g^y=b^{-1}(c-af^x)\)，这是一个以 \(g\) 为底的离散对数。
也就是说，"单指数"的版本在量子计算机上是容易的。困难来自两个指数的真正耦合：加法 \(af^x+bg^y\) 把两个循环群的乘法结构混在一起。量子傅里叶采样擅长处理的是"周期函数""阿贝尔群结构"，而映射 \((x,y)\mapsto af^x+bg^y\) 的等值集合 \(\{(x,y):af^x+bg^y=c\}\) 一般不构成群，也不具有可以直接傅里叶采样的周期结构。因此，既有的 HSP 机器无法直接吞下这个问题。
这个问题为什么值得研究？至少有三层动机。第一，它是检验"量子加速边界"的天然试金石：单离散对数有多项式时间量子算法，而稍加耦合之后，最好的量子算法仍然要花费关于 \(q\) 的指数时间——指数幂从经典的 \(9/8\) 降到 \(3/8\)，是一个实质但不彻底的改进，画出了当前技术的边界。第二，指数同余与某些半直积群上的隐子群问题 (hidden subgroup problem, HSP) 密切相关：如果能以 \(\operatorname{poly}(\log q)\) 时间求解此类同余，就能为相应的 HSP 提供新的多项式时间量子算法；van Dam–Shparlinski 的论文明确讨论了这层联系，同时也明确指出他们的结果没有解决那个 HSP 所需的多项式时间子程序——这是本课第 7 节要再次强调的保留条款。第三，指数同余的解数估计本身是解析数论中的经典问题，乘法特征和（Gauss 和、Weil 界一路的技术）在其中扮演核心角色；本课可以看到这套经典工具如何与 Grover 搜索拼接成量子算法。
1.2 经典算法的瓶颈¶
经典计算机如何处理这个问题？朴素的办法是穷举：遍历所有候选的 \(y\)，对每个 \(y\) 计算 \(z=a^{-1}(c-bg^y)\)，然后判断 \(z\) 是否落在子群 \(\langle f\rangle\) 中、若落在其中则求出离散对数 \(x\)。瓶颈在第二步：经典模型下没有多项式时间的离散对数算法。用通用群算法（如 Shanks 的大步小步法）在以 \(f\) 为底、阶为 \(s\) 的群中做一次成员判定兼离散对数，需要 \(\widetilde O(\sqrt{s}\,)\) 次群运算，最坏情形 \(s\approx q\) 时单次检查的代价就是 \(\widetilde O(q^{1/2})\)。这个 \(\sqrt{s}\) 不是偶然的：在只使用群运算黑箱的通用群模型中，离散对数有 \(\Omega(\sqrt{s}\,)\) 的下界，因此大步小步在通用意义下已是最优——除非利用 \(\mathbb F_q^\times\) 的具体表示（如指数演减法），否则经典每次候选检查都甩不掉这个平方根因子。
把"候选数 \(\times\) 单次离散对数代价"与下文将要推导的数论引理结合起来，van Dam–Shparlinski 给出的经典算法最坏时间为 \(\widetilde O(q^{9/8})\)。这个 \(9/8\) 本身就是一个参数平衡的结果：候选集合的宽度随 \(s\) 增大而变窄，而单次判定的 \(\sqrt s\) 随 \(s\) 增大而变贵，最坏情形出现在两者顶住的临界点上。我们先把这个数当作经典基准记住，第 5.3 节会逐项重现它的推导，并看清量子算法的 \(q^{3/8}\) 究竟改进了哪几个因子。
1.3 算法概览¶
量子算法由三个部件拼接而成，每个部件各司其职：
阶查找：用 Shor 算法求出 \(s=\operatorname{ord}(f)\)、\(t=\operatorname{ord}(g)\)，把搜索范围限定为 \(s\times t\) 的基本周期矩形；
特征和引理（纯数论，经典证明）：证明当 \(s\) 不太小时，解必定出现在 \(y\) 轴方向宽度约为 \(q^{3/2}s^{-1}\) 的窄条带内，从而把搜索空间从 \(t\) 压缩到 \(r\ll t\)；
Grover 搜索：把"固定 \(y\)、求离散对数、验证等式"做成相干预言机，在压缩后的候选集上做平方根加速搜索。
三个部件中，只有第 3 步是"搜索加速"，第 1 步是"参数确定"，而第 2 步负责完备性——保证搜索范围之外确实没有遗漏的解。这个分工在第 3 节和第 5 节会反复出现。
2. 搜索空间由元素阶决定¶
记
即 \(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\bmod s\) 与 \(y\bmod t\) 的代表元也给出一个解；反过来，每个解的指数在模 \(s\)、模 \(t\) 意义下唯一。于是我们只需考虑
称这个 \(s\times t\) 的整数矩形为基本周期矩形。搜索空间的大小从"无限"变成 \(st\)，而 \(st\le(q-1)^2\)。
阶 \(s,t\) 本身如何得到？用 Shor 的阶查找子程序（与因数分解中完全相同的部分）：对乘法算子 \(|z\rangle\mapsto|fz\bmod q\rangle\) 做相位估计，以 \(\operatorname{poly}(\log q)\) 的时间求出 \(s\)；同理求出 \(t\)。这一步的代价被 \(\widetilde O(\cdot)\) 吸收，后文不再计入。由于方程关于 \((a,f,x)\) 与 \((b,g,y)\) 对称（交换两组变量的角色，方程形状不变），以下不妨设 \(s\ge t\)。
接下来是关键的一步约化。固定某个 \(y\in\{0,\ldots,t-1\}\)，方程等价于
记右端的值为 \(z_y:=a^{-1}(c-bg^y)\)。分两种情况：
若 \(z_y\) 属于循环子群 \(\langle f\rangle=\{1,f,f^2,\ldots,f^{s-1}\}\)，那么离散对数方程 \(f^x=z_y\) 在 \(\{0,\ldots,s-1\}\) 中有唯一解 \(x\)（因为 \(f\) 的阶恰好是 \(s\)，映射 \(x\mapsto f^x\) 在这个区间上是单射），Shor 离散对数算法可以在 \(\operatorname{poly}(\log q)\) 时间内求出它；
若 \(z_y\notin\langle f\rangle\)（包括 \(z_y=0\) 的情形，因为 \(\langle f\rangle\) 中的元素都是非零的），则这个 \(y\) 不可能对应任何解。
因此我们可以定义一个判定函数
每次调用 \(S(y)\) 的成本关于 \(\log q\) 为多项式：一次模幂 \(g^y\)、一次域上的线性组合、一次 Shor 离散对数、一次验证。第 4.1 节会说明如何把它做成可相干调用的量子预言机，目前先把它当作"多项式代价的黑箱判定器"。
上面的"唯一性"观察还有一个计数层面的推论，后文会反复用到：每个 \(y\) 至多贡献一个解。因此，对任何候选集合 \(Y\subseteq\{0,\ldots,t-1\}\)，矩形 \(\{0,\ldots,s-1\}\times Y\) 中的解数恰好等于 \(Y\) 中标记项的个数 \(\#\{y\in Y:S(y)=1\}\)。换句话说，下一节要估计的"条带中的解数" \(N(r,s)\)，正是 Grover 搜索框架里"标记项个数 \(m\)"的化身——第 7 节讨论多解加速时，这个对应关系会把数论估计与查询复杂度直接焊接起来。
有了 \(S(y)\)，最朴素的量子算法是：直接在 \(y\in\{0,\ldots,t-1\}\) 上做 Grover 搜索，寻找使 \(S(y)=1\) 的 \(y\)。成本为
但这还不够好：\(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-bg^y)\) 是否属于子群 \(\langle f\rangle\)。解析数论处理这类"子群成员关系"的标准工具是乘法特征 (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,\ldots,q-2\)），其中 \(\omega\) 是 \(q-1\) 次单位根。特征满足正交关系：对 \(z\in\mathbb F_q^\times\)，
其中求和取遍全部 \(q-1\) 个乘法特征。（当 \(z=1\) 时每一项都是 \(1\)；当 \(z\neq1\) 时，存在某个特征 \(\chi_1\) 使 \(\chi_1(z)\neq1\)，两边同乘 \(\chi_1(z)\) 后求和集不变，于是和只能为 \(0\)。）我们约定 \(\chi(0)=0\)。
现在把正交关系"升级"为子群成员关系的指标函数。设 \(s=\operatorname{ord}(f)\)，并记
即子群 \(\langle f\rangle\) 在 \(\mathbb F_q^\times\) 中的指数（由于 \(s\mid(q-1)\)，\(n\) 是整数）。商群 \(\mathbb F_q^\times/\langle f\rangle\) 是 \(n\) 阶循环群。在所有乘法特征中，恰有 \(n\) 个在 \(\langle f\rangle\) 上恒取 \(1\)——它们正是商群的全部特征（每个这样的特征只依赖于陪集 \(z\langle f\rangle\)，而 \(n\) 阶循环群恰有 \(n\) 个特征）。把这 \(n\) 个特征取出来，对任意 \(z\in\mathbb F_q^\times\) 定义
这个和式就是子群成员关系的精确指标函数：若 \(z\in\langle f\rangle\)，则每一项 \(\chi(z)=1\)，和为 \(n\)，除以 \(n\) 得 \(1\)；若 \(z\notin\langle f\rangle\)，则 \(z\) 在商群中的像 \(\bar z\neq 1\)，和式等于商群上的正交关系 \(\sum_{\hat\chi}\hat\chi(\bar z)=0\)，除以 \(n\) 得 \(0\)。于是我们得到了一个完全代数的判据：
3.2 解数估计：主项与误差项¶
令 \(N(r,s)\) 表示满足
的解 \((x,y)\) 的个数，其中 \(r\le t\) 是待定的条带宽度。由上节的讨论，固定 \(y\) 时解的个数恰为 \(\mathbf 1_{\langle f\rangle}(z_y)\)（属于子群恰对应唯一一个 \(x\)，否则为零），因此
第二个等号只是把指标函数的定义代入并交换求和次序。现在这个双重和可以按特征分成两部分来估计。
主项：平凡特征 \(\chi_0\)。 \(\chi_0\) 在所有非零元上取 \(1\)，所以内层和为 \(\sum_{y=0}^{r-1}\chi_0(z_y)=r-\#\{y:z_y=0\}\)。注意 \(z_y=0\) 等价于 \(c=bg^y\)，在 \(0\le y<r\le t\) 中至多发生一次（\(g\) 的阶是 \(t\)，\(g^y\) 在一个周期内两两不同）。所以平凡特征的贡献是
其中用了 \(n=(q-1)/s\)，即 \(\frac{1}{n}=\frac{s}{q-1}\)。后面的 \(O(1)\) 会被最终误差项吸收，以下不再单独写出。
误差项：其余 \(n-1\) 个非平凡特征。 对每个非平凡特征 \(\chi\)，内层和
是一个"沿几何序列 \(g^y\) 取值"的不完全乘法特征和。解析数论对这类和有通用上界：完全和的平方根抵消（Weil 界的典型尺度）给出 \(q^{1/2}\) 量级，把截断区间补全为完全和的标准技术再付出一个 \(\log q\) 因子，合起来形如
且该界对所有非平凡 \(\chi\) 一致成立。这里我们只做定性说明：\(q^{1/2}\) 反映的是"随机 ±1 序列求和的平方根涨落"这一普遍现象（Weil 界说明代数族特征和确实达到随机行为的尺度），\(\log q\) 是不完全和相对于完全和的技术性损失。
最后把两部分合并。非平凡特征共有 \(n-1\) 个，每个权重 \(1/n\)，因此它们对 \(N(r,s)\) 的总贡献的绝对值不超过
注意这里的要点：\(1/n\) 这个平均因子使得误差项取决于单个特征和的最大值，而不是 \(n\) 个特征和的总和——所以无论 \(n\) 多大，误差项都保持在 \(q^{1/2}\log q\) 的尺度。合起来我们得到解数渐近公式
公式的直观解读。 主项 \(\frac{rs}{q-1}\) 正是随机模型下的期望解数：把 \(z_y\) 想象成 \(\mathbb F_q^\times\) 中的随机元素，它落在占比 \(\frac{s}{q-1}=\frac{1}{n}\) 的子群 \(\langle f\rangle\) 中的概率是 \(\frac{s}{q-1}\)，\(r\) 次独立尝试的期望命中数就是 \(\frac{rs}{q-1}\)。误差项 \(O(q^{1/2}\log q)\) 则衡量真实序列 \(c-bg^y\) 与随机模型的偏离——它来自乘法子群结构（\(g\) 的幂）与加法平移（减 \(c\)、除以 \(a\)）之间的相互作用，而特征和界告诉我们：这种偏离至多是平方根量级的涨落，不会系统性地把解"排挤出"任何一段区间。
3.3 条带宽度的选取¶
渐近公式立刻给出一个存在性判据：只要主项压过误差项，\(N(r,s)\) 就是正的，条带内必有解。具体地，设误差项 \(O(q^{1/2}\log q)\) 中的隐含常数为 \(C'\)。若我们能保证
那么
条带中至少有一个解（事实上至少有主项一半那么多的解）。把上面的不等式解出 \(r\)：两边乘以 \(\frac{q-1}{s}\)，并用 \(q-1<q\)，只需
取 \(C=2C'\)，定义
于是我们证明了本课的核心数论事实：
Lemma（短边引理）. 设 \(r=\lceil Cq^{3/2}s^{-1}\log q\rceil\)，其中 \(C\) 是充分大的绝对常数。若 \(r\le t\)，则存在 \(y\in\{0,\ldots,r-1\}\) 与 \(x\in\{0,\ldots,s-1\}\) 满足 \(af^x+bg^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\rangle\)，一次调用就要同时算出所有 \(S(y)\)，而不能逐个测量。我们按标准的"计算—标志—相位翻转—反计算"模式实现 \(S(y)\)，分五步：
计算 \(g^y\)：用平方-乘算法实现可逆模幂 \(|y\rangle|0\rangle\mapsto|y\rangle|g^y\rangle\)，需要 \(O(\log t)=O(\log q)\) 次域乘法，总代价 \(\operatorname{poly}(\log q)\)；
计算 \(z_y=a^{-1}(c-bg^y)\)：域上的乘法、减法都是可逆运算，代价 \(\operatorname{poly}(\log q)\)；
相干离散对数：在 \(z_y\) 上运行 Shor 离散对数线路（以 \(f\) 为底），把所有测量推迟。线路输出一个候选对数 \(\hat x\) 及工作区。关键点在于：Shor 算法的输出是可验证的——追加一个可逆比较器，计算标志比特 \(b=[f^{\hat x}=z_y\ \land\ z_y\neq0]\)。若 \(z_y\in\langle f\rangle\)，Shor 算法以高概率给出正确的 \(\hat x\)，验证通过，\(b=1\)；若 \(z_y\notin\langle f\rangle\)，任何 \(\hat x\) 都无法通过验证，\(b=0\)。因此 \(b\) 正是 \(S(y)\)（误差概率见下）；
相位翻转：对标志比特施加受控相位（或先制备 \(|{-}\rangle\) 做相位反冲），实现 \(|y\rangle\mapsto(-1)^{S(y)}|y\rangle\)；
反计算：把第 1–3 步的线路逆向运行，清除工作区，只留下 \(y\) 寄存器和已注入的相位。
两点技术说明。第一，Shor 离散对数是有界误差算法，单次成功概率为常数；把它独立重复 \(O(\log\log q)\) 次并取验证通过的结果，可以把每次预言机调用的错误率压到 \(1/\operatorname{poly}(q)\) 以下，对 Grover 迭代的总影响可以忽略，代价只是 \(\operatorname{polylog} q\) 因子，被 \(\widetilde O(\cdot)\) 吸收。第二，搜索区间内标记项的数目 \(m\) 事先未知（这正是问题的难点），因此不能用固定迭代次数的 Grover，而要用振幅放大一章中处理未知解数的版本（BBHT 式的指数增长尝试）：其成本为 \(\widetilde O(\sqrt{|Y|/m}\,)\)，其中 \(Y\) 是搜索区间；最坏情形 \(m\ge1\) 时即 \(\widetilde O(\sqrt{|Y|}\,)\)。
4.2 整体流程¶
综合前面的所有部件，算法如下：
阶查找：用 Shor 算法求 \(s=\operatorname{ord}(f)\)、\(t=\operatorname{ord}(g)\)。若 \(s<t\)，交换两组参数 \((a,f,x)\leftrightarrow(b,g,y)\) 的角色，使 \(s\ge t\)。代价 \(\operatorname{poly}(\log q)\)；
计算条带宽度 \(r=\lceil Cq^{3/2}s^{-1}\log q\rceil\)（纯经典算术）；
分情形搜索：若 \(r\le t\)，令搜索区间 \(Y=\{0,\ldots,r-1\}\)；否则令 \(Y=\{0,\ldots,t-1\}\)。以 \(S(y)\) 为预言机，在 \(Y\) 上运行 BBHT 振幅放大搜索；
输出：若搜索找到 \(y\)，再运行一次 Shor 离散对数求出 \(x\) 并验证 \(af^x+bg^y=c\)，输出 \((x,y)\)；若搜索宣告无标记项，输出"无解"。
正确性由两方面的论证保证：当 \(r\le t\) 时，短边引理保证 \(Y\) 中必有标记项，振幅放大以高概率找到它；当 \(r>t\) 时，\(Y\) 覆盖整个基本周期矩形，搜索穷尽所有候选，找到即解、找不到即无解（至多受子程序有界误差影响，可忽略）。
5. 复杂度分析¶
现在逐项推导两种情形下的运行时间。搜索区间大小为 \(|Y|\)，每次预言机调用代价 \(\operatorname{poly}(\log q)\)，BBHT 搜索调用 \(O(\sqrt{|Y|}\,)\) 次（最坏情形），故总时间为 \(\widetilde O(\sqrt{|Y|}\,)\)，问题归结为估计 \(\sqrt{|Y|}\)。
5.1 情形 A：\(r\le t\)¶
搜索区间是条带，\(|Y|=r\)，成本为
其中第二步把常数 \(C\) 和 \(\sqrt{\log q}\) 吸收进 \(\widetilde O\)。这个表达式里 \(s\) 越小成本越高，所以我们需要 \(s\) 的下界。由两条信息：
\(s\ge t\ge r\)（第一条是约定，第二条是情形 A 的前提）；
\(r\ge Cq^{3/2}s^{-1}\log q\)（\(r\) 的定义，上取整只会让它更大），即 \(sr\gtrsim q^{3/2}\)，
把第一条的 \(r\le s\) 与第二条相乘的方向对齐：
两边开方得 \(s\gtrsim q^{3/4}\)。代回成本表达式——注意 \(s^{-1/2}\) 关于 \(s\) 递减，下界代入后得到上界：
故情形 A 的成本为 \(\widetilde 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\)，成本为 \(\widetilde O(\sqrt t\,)\)。由情形前提 \(t<r\) 以及 \(r\) 的定义（注意 \(r>t\ge1\) 意味着上取整不起主导作用，\(r\) 与 \(Cq^{3/2}s^{-1}\log q\) 同阶）：
再由约定 \(t\le s\)，有 \(t^2\le st\)。于是
polylog 因子照例被吸收。故情形 B 的成本同样是 \(\widetilde O(q^{3/8})\)。
两种分支合起来：算法在 \(\widetilde O(q^{3/8})\) 时间内找到一组解 \((x,y)\)，或确定整个基本周期矩形中无解。 这就是 van Dam–Shparlinski 的最坏情形量子界。
5.3 与经典算法的对比：三次方改进的来源¶
为了看清量子改进究竟来自哪里，我们用同一副骨架重建论文中的经典 \(\widetilde O(q^{9/8})\) 算法。骨架完全相同：阶已知（经典可用因数分解 \(q-1\) 后逐个检验，代价被吸收）、短边引理相同、情形划分相同。唯一的差别在判定器 \(S(y)\) 的代价：经典模型下，用 Shanks 大步小步法做子群成员判定兼离散对数需要 \(\widetilde O(\sqrt s\,)\) 次群运算；而且经典没有振幅放大，搜索是逐项扫描。于是：
情形 A：扫描 \(r\) 个候选，每个代价 \(\sqrt s\)，总成本
其中最后一步同样用了情形 A 导出的 \(s\gtrsim q^{3/4}\)；
情形 B：扫描 \(t\) 个候选，总成本 \(\widetilde O(t\sqrt s\,)\)。利用 \(t\le s\) 给出的 \(t\le(st)^{1/2}\)（即 \(t^{1/2}\le(st)^{1/4}\)）：
对照量子版本，改进来自两个因子的叠加：搜索从逐项扫描 \(O(|Y|)\) 变为振幅放大 \(O(\sqrt{|Y|})\)（平方根），单次判定从经典大步小步的 \(\widetilde O(\sqrt s\,)\) 变为 Shor 算法的 \(\operatorname{poly}(\log q)\)（指数级）。两种情形中成本表达式的"主结构"——情形 A 的 \(|Y|\cdot\sqrt s\) 与情形 B 的 \(t\cdot\sqrt s\)——被替换为 \(\sqrt{|Y|}\cdot\operatorname{polylog}\) 与 \(\sqrt t\cdot\operatorname{polylog}\)，最终在 \(q\) 的指数上体现为
即指数幂的三次方改进。必须强调的是这个改进的限度：输入 \(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\) 是未指定的大常数），但算法的每个部件都可以完整地手工跑一遍。取
即求解 \(3^x+2^y=5\pmod 7\)。
第一步：阶查找。 \(\mathbb F_7^\times=\{1,2,3,4,5,6\}\) 是 \(6\) 阶循环群。逐次计算 \(3\) 的幂：
所以 \(s=\operatorname{ord}(3)=6\)，\(3\) 是生成元，\(\langle 3\rangle=\mathbb F_7^\times\)。再算 \(2\) 的幂：
所以 \(t=\operatorname{ord}(2)=3\)。基本周期矩形是 \(0\le x<6\)、\(0\le y<3\)，共 \(18\) 个候选指数对。
第二步：逐 \(y\) 运行判定器。 计算 \(z_y=c-g^y=5-2^y\bmod 7\)，并判断 \(z_y\in\langle 3\rangle\)、求离散对数 \(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)\}\)。逐一验证：
第三步：对照解数公式。 条带取满整个周期 \(r=t=3\) 时，公式的主项给出
与实际解数 \(3\) 完全吻合（当然在 \(q=7\) 时误差项的渐近界无意义，这只是巧合级别的吻合，用来说明主项的含义）。
第四步：量子算法在这个例子上会做什么。 真实的算法不会顺序尝试 \(y\)：它先由相位估计求出 \(s=6\)、\(t=3\)；然后注意到 \(s=q-1\)（\(f\) 是生成元），于是任意非零的 \(z_y\) 必在 \(\langle f\rangle\) 中，判定器几乎总是回答 \(1\)；Grover/BBHT 在 \(|Y|=3\) 个候选、\(m=3\) 个标记项上以约 \(\sqrt{3/3}=1\) 次查询级别的代价直接选中某个解，最后再跑一次离散对数输出 \((x,y)\)。整个流程中"计算 \(g^y\)、检查子群成员关系、求离散对数、验证等式"都被做成相干子程序，由振幅放大选择成功分支——小例子里看不出加速，但线路结构与 \(q\) 巨大时完全相同。
这个例子还演示了判定器退化的极端情形：当 \(f\) 是生成元（\(s=q-1\)）时，子群成员检验形同虚设，问题实质上变成"\(t\) 个候选中做搜索"，量子成本 \(\widetilde O(\sqrt t\,)\) 直接就是好的。真正困难的情形是 \(s,t\) 都远小于 \(q\)——那也正是特征和引理发挥压缩作用的舞台。
为了看清成员检验真正起筛选作用的样子，把同一个域上的底换成非生成元：取 \(f=2\)（阶 \(s=3\)，\(\langle 2\rangle=\{1,2,4\}\)）、\(g=3\)（阶 \(t=6\)），解 \(2^x+3^y=6\pmod 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\langle 2\rangle\)，\(S(1)=0\)；
\(y=2\)：\(z_2=6-2=4\in\langle 2\rangle\)，且 \(4=2^2\)，得解 \((x,y)=(2,2)\)：验证 \(2^2+3^2=4+2=6\ \checkmark\)；
\(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\ \checkmark\)；
\(y=5\)：\(z_5=6-5=1=2^0\)，得解 \((0,5)\)：\(1+3^5=1+5=6\ \checkmark\)。
\(6\) 个候选中 \(3\) 个被判定器筛掉、\(3\) 个命中；对照主项：\(N(6,3)\approx\frac{6\times3}{6}=3\)，再次与实际吻合。在这个例子里"先筛后搜"的收益已经可见：Grover 只需要在判定器标记的项上放大振幅。
7. 更强承诺与平均情形（保留条款）¶
第 5 节的 \(q^{3/8}\) 是无条件的最坏情形界。论文还在若干更强的输入承诺下给出更好的界，本节转述这些结果，并明确它们的适用边界。
多解承诺下的参数化界。 短边引理实际上给出的是解数估计而不只是存在性：当 \(st\) 较大时，渐近公式应用于整个基本周期矩形（\(r=t\)）给出
当 \(st\gg q^{3/2}\log q\) 时，主项压过误差，矩形中有 \(M\approx\frac{st}{q-1}\gg1\) 个解。标记项为 \(m\) 时振幅放大的成本是 \(\sqrt{|Y|/m}\) 而非 \(\sqrt{|Y|}\)：沿 \(y\) 方向搜索的成本为
由对称性，沿 \(x\) 方向搜索（固定 \(x\)、对 \(y\) 求离散对数）成本为 \(\widetilde O(q^{1/2}t^{-1/2})\)。取两个方向中较好的一侧（\(s\ge t\) 时沿 \(y\) 搜，代价更小），并用 \(s\ge\sqrt{st}\)：
这就是论文中 \(\widetilde O\bigl(q^{1/2}(st)^{-1/4}\bigr)\) 一类的参数化界：\(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 的量子算法状态不因本结果而改变。指数同余能否在 \(\operatorname{poly}(\log q)\) 时间求解，仍然开放。
8. 小结¶
小结。
指数同余 \(af^x+bg^y=c\) 的困难来自两个指数经加法耦合；固定任一个变量，问题退化为一次离散对数，量子上是容易的。
阶查找把搜索域限制为 \(s\times t\) 的基本周期矩形，其中 \(s=\operatorname{ord}(f)\)、\(t=\operatorname{ord}(g)\)，不妨 \(s\ge t\)。
乘法特征的正交关系把"子群成员关系"代数化，给出解数渐近公式 \(N(r,s)=\frac{rs}{q-1}+O(q^{1/2}\log q)\)；主项是随机模型的期望解数，误差项衡量乘法子群与加法平移之间的偏离。
取条带宽度 \(r=\lceil Cq^{3/2}s^{-1}\log q\rceil\) 使主项压过误差，得到短边引理：\(r\le t\) 时前 \(r\) 个 \(y\) 中必有解。
Shor 离散对数包装成相干判定器 \(S(y)\)，BBHT 振幅放大在 \(y\) 上做平方根加速；两种情形分别给出 \(\sqrt r\) 与 \(\sqrt t\) 的界，统一为最坏 \(\widetilde O(q^{3/8})\)。
相对同一骨架下经典判定器（大步小步 \(\widetilde O(\sqrt s\,)\)、逐项扫描）的 \(\widetilde O(q^{9/8})\)，这是关于 \(q\) 的三次方指数改进；但 \(q^{9/8}\to q^{3/8}\) 不是关于 \(\log q\) 的多项式算法，两类算法都是指数时间。
练习题¶
练习 1【从离散对数到指数同余】（→ 1.1 节）
写出指数同余方程 \(af^x+bg^y=c\)：指明哪些量已知、要求的是什么，并说明为什么固定 \(y\)（或固定 \(x\)）后问题分别退化为以 \(f\)（或 \(g\)）为底的一次离散对数。
解释为什么既有的 HSP/量子傅里叶采样机器无法直接求解这个方程：映射 \((x,y)\mapsto af^x+bg^y\) 的等值集合缺少什么结构？
提示：对照"周期函数/阿贝尔群同态的核"，检查等值集合 \(\{(x,y):af^x+bg^y=c\}\) 是否构成群或具有周期性。
练习 2【基本周期矩形与判定器 \(S(y)\)】（→ 第 2 节）
设 \(s=\operatorname{ord}(f)\)、\(t=\operatorname{ord}(g)\)：写出基本周期矩形的定义，解释为什么每个解在模 \(s\)、模 \(t\) 意义下唯一；再写出判定函数 \(S(y)\) 的取值规则，并说明 \(z_y\notin\langle f\rangle\)（含 \(z_y=0\)）的 \(y\) 为什么无解。
证明：固定 \(y\) 时，方程 \(af^x+bg^y=c\) 在 \(0\le x<s\) 中至多有一个解。
提示：\(x\mapsto f^x\) 在阶为 \(s\) 的区间上是什么样的映射？
练习 3【乘法特征与子群成员指标】（→ 3.1 节）
对 \(\mathbb F_7\) 写出二次乘法特征（Legendre 符号）在 \(1,2,\ldots,6\) 上的取值，并验证 \(\sum_{z\in\mathbb F_7^\times}\chi(z)=0\)；再写出一般正交关系 \(\frac{1}{q-1}\sum_\chi\chi(z)\) 在 \(z=1\) 与 \(z\ne1\) 时的取值。
验证 3.1 节的指标公式：设 \(\chi\) 取遍在 \(\langle f\rangle\) 上平凡的全部 \(n=(q-1)/s\) 个乘法特征，证明 \(\frac{1}{n}\sum_\chi\chi(z)\) 当 \(z\in\langle f\rangle\) 时等于 \(1\)，当 \(z\in\mathbb F_q^\times\setminus\langle f\rangle\) 时等于 \(0\)。
提示：把这些特征与商群 \(\mathbb F_q^\times/\langle f\rangle\) 的特征一一对应，再用正交关系。
练习 4【解数渐近公式】（→ 3.2 节）
写出解数渐近公式并用随机模型解释主项：单次尝试命中的概率是多少？\(r\) 次尝试的期望命中数是多少？对照第 6 节：\(q=7\)、\(s=6\)、\(r=t=3\) 时主项预言多少个解？
解释为什么误差项只取决于单个特征和的最大值 \(\max_{\chi\ne\chi_0}|T_\chi|=O(q^{1/2}\log q)\)、而不是 \(n\) 个非平凡特征的总和：指出推导中的哪个因子保证了这一点，并说明平凡特征的内层和为什么会差一个 \(O(1)\)。
提示：非平凡特征各自的权重是 \(\frac1n\)；\(z_y=0\) 等价于 \(c=bg^y\)，在一个周期内至多发生一次。
练习 5【短边引理与完备性】（→ 3.3 节）
由下界 \(N(r,s)\ge\frac{rs}{q-1}-C'q^{1/2}\log q\) 出发，推导"主项压过误差"的条件并解出条带宽度 \(r=\lceil Cq^{3/2}s^{-1}\log q\rceil\)，写明常数关系 \(C=2C'\) 与每一步用到的放缩。
解释为什么特征和引理负责算法的"无漏解"（完备性），而 Grover 搜索本身不负责。具体地：如果跳过短边引理、直接在 \(\{0,\ldots,\lfloor q^{3/8}\rfloor\}\) 上跑 Grover，算法的输出语义会出什么问题？
提示：分别考虑 \(r\le t\) 与 \(r>t\) 两种情形下"搜索失败"各能推出什么结论；跳过引理后"没找到"还能不能断言无解？
练习 6【相干判定器与振幅放大】（→ 4.1 节）
按顺序列出预言机实现 \(S(y)\) 的五个步骤，并说明"反计算"一步的作用：若省略它，寄存器里会残留什么、对 Grover 迭代中的干涉有什么影响？
解释标志比特 \(b=[f^{\hat x}=z_y\ \land\ z_y\neq0]\) 为什么恰好实现 \(S(y)\)：分别讨论 \(z_y\in\langle f\rangle\) 与 \(z_y\notin\langle f\rangle\) 两种情形；再解释为什么不能用固定迭代次数的 Grover，而要用 BBHT 式的未知解数版本。
提示：Shor 离散对数的输出是可验证的；搜索区间内标记项个数 \(m\) 事先未知。
练习 7【复杂度分析与三次方改进】（→ 5.3 节）
在最坏点 \(s\approx r\approx q^{3/4}\) 处，把经典情形 A 的成本分解为"扫描 \(r\) 个候选 \(\times\) 单次判定 \(\sqrt s\,\)"两个因子的幂，指出振幅放大与 Shor 判定器分别把这两个因子改成了什么，再用 \(\frac{9/8}{3/8}=3\) 核验"三次方改进"的说法。
完整写出情形 A（\(r\le t\)）从 \(\widetilde O(\sqrt r\,)\) 到 \(\widetilde O(q^{3/8})\) 的不等式链，并指出每一步用到了哪条前提（\(s\ge t\)、\(r\le t\)、\(r\) 的定义）；模仿 5.1 节，但要求自己补全所有代数变形。
在第 7 节的多解承诺 \(M\approx\frac{st}{q-1}\gg1\) 下，自行推导参数化界 \(\widetilde O\bigl(q^{1/2}(st)^{-1/4}\bigr)\)。
提示：情形 A 用 \(r\le s\) 与 \(sr\gtrsim q^{3/2}\) 相乘；多解承诺下在 \(x\)、\(y\) 两个方向分别写出成本 \(\sqrt{t/M}\) 与 \(\sqrt{s/M}\)，取较好的一侧并用 \(s\ge t\) 消元。
练习 8【\(\mathbb F_7\) 小例子演算】（→ 第 6 节）
在 \(\mathbb F_7\) 上解 \(4^x+3^y=3\pmod 7\)：先求 \(\operatorname{ord}(4)\)、\(\operatorname{ord}(3)\) 与基本周期矩形，再逐 \(y\) 计算 \(z_y=3-3^y\) 并判断是否属于 \(\langle 4\rangle\)，写出全部解并逐一验证。
设 \(f\) 是 \(\mathbb F_q^\times\) 的生成元。说明：除 \(z_y=0\)（即 \(c=bg^y\)）外，任意固定的 \(y\) 都能用一次离散对数求出唯一的 \(x\)，并解释此时整个算法的成本由什么决定。
提示：对照第 6 节第一个例子里 \(s=q-1\) 的讨论——成员检验形同虚设时，问题变成"在 \(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.