跳转至

離散對數

定義

前置知識：階與原根。

離散對數的定義方式和對數類似。取有原根的正整數模數 \(m\)，設其一個原根為 \(g\). 對滿足 \((a,m)=1\) 的整數 \(a\)，我們知道必存在唯一的整數 \(0\leq k<\varphi(m)\) 使得

\[ g^k\equiv a\pmod m \]

我們稱這個 \(k\) 為以 \(g\) 為底，模 \(m\) 的離散對數，記作 \(k=\operatorname{ind}_g a\)，在不引起混淆的情況下可記作 \(\operatorname{ind} a\).

顯然 \(\operatorname{ind}_g 1=0\)，\(\operatorname{ind}_g g=1\).

性質

離散對數的性質也和對數有諸多類似之處。

性質

設 \(g\) 是模 \(m\) 的原根，\((a,m)=(b,m)=1\)，則：

  1. \(\operatorname{ind}_g(ab)\equiv\operatorname{ind}_g a+\operatorname{ind}_g b\pmod{\varphi(m)}\)

    進而 \((\forall n\in\mathbf{N}),~~\operatorname{ind}_g a^n\equiv n\operatorname{ind}_g a\pmod{\varphi(m)}\)

  2. 若 \(g_1\) 也是模 \(m\) 的原根，則 \(\operatorname{ind}_g a\equiv\operatorname{ind}_{g_1}a \cdot \operatorname{ind}_g g_1\pmod{\varphi(m)}\)

  3. \(a\equiv b\pmod m\iff \operatorname{ind}_g a=\operatorname{ind}_g b\)
證明
  1. \(g^{\operatorname{ind}_g(ab)}\equiv ab\equiv g^{\operatorname{ind}_g a}g^{\operatorname{ind}_g b}\equiv g^{\operatorname{ind}_g a+\operatorname{ind}_g b}\pmod m\)

  2. 令 \(x=\operatorname{ind}_{g_1}a\)，則 \(a\equiv g_1^x\pmod m\). 又令 \(y=\operatorname{ind}_g g_1\)，則 \(g_1\equiv g^y\pmod m\).

    故 \(a\equiv g^{xy}\pmod m\)，即 \(\operatorname{ind}_g a\equiv xy\equiv\operatorname{ind}_{g_1}a \cdot \operatorname{ind}_g g_1\pmod{\varphi(m)}\)

  3. 注意到

    \[ \begin{aligned} \operatorname{ind}_g a=\operatorname{ind}_g b&\iff \operatorname{ind}_g a\equiv\operatorname{ind}_g b\pmod{\varphi(m)}\\ &\iff g^{\operatorname{ind}_g a}\equiv g^{\operatorname{ind}_g b}\pmod m\\ &\iff a\equiv b\pmod m \end{aligned} \]

大步小步算法

目前離散對數問題仍不存在多項式時間經典算法（離散對數問題的輸入規模是輸入數據的位數）。在密碼學中，基於這一點人們設計了許多非對稱加密算法，如 Ed25519。

在算法競賽中，BSGS（baby-step giant-step，大步小步算法）常用於求解離散對數問題。形式化地説，對 \(a,b,m\in\mathbf{Z}^+\)，該算法可以在 \(O(\sqrt{m})\) 的時間內求解

\[ a^x \equiv b \pmod m \]

其中 \(a\perp m\)。方程的解 \(x\) 滿足 \(0 \le x < m\).（注意 \(m\) 不一定是素數）

算法描述

令 \(x = A \left \lceil \sqrt m \right \rceil - B\)，其中 \(0\le A,B \le \left \lceil \sqrt m \right \rceil\)，則有 \(a^{A\left \lceil \sqrt m \right \rceil -B} \equiv b \pmod m\)，稍加變換，則有 \(a^{A\left \lceil \sqrt m \right \rceil} \equiv ba^B \pmod m\).

我們已知的是 \(a,b\)，所以我們可以先算出等式右邊的 \(ba^B\) 的所有取值，枚舉 \(B\)，用 hash/map 存下來，然後逐一計算 \(a^{A\left \lceil \sqrt m \right \rceil}\)，枚舉 \(A\)，尋找是否有與之相等的 \(ba^B\)，從而我們可以得到所有的 \(x\)，\(x=A \left \lceil \sqrt m \right \rceil - B\).

注意到 \(A,B\) 均小於 \(\left \lceil \sqrt m \right \rceil\)，所以時間複雜度為 \(\Theta\left (\sqrt m\right )\)，用 map 則多一個 \(\log\).

為什麼要求 \(a\) 與 \(m\) 互質

