指数同余方程：离散对数子程序与 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\) 没有解。因此可以定义可逆量子子程序

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

每次 \(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 本身不负责。

参考文献