离散对数

定义

前置知识：阶与原根。

离散对数的定义方式和对数类似。取有原根的正整数模数 $m$，设其一个原根为 $g$. 对满足 $(a,m)=1$ 的整数 $a$，我们知道必存在唯一的整数 $0\le k<\phi (m)$ 使得

$$g^k\equiv a(\mathrm{mod}m)$$

我们称这个 $k$ 为以 $g$ 为底，模 $m$ 的离散对数，记作 $k={\mathrm{ind}}_{g}a$，在不引起混淆的情况下可记作 $\mathrm{ind}a$.

显然 ${\mathrm{ind}}_{g}1=0$，${\mathrm{ind}}_{g}g=1$.

性质

离散对数的性质也和对数有诸多类似之处。

性质

设 $g$ 是模 $m$ 的原根，$(a,m)=(b,m)=1$，则：

1. ${\mathrm{ind}}_g(ab)\equiv {\mathrm{ind}}_{g}a+{\mathrm{ind}}_{g}b(\mathrm{mod}\phi (m))$

   进而 $(\forall n\in \mathbf{N}),{\mathrm{ind}}_g{a}^n\equiv n{\mathrm{ind}}_{g}a(\mathrm{mod}\phi (m))$

2. 若 $g_1$ 也是模 $m$ 的原根，则 ${\mathrm{ind}}_{g}a\equiv {\mathrm{ind}}_{g_1}a\cdot {\mathrm{ind}}_g{g}_1(\mathrm{mod}\phi (m))$

3. $a\equiv b(\mathrm{mod}m)⟺{\mathrm{ind}}_{g}a={\mathrm{ind}}_{g}b$

证明

1. $g^{{\mathrm{ind}}_g(ab)}\equiv ab\equiv g^{{\mathrm{ind}}_{g}a}{g}^{{\mathrm{ind}}_{g}b}\equiv g^{{\mathrm{ind}}_{g}a+{\mathrm{ind}}_{g}b}(\mathrm{mod}m)$

2. 令 $x={\mathrm{ind}}_{g_1}a$，则 $a\equiv g_1^x(\mathrm{mod}m)$. 又令 $y={\mathrm{ind}}_g{g}_1$，则 $g_1\equiv g^y(\mathrm{mod}m)$.

   故 $a\equiv g^{xy}(\mathrm{mod}m)$，即 ${\mathrm{ind}}_{g}a\equiv xy\equiv {\mathrm{ind}}_{g_1}a\cdot {\mathrm{ind}}_g{g}_1(\mathrm{mod}\phi (m))$

3. 注意到

   $$\begin{array}{rl}{\mathrm{ind}}_{g}a={\mathrm{ind}}_{g}b& ⟺{\mathrm{ind}}_{g}a\equiv {\mathrm{ind}}_{g}b(\mathrm{mod}\phi (m))\\ & ⟺g^{{\mathrm{ind}}_{g}a}\equiv g^{{\mathrm{ind}}_{g}b}(\mathrm{mod}m)\\ & ⟺a\equiv b(\mathrm{mod}m)\end{array}$$

大步小步算法

目前离散对数问题仍不存在多项式时间经典算法（离散对数问题的输入规模是输入数据的位数）。在密码学中，基于这一点人们设计了许多非对称加密算法，如 Ed25519。

在算法竞赛中，BSGS（baby-step giant-step，大步小步算法）常用于求解离散对数问题。形式化地说，对 $a,b,m\in {\mathbf{Z}}^{+}$，该算法可以在 $O(\sqrt{m})$ 的时间内求解

$$a^x\equiv b(\mathrm{mod}m)$$

其中 $a\perp m$。方程的解 $x$ 满足 $0\le x<m$.（注意 $m$ 不一定是素数）

算法描述

令 $x=A\lceil \sqrt{m}\rceil -B$，其中 $0\le A,B\le \lceil \sqrt{m}\rceil$，则有 $a^{A\lceil \sqrt{m}\rceil -B}\equiv b(\mathrm{mod}m)$，稍加变换，则有 $a^{A\lceil \sqrt{m}\rceil }\equiv b{a}^B(\mathrm{mod}m)$.