注意到我們求出的是 \(A,B\)，我們需要保證從 \(a^{A\left \lceil \sqrt m \right \rceil} \equiv ba^B \pmod m\) 可以推回 \(a^{A\left \lceil \sqrt m \right \rceil -B} \equiv b \pmod m\)，後式是前式左右兩邊除以 \(a^B\) 得到，所以必須有 \(a^B \perp m\) 即 \(a\perp m\).

進階篇

對 \(a,b\in\mathbf{Z}^+\)，\(p\in\mathbf{P}\)，求解

\[ x^a \equiv b \pmod p \]

該問題可以轉化為 BSGS 求解的問題。

由於式子中的模數 \(p\) 是一個質數，那麼 \(p\) 一定存在一個原根 \(g\). 因此對於模 \(p\) 意義下的任意的數 \(x~(1\le x<p)\) 有且僅有一個數 \(i~(0\le i<p-1)\) 滿足 \(x = g^i\).

方法一

我們令 \(x=g^c\)，\(g\) 是 \(p\) 的原根（我們一定可以找到這個 \(g\) 和 \(c\)），問題轉化為求解 \((g^c)^a \equiv b \pmod p\). 稍加變換，得到

\[ (g^a)^c \equiv b \pmod p \]

於是就轉換成了 BSGS 的基本模型了，可以在 \(O(\sqrt p)\) 解出 \(c\)，這樣可以得到原方程的一個特解 \(x_0\equiv g^c\pmod p\).

方法二

我們仍令 \(x=g^c\)，並且設 \(b=g^t\)，於是我們得到

\[ g^{ac}\equiv g^t\pmod p \]

方程兩邊同時取離散對數得到

\[ ac\equiv t\pmod{\varphi(p)} \]

我們可以通過 BSGS 求解 \(g^t\equiv b\pmod p\) 得到 \(t\)，於是這就轉化成了一個線性同餘方程的問題。這樣也可以解出 \(c\)，求出 \(x\) 的一個特解 \(x_0\equiv g^c\pmod p\).

找到所有解

在知道 \(x_0\equiv g^{c}\pmod p\) 的情況下，我們想得到原問題的所有解。首先我們知道 \(g^{\varphi(p)}\equiv 1\pmod p\)，於是可以得到

\[ \forall\ t \in \mathbf{Z},\ x^a \equiv g^{ c \cdot a + t\cdot\varphi(p)}\equiv b \pmod p \]

於是得到所有解為

\[ \forall\ t\in \mathbf{Z},a\mid t\cdot\varphi(p),\ x\equiv g^{c+\frac{t\cdot\varphi(p)}{a}}\pmod p \]

對於上面這個式子，顯然有 \(\frac{a}{(a,\varphi(p))} \mid t\). 因此我們設 \(t=\frac{a}{(a,\varphi(p))}\cdot i\)，得到

\[ \forall \ i\in \mathbf{Z},x\equiv g^{c+\frac{\varphi(p)}{(a,\varphi(p))}\cdot i}\pmod p \]

這就是原問題的所有解。

實現

下面的代碼實現的找原根、離散對數解和原問題所有解的過程。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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("%d\n", ans.size());
  for (int answer : ans) printf("%d ", answer);
}

擴展篇（擴展 BSGS）

對 \(a,b,m\in\mathbf{Z}^+\)，求解

\[ a^x\equiv b\pmod 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}\pmod{\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_1d_2}\cdot a^{x-2}≡\frac{b}{d_1d_2} \pmod{\frac{m}{d_1d_2}} \]

同理，這樣不停的判斷下去，直到 \(a\perp \dfrac{m}{d_1d_2\cdots d_k}\).

記 \(D=\prod_{i=1}^kd_i\)，於是方程就變成了這樣：

\[ \frac{a^k}{D}\cdot a^{x-k}\equiv\frac{b}{D} \pmod{\frac{m}{D}} \]

由於 \(a\perp\dfrac{m}{D}\)，於是推出 \(\dfrac{a^k}{D}\perp \dfrac{m}{D}\). 這樣 \(\dfrac{a^k}{D}\) 就有逆元了，於是把它丟到方程右邊，這就是一個普通的 BSGS 問題了，於是求解 \(x-k\) 後再加上 \(k\) 就是原方程的解啦。

注意，不排除解小於等於 \(k\) 的情況，所以在消因子之前做一下 \(\Theta(k)\) 枚舉，直接驗證 \(a^i\equiv b \pmod m\)，這樣就能避免這種情況。

習題

本頁面部分內容以及代碼譯自博文 Дискретное извлечение корня 與其英文翻譯版 Discrete Root。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

參考資料

  1. Discrete logarithm - Wikipedia
  2. 潘承洞，潘承彪。初等數論。
  3. 馮克勤。初等數論及其應用。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用