离散对数

出处说明

本文内容摘自外部资源，为方便学员快速学习相关前置数学知识而整理在一起。内容可能较原文有删减，仅保留本课程所需的前置内容，以便学员快速掌握必备知识。

原文链接：https://oi-wiki.org/math/number-theory/discrete-logarithm/

引入

对数的本质是构建一个乘法运算到加法运算的映射。仿照复数中构建对数运算的办法，可以在模 $n$ 意义下存在原根 $g$ 的情况时，建立对数运算。

多值函数

如果对于自变量，有多于一个的函数值与其对应，这样的函数称为 多值函数。

多值函数的函数值为集合，值域为函数值集合的集合。多值函数常常首字母大写，并规定一个对应首字母小写的单值函数称为主值。

在复数中构建的对数运算是多值函数：

Ln z = {\ln z + 2 k π i | k \in Z}

它的主值是：

\ln z = \ln | z | + i \arg z

在模 $p$ 意义下构建离散的对数运算，原理也是类似的。

离散对数

对于模 $n$ 的原根 $g$ ，如果有：

g^{t} \equiv a (\mod n)

则称 $a$ 在模 $n$ 意义下，以 $g$ 为底的对数为 $t$ 。

因为 $g$ 是原根，所以 $g$ 的幂可以取到模 $n$ 意义下的所有元素，每 $φ (n)$ 是一个周期，一个周期后可以回到 $1$ 。

如果使用对数的记号书写，则构成多值函数关系：

{Log}_{g} a = {\log_{g} a + k φ (n) | k \in Z}

它的主值是：

\log_{g} a = t

规定主值 $t$ 取 $0$ 到 $φ (n) - 1$ 。当 $n$ 是素数时，就是 $0$ 到 $n - 2$ 。

与复对数一致，离散对数拥有性质：

{Log}_{g} (a_{1} a_{2}) = {Log}_{g} a_{1} + {Log}_{g} a_{2}

与复对数一致，离散对数的主值不满足该性质。事实上，把离散对数的结果看作对 $φ (n)$ 取模，则非常容易理解这样的关系：对数的本质是构建一个乘法运算到加法运算的映射，离散对数将运算的集合从模 $n$ 缩减到了模 $φ (n)$ ，因为位于乘法位置的自变量只有 $φ (n)$ 个。

因此，为了概念的介绍方便，不再试图去硬性区分多值函数和多值函数的主值这两个概念，而是将记号直接记为：

\log_{g} a \equiv t (\mod φ (n))

这里后面的模数由 $n$ 变为 $φ (n)$ ，原因已经从多值函数的角度进行过讨论。注意这里模 $φ (n)$ 是一个记号，实际仍旧在讨论模 $n$ 范畴的问题。

换底公式

如果模 $n$ 存在不同的两个原根 $g_{1}$ 和 $g_{2}$ ，则离散对数可以换底，换底公式与通常的对数一致。借助模 $φ (n)$ 的记号，可以写为：

\log_{g_{1}} g_{2} \equiv \frac{\log_{g_{2}} a}{\log_{g_{1}} a} (\mod φ (n))

使用原根为底的原因也得到了解释：为了使得模 $φ (n)$ 的除法能够进行。如果不使用原根为底，则模 $φ (n)$ 的除法无法进行。

大步小步算法

BSGS（baby-step giant-step），即大步小步算法。常用于求解离散对数问题。形式化地说，该算法可以在 $O (\sqrt{p})$ 的时间内求解

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

其中 $a ⊥ p$ 。方程的解 $x$ 满足 $0 \leq x < p$ 。（在这里需要注意，只要 $a ⊥ p$ 就行了，不要求 $p$ 是素数）

算法描述

令 $x = A ⌈ \sqrt{p} ⌉ - B$ ，其中 $0 \leq A, B \leq ⌈ \sqrt{p} ⌉$ ，则有 $a^{A ⌈ \sqrt{p} ⌉ - B} \equiv b (\mod p)$ ，稍加变换，则有 $a^{A ⌈ \sqrt{p} ⌉} \equiv b a^{B} (\mod p)$ 。

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

注意到 $A, B$ 均小于 $⌈ \sqrt{p} ⌉$ ，所以时间复杂度为 $Θ (\sqrt{p})$ ，用 map 则多一个 $\log$ 。

