离散对数（Discrete Logarithm）问题是这样一个问题，它是要求解模方程

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

这个问题是否存在多项式算法目前还是未知的，这篇文章先从 $m$ 是质数开始介绍大步小步法（Baby Step Giant Step）来解决它，之后再将其应用到 $m$ 是任意数的情况。这个算法可以在 $\mathcal O(\sqrt m)$ 的时间内计算出最小的 $x$，或者说明不存在这样一个 $x$

题目链接：BZOJ-2480、SPOJ-MOD、BZOJ-3239

模数为质数的情况

首先解决 $m=p$ 是质数的情况，我们可以设 $x = A \lceil \sqrt{p} \rceil + B$，其中 $0 \leq B < \lceil \sqrt{p} \rceil$,  $0 \leq A < \lceil \sqrt{p} \rceil$，这样的话就变成求解 $A$ 和 $B$ 了，方程也变成

\[a^{A\lceil \sqrt{p} \rceil + B} \equiv b \pmod p\]

可以在两边同时乘以 $a^B$ 的逆元，由于 $p$ 是质数，这个逆元一定存在，于是方程变成

\[a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^{-B} \pmod p\]

由于 $A, B$ 都是 $\mathcal O(\sqrt p)$ 级别的数，可以先计算出右边这部分的值，存入 Hash 表，然后计算左边的值，在 Hash 表中查找，只要按照从小到大的顺序如果有解就能够找到最小的解，由于两边都只有 $\mathcal O(\sqrt p)$ 个数，因此时间复杂度是 $\mathcal O(\sqrt p)$ 的，这样 $m$ 是质数的情况就解决了

一个优化

我们可以设 $x = A \lceil \sqrt{p} \rceil - B$，其中 $0 \leq B < \lceil \sqrt{p} \rceil$,  $0 < A \leq \lceil \sqrt{p} \rceil + 1$，这样的话化简后的方程就是

\[a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^B \pmod p\]

就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在

一般情况

现在来看 $m$ 不是质数的情况，同样可以设 $x = A \lceil \sqrt{m} \rceil + B$，根据上面的推导，会发现需要用到的性质就是 $a^B$ 的逆元存在，所以当 $m$ 和 $a$ 互质的时候这个方法仍然有效！

如果 $(m, a) \neq 1$ 该怎么办呢？我们要想办法把方程转化为 $(m, a) = 1$ 的情况

把要求的模方程写成另外一种形式

\[a^x + km = b, k \in \mathbb Z\]

设 $g = (a, m)$，这样的话可以确定如果 $g \nmid b$ 那么该方程一定无解，所以当 $g \mid b$ 的时候，在方程左右两边同时除以 $g$

\[\frac{a}{g} a^{x-1} + k \frac{m}{g} = \frac{b}{g}, k \in \mathbb{Z}\]

这样便消去了一个因子，得到方程

\[\frac{a}{g} a^{x-1} \equiv \frac{b}{g} \pmod {\frac{m}{g}}\]

令 $m’ = \frac{m}{g}, b’ = \frac{b}{g} \left (\frac{a}{g}\right)^{-1}$（这里不可以把 $g$ 消掉），就可以得到新的方程

\[a^{x'} \equiv b' \pmod {m'}\]

得到解之后原方程的解 $x = x’ + 1$，不断重复这个过程最后一定会得到一个可以解的方程，套用刚刚的大步小步法解出后即可。要注意的是在这个过程中如果某一步发现 $b’=1$，那么就可以直接退出，因为这时候已经得到了解

代码

下面的是代码，题目是文章开头给的链接（题目应该是加了一组模$1$的数据，原先的代码才会WA）

/* BZOJ-2480: Spoj3105 Mod
 *   扩展大步小步  */
#include <cstdio>
#include <cmath>
#include <map>

int mod_pow(long long x, long long p, long long mod_v)
{
	long long v = 1;
	while(p)
	{
		if(p & 1) v = x * v % mod_v;
		x = x * x % mod_v;
		p >>= 1;
	}

	return v;
}

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

int baby_step_giant_step(int a, int b, int p)
{
	a %= p, b %= p;
	if(b == 1) return 0;
	int cnt = 0;
	long long t = 1;
	for(int g = gcd(a, p); g != 1; g = gcd(a, p))
	{
		if(b % g) return -1;
		p /= g, b /= g, t = t * a / g % p;
		++cnt;
		if(b == t) return cnt;
	}

	std::map<int, int> hash;
	int m = int(sqrt(1.0 * p) + 1);
	long long base = b;
	for(int i = 0; i != m; ++i)
	{
		hash[base] = i;
		base = base * a % p;
	}

	base = mod_pow(a, m, p);
	long long now = t;
	for(int i = 1; i <= m + 1; ++i)
	{
		now = now * base % p;
		if(hash.count(now))
			return i * m - hash[now] + cnt;
	}

	return -1;
}

int main()
{
	int a, b, p;
	while(std::scanf("%d %d %d", &a, &p, &b), p)
	{
		int ans = baby_step_giant_step(a, b, p);
		if(ans == -1) std::puts("No Solution");
		else std::printf("%d\n", ans);
	}
	return 0;
}

本文遵守 CC BY-NC 4.0 许可协议。