离散对数

引入

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

多值函数

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

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

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

它的主值是：

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

离散对数

对于模 的原根 ，如果有：

则称 在模 意义下，以 为底的对数为 。

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

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

它的主值是：

规定主值 取 到 。当 是素数时，就是 到 。

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

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

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

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

换底公式

如果模 存在不同的两个原根 和 ，则离散对数可以换底，换底公式与通常的对数一致。借助模 的记号，可以写为：

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

大步小步算法

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

其中 。方程的解 满足 。（在这里需要注意，只要 就行了，不要求 是素数）

算法描述

令 ，其中 ，则有 ，稍加变换，则有 。

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

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

进阶篇

求解

其中 是个质数。

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

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

方法一

我们令 ， 是 的原根（我们一定可以找到这个 和 ），问题转化为求解 。稍加变换，得到

于是就转换成了我们熟知的 BSGS 的基本模型了，可以在 解出 ，这样可以得到原方程的一个特解 。

方法二

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

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

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

找到所有解

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

于是得到所有解为

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

这就是原问题的所有解。

实现

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

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 算法求解。于是我们想办法让他们变得互质。

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

如果 和 仍不互质就再除，设 。如果 ，则方程无解；否则同时除以 得到

同理，这样不停的判断下去。直到 。

记 ，于是方程就变成了这样：

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

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

习题

• 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。