跳转至

离散对数

定义

前置知识:阶与原根

离散对数的定义方式和对数类似。取有原根的正整数模数 ,设其一个原根为 . 对满足 的整数 ,我们知道必存在唯一的整数 使得

我们称这个 为以 为底,模 的离散对数,记作 ,在不引起混淆的情况下可记作 .

显然 .

性质

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

性质

是模 的原根,,则:

  1. 进而

  2. 也是模 的原根,则

证明
  1. ,则 . 又令 ,则 .

    ,即

  2. 注意到

大步小步算法

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

在算法竞赛中,BSGS(baby-step giant-step,大步小步算法)常用于求解离散对数问题。形式化地说,对 ,该算法可以在 的时间内求解

其中 。方程的解 满足 .(注意 不一定是素数)

算法描述

,其中 ,则有 ,稍加变换,则有 .

我们已知的是 ,所以我们可以先算出等式右边的 的所有取值,枚举 ,用 hash/map 存下来,然后逐一计算 ,枚举 ,寻找是否有与之相等的 ,从而我们可以得到所有的 .

注意到 均小于 ,所以时间复杂度为 ,用 map 则多一个 .

为什么要求 互质

注意到我们求出的是 ,我们需要保证从 可以推回 ,后式是前式左右两边除以 得到,所以必须有 .

进阶篇

,求解

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

由于式子中的模数 是一个质数,那么 一定存在一个原根 . 因此对于模 意义下的任意的数 有且仅有一个数 满足 .

方法一

我们令 的原根(我们一定可以找到这个 ),问题转化为求解 . 稍加变换,得到

于是就转换成了 BSGS 的基本模型了,可以在 解出 ,这样可以得到原方程的一个特解 .

方法二

我们仍令 ,并且设 ,于是我们得到

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

我们可以通过 BSGS 求解 得到 ,于是这就转化成了一个线性同余方程的问题。这样也可以解出 ,求出 的一个特解 .

找到所有解

在知道 的情况下,我们想得到原问题的所有解。首先我们知道 ,于是可以得到

于是得到所有解为

对于上面这个式子,显然有 . 因此我们设 ,得到

这就是原问题的所有解。

实现

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

参考代码
 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("%zu\n", ans.size());
  for (int answer : ans) printf("%d ", answer);
}

扩展篇(扩展 BSGS)

,求解

其中 不一定互质。

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

具体地,设 . 如果 ,则原方程无解。否则我们把方程同时除以 ,得到

如果 仍不互质就再除,设 . 如果 ,则方程无解;否则同时除以 得到

同理,这样不停的判断下去,直到 .

,于是方程就变成了这样:

由于 ,于是推出 . 这样 就有逆元了,于是把它丢到方程右边,这就是一个普通的 BSGS 问题了,于是求解 后再加上 就是原方程的解啦。

注意,不排除解小于等于 的情况,所以在消因子之前做一下 枚举,直接验证 ,这样就能避免这种情况。

习题

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

参考资料

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