离散对数

定义

前置知识：阶与原根。

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

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

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

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

性质

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

性质

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

${ind}_{g} (a b) \equiv {ind}_{g} a + {ind}_{g} b (\mod φ (m))$

进而 $(\forall n \in N), {ind}_{g} a^{n} \equiv n {ind}_{g} a (\mod φ (m))$
若 $g_{1}$ 也是模 $m$ 的原根，则 ${ind}_{g} a \equiv {ind}_{g_{1}} a \cdot {ind}_{g} g_{1} (\mod φ (m))$
$a \equiv b (\mod m) ⟺ {ind}_{g} a = {ind}_{g} b$

证明

$g^{{ind}_{g} (a b)} \equiv a b \equiv g^{{ind}_{g} a} g^{{ind}_{g} b} \equiv g^{{ind}_{g} a + {ind}_{g} b} (\mod m)$
令 $x = {ind}_{g_{1}} a$ ，则 $a \equiv g_{1}^{x} (\mod m)$ . 又令 $y = {ind}_{g} g_{1}$ ，则 $g_{1} \equiv g^{y} (\mod m)$ .

故 $a \equiv g^{x y} (\mod m)$ ，即 ${ind}_{g} a \equiv x y \equiv {ind}_{g_{1}} a \cdot {ind}_{g} g_{1} (\mod φ (m))$
注意到
$\begin{aligned} {ind}_{g} a = {ind}_{g} b & ⟺ {ind}_{g} a \equiv {ind}_{g} b (\mod φ (m)) \\ ⟺ g^{{ind}_{g} a} \equiv g^{{ind}_{g} b} (\mod m) \\ ⟺ a \equiv b (\mod m) \end{aligned}$

大步小步算法

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

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

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

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

算法描述

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

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

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

为什么要求

a

与

m

互质

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

进阶篇

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

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

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

由于式子中的模数 $p$ 是一个质数，那么 $p$ 一定存在一个原根 $g$ . 因此对于模 $p$ 意义下的任意的数 $x (1 \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}{(a, φ (p))} ∣ t$ . 因此我们设 $t = \frac{a}{(a, φ (p))} \cdot i$ ，得到

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

这就是原问题的所有解。

实现

下面的代码实现的找原根、离散对数解和原问题所有解的过程。

参考代码

int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }

int powmod(int a, int b, int p) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % p;
    a = a * a % p, b >>= 1;
  }
  return res;
}

// Finds the primitive root modulo p
int generator(int p) {
  vector<int> fact;
  int phi = p - 1, n = phi;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      fact.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) fact.push_back(n);
  for (int res = 2; res <= p; ++res) {
    bool ok = true;
    for (int factor : fact) {
      if (powmod(res, phi / factor, p) == 1) {
        ok = false;
        break;
      }
    }
    if (ok) return res;
  }
  return -1;
}

// This program finds all numbers x such that x^k=a (mod n)
int main() {
  int n, k, a;
  scanf("%d %d %d", &n, &k, &a);
  if (a == 0) return puts("1\n0"), 0;
  int g = generator(n);
  // Baby-step giant-step discrete logarithm algorithm
  int sq = (int)sqrt(n + .0) + 1;
  vector<pair<int, int>> dec(sq);
  for (int i = 1; i <= sq; ++i)
    dec[i - 1] = {powmod(g, i * sq * k % (n - 1), n), i};
  sort(dec.begin(), dec.end());
  int any_ans = -1;
  for (int i = 0; i < sq; ++i) {
    int my = powmod(g, i * k % (n - 1), n) * a % n;
    auto it = lower_bound(dec.begin(), dec.end(), make_pair(my, 0));
    if (it != dec.end() && it->first == my) {
      any_ans = it->second * sq - i;
      break;
    }
  }
  if (any_ans == -1) return puts("0"), 0;
  // Print all possible answers
  int delta = (n - 1) / gcd(k, n - 1);
  vector<int> ans;
  for (int cur = any_ans % delta; cur < n - 1; cur += delta)
    ans.push_back(powmod(g, cur, n));
  sort(ans.begin(), ans.end());
  printf("%zu\n", ans.size());
  for (int answer : ans) printf("%d ", answer);
}

扩展篇（扩展 BSGS）

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

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

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

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

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

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

如果 $a$ 和 $\frac{m}{d_{1}}$ 仍不互质就再除，设 $d_{2} = (a, \frac{m}{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{m}{d_{1} d_{2}})

同理，这样不停的判断下去，直到 $a ⊥ \frac{m}{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{m}{D})

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

注意，不排除解小于等于 $k$ 的情况，所以在消因子之前做一下 $Θ (k)$ 枚举，直接验证 $a^{i} \equiv b (\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。

参考资料

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

本页面最近更新：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 协议之条款下提供，附加条款亦可能应用