我们已知的是 $a,b$，所以我们可以先算出等式右边的 $b{a}^B$ 的所有取值，枚举 $B$，用 hash/map 存下来，然后逐一计算 $a^{A\lceil \sqrt{m}\rceil }$，枚举 $A$，寻找是否有与之相等的 $b{a}^B$，从而我们可以得到所有的 $x$，$x=A\lceil \sqrt{m}\rceil -B$.

注意到 $A,B$ 均小于 $\lceil \sqrt{m}\rceil$，所以时间复杂度为 $\Theta \left(\sqrt{m}\right)$，用 map 则多一个 $\log$.

为什么要求 $a$ 与 $m$ 互质

注意到我们求出的是 $A,B$，我们需要保证从 $a^{A\lceil \sqrt{m}\rceil }\equiv b{a}^B(\mathrm{mod}m)$ 可以推回 $a^{A\lceil \sqrt{m}\rceil -B}\equiv b(\mathrm{mod}m)$，后式是前式左右两边除以 $a^B$ 得到，所以必须有 $a^B\perp m$ 即 $a\perp m$.

扩展 BSGS 算法

对 $a,b,m\in {\mathbf{Z}}^{+}$，求解

$$a^x\equiv b(\mathrm{mod}m)$$

其中 $a,m$ 不一定互质。

当 $(a,m)=1$ 时，在模 $m$ 意义下 $a$ 存在逆元，因此可以使用 BSGS 算法求解。于是我们想办法让他们变得互质。

具体地，设 $d_1=(a,m)$. 如果 $d_1\nmid b$，则原方程无解。否则我们把方程同时除以 $d_1$，得到

$$\frac{a}{d_1}\cdot a^{x-1}\equiv \frac{b}{d_1}(\mathrm{mod}\frac{m}{d_1})$$

如果 $a$ 和 $\frac{m}{d_1}$ 仍不互质就再除，设 $d_2=\left(a,\frac{m}{d_1}\right)$. 如果 $d_2\nmid \frac{b}{d_1}$，则方程无解；否则同时除以 $d_2$ 得到

$$\frac{a^2}{d_1{d}_2}\cdot a^{x-2}\equiv \frac{b}{d_1{d}_2}(\mathrm{mod}\frac{m}{d_1{d}_2})$$

同理，这样不停的判断下去，直到 $a\perp \frac{m}{d_1{d}_2\cdots d_k}$.

记 $D={\prod }_{i=1}^k{d}_i$，于是方程就变成了这样：

$$\frac{a^k}{D}\cdot a^{x-k}\equiv \frac{b}{D}(\mathrm{mod}\frac{m}{D})$$

由于 $a\perp \frac{m}{D}$，于是推出 $\frac{a^k}{D}\perp \frac{m}{D}$. 这样 $\frac{a^k}{D}$ 就有逆元了，于是把它丢到方程右边，这就是一个普通的 BSGS 问题了，于是求解 $x-k$ 后再加上 $k$ 就是原方程的解啦。

注意，不排除解小于等于 $k$ 的情况，所以在消因子之前做一下 $\Theta (k)$ 枚举，直接验证 $a^i\equiv b(\mathrm{mod}m)$，这样就能避免这种情况。

习题

• SPOJ MOD 模板
• SDOI2013 随机数生成器
• SGU261 Discrete Roots 模板
• SDOI2011 计算器 模板
• Luogu4195【模板】exBSGS/Spoj3105 Mod 模板
• Codeforces - Lunar New Year and a Recursive Sequence
• LOJ6542 离散对数 index calculus 方法，非模板

本页面部分内容以及代码译自博文 Дискретное извлечение корня 与其英文翻译版 Discrete Root。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

参考资料

1. Discrete logarithm - Wikipedia
2. 潘承洞，潘承彪。初等数论。
3. 冯克勤。初等数论及其应用。