离散对数

定义

前置知识：阶与原根。

离散对数的定义方式和对数类似。取有原根的正整数模数 $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))$

   进而 $(\mathrm{\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$，所以时间复杂度为 $\mathrm{\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$.

进阶篇

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

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

该问题可以转化为 BSGS 求解的问题。

由于式子中的模数 $p$ 是一个质数，那么 $p$ 一定存在一个原根 $g$. 因此对于模 $p$ 意义下的任意的数 $x~(1\le x

---

本页面最近更新：2024/10/9 22:38:42，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, StudyingFather, sshwy, Steaunk, Great-designer, H-J-Granger, Enter-tainer, MegaOwIer, countercurrent-time, Henry-ZHR, Konano, ksyx, NachtgeistW, ouuan, stevebraveman, Tiphereth-A, Xeonacid, Alpha1022, AngelKitty, CCXXXI, Chrogeek, ChungZH, cjsoft, diauweb, Early0v0, ezoixx130, FFjet, GavinZhengOI, GekkaSaori, Gesrua, hly1204, hsfzLZH1, iamtwz, isdanni, Kelatte, kxccc, Lampese, LovelyBuggies, lychees, Makkiy, Marcythm, mgt, minghu6, P-Y-Y, Peanut-Tang, PotassiumWings, purple-vine, SamZhangQingChuan, SukkaW, Suyun514, weiyong1024, xyf007, YOYO-UIAT
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用