" 为什么要求 $a$ 与 $p$ 互质 "

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

进阶篇

求解

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

其中 $p$ 是个质数。

该模型可以通过一系列的转化为成 基础篇 中的模型，你可能需要了解关于阶与原根的知识。

由于式子中的模数 $p$ 是一个质数，那么 $p$ 一定存在一个原根 $g$ 。因此对于模 $p$ 意义下的任意的数 $x (0 \leq x < p)$ 有且仅有一个数 $i (0 \leq i < p - 1)$ 满足 $x = g^{i}$ 。

方法一

我们令 $x = g^{c}$ ， $g$ 是 $p$ 的原根（我们一定可以找到这个 $g$ 和 $c$ ），问题转化为求解 $(g^{c})^{a} \equiv b (\mod p)$ 。稍加变换，得到

(g^{a})^{c} \equiv b (\mod p)

于是就转换成了我们熟知的 BSGS 的基本模型了，可以在 $O (\sqrt{p})$ 解出 $c$ ，这样可以得到原方程的一个特解 $x_{0} \equiv g^{c} (\mod p)$ 。

方法二

我们仍令 $x = g^{c}$ ，并且设 $b = g^{t}$ ，于是我们得到

g^{a c} \equiv g^{t} (\mod p)

方程两边同时取离散对数得到

a c \equiv t (\mod φ (p))

我们可以通过 BSGS 求解 $g^{t} \equiv b (\mod p)$ 得到 $t$ ，于是这就转化成了一个线性同余方程的问题。这样也可以解出 $c$ ，求出 $x$ 的一个特解 $x_{0} \equiv g^{c} (\mod p)$ 。

找到所有解

在知道 $x_{0} \equiv g^{c} (\mod p)$ 的情况下，我们想得到原问题的所有解。首先我们知道 $g^{φ (p)} \equiv 1 (\mod p)$ ，于是可以得到

\forall t \in Z, x^{a} \equiv g^{c \cdot a + t \cdot φ (p)} \equiv b (\mod p)

于是得到所有解为

\forall t \in Z, a ∣ t \cdot φ (p), x \equiv g^{c + \frac{t \cdot φ (p)}{a}} (\mod p)

对于上面这个式子，显然有 $\frac{a}{gcd (a, φ (p))} ∣ t$ 。因此我们设 $t = \frac{a}{gcd (a, φ (p))} \cdot i$ ，得到

\forall i \in Z, x \equiv g^{c + \frac{φ (p)}{gcd (a, φ (p))} \cdot i} (\mod p)

这就是原问题的所有解。

扩展篇

接下来我们求解

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

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

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

具体地，设 $d_{1} = gcd (a, p)$ 。如果 $d_{1} ∤ b$ ，则原方程无解。否则我们把方程同时除以 $d_{1}$ ，得到

\frac{a}{d_{1}} \cdot a^{x - 1} \equiv \frac{b}{d_{1}} (\mod \frac{p}{d_{1}})

如果 $a$ 和 $\frac{p}{d_{1}}$ 仍不互质就再除，设 $d_{2} = gcd (a, \frac{p}{d_{1}})$ 。如果 $d_{2} ∤ \frac{b}{d_{1}}$ ，则方程无解；否则同时除以 $d_{2}$ 得到

\frac{a^{2}}{d_{1} d_{2}} \cdot a^{x - 2} \equiv \frac{b}{d_{1} d_{2}} (\mod \frac{p}{d_{1} d_{2}})

同理，这样不停的判断下去。直到 $a ⊥ \frac{p}{d_{1} d_{2} \dots d_{k}}$ 。

记 $D = \prod_{i = 1}^{k} d_{i}$ ，于是方程就变成了这样：

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

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

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

习题

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

离散对数 ​

引入 ​

多值函数 ​

离散对数 ​

换底公式 ​

大步小步算法 ​

算法描述 ​

进阶篇 ​

方法一 ​

方法二 ​

找到所有解 ​

扩展篇 ​

习题 ​

离散对数

引入

多值函数

离散对数

换底公式

大步小步算法

算法描述

进阶篇

方法一

方法二

找到所有解

扩展篇

习题