标签：int 复杂度 times 离散 pmod 对数 BSGS equiv

离散对数定义

求 $k$ 使得 $a^k \equiv n \pmod p$ ，称 $n$ 在模 $p$ 意义下以 $a$ 为底的对数是 $k$ 。

如何求离散对数

BSGS（Baby Step,Giant Step）大步小步算法可以求离散对数，它的思想是分块思想。

首先要满足 $a \perp p$ ，因为在后面会需要把两边同时除以 $a$ 的幂，所以需要 $a \perp p$ 。

考虑朴素的算法，我们可以枚举 $k$ ，找到使得 $a^k \equiv n \pmod p$ 的 $k$ ，时间复杂度 $O(p)$ ，但 $p$ 一般都很大，所以考虑优化。

我们可以把 $1$ 到 $p$ 进行分块，然后先一块一块地走，然后快到答案是再一个一个走，如果块长是 $m$ ，时间复杂度为 $O(\max\{m,p/m\})$ ，不难发现，当 $m = \sqrt n$ 时，时间复杂度是最优的 $O(\sqrt p)$ ，这就是 BSGS 的思想，可以从名字里看出。

具体实现：设一大步步长为 $t$ ，大步步数为 $i$ ，则 $k=i \times t - r$ ，其中 $r$ 是往回走小步的步数，把它代入上面的式子中可得：

\[a^{i\times t - r} \equiv n \pmod p \]

\[a^{i\times t} \times a^{-r} \equiv n \pmod p \]

\[a^{i \times t} \equiv n \times a^{r} \pmod p \]

我们可以枚举大步步数（大步步长是确定的），然后每次判断有没有 $r$ 满足 $a^{i \times t} \equiv n \times a^{r} \pmod p$，但是如果枚举 $r$ 就还是 $O(p)$ 的，但 $1 \le r < t $ ，所以我们可以预处理出 $n \times a^{0}$ ， $n \times a^{1}$ 一直到 $n \times a^{t}$ ，然后用 map 存下来，以他们对 $p$ 的余数作为索引，$a^{r}$ 中的 $r$ 作为值，然后枚举大步步数，每次 $O(1)$ 判断，这样时间复杂度就是 $O(\sqrt p \log p)$ ，其中 $\log p$ 是 map 的时间复杂度。这就是 BSGS 。

code

int fpow(int a, int b, int p) {
	if (b == 1)
		return a;
	int ans = fpow(a, b / 2, p);
	ans = (1ll * ans * ans) % p;
	if (b % 2 == 1)
		ans = (1ll * ans * a) % p;
	return ans; 
}
int stp, r;
int nbr[50000], t;
map<int, int> mp;
int BSGS(int p, int b, int n) {
	stp = sqrt(p), t = fpow(b, stp, p), nbr[0] = n % p;
	for (int i = 1; i < stp; i++) { //注意这里是小于，不然 n=1 时会挂
	    nbr[i] = (1ll * nbr[i - 1] * b) % p;
	    mp[nbr[i]] = i;
	}
	for (int i = 1, lt = t; 1ll * i * stp - stp <= p; i++, lt = (1ll * lt * t) % p)
		if (mp[lt] > 0) 
		    return 1ll * i * stp - mp[lt];
	return -1;
}

BSGS 求阶

当 $a \perp p$ 时，最小的正整数 $k$ 满足 $a^k \equiv 1\pmod p$ ，则称 $k$ 是 $n$ 模 $p$ 的阶，记作 $\delta_p(a)$ 或 $Ord_p(a)$ 。

一个数的阶就可以用 BSGS 来求，方法同上面一样。

BSGS 的一些题目

P1082 [NOIP2012 提高组] 同余方程

题意：求最小的正整数 $x$ 满足 $ax \equiv 1 \pmod p$ 。

思路：

这题的题解貌似一篇 BSGS 的都没有~~

BSGS 不只是可以求离散对数，这道题也可以做。我们设一大步步长为 $t$ ，大步步数为 $i$ ，则 $x=i \times t - r$ ，其中 $r$ 是往回走小步的步数，把它代入上面的式子中可得：

\[a\times(i \times t-r) \equiv 1 \pmod p \]

\[a \times i \times t \equiv a \times r + 1 \pmod p \]

所以我们就可以提前预处理出所有 $1 \le r \le \sqrt p$ 的 $ar+1$ 的值，然后枚举大步，每次 $O(1)$ 判断即可，时间复杂度 $O(\sqrt p \log p)$。

P2485 [SDOI2011]计算器

题意：回答三种询问，分别是：

$y^z \mod p$ 的值。
满足 $xy \equiv z\pmod p$ 的最小整数 $x$ 。
满足 $y^x \equiv z \pmod p$ 的最小整数 $x$ 。

思路

操作一：直接快速幂即可。

操作二：BSGS 直接求，和上一道题几乎一样，就是把 $ar+1$ 改成 $ar+z$ 即可。

操作三：BSGS 原封不动就可以了。

时间复杂度：$O(\sqrt p \log p)$ 或 $O(\log z)$ 。

标签：int,复杂度,times,离散,pmod,对数,BSGS,equiv
From： https://www.cnblogs.com/rlc202204/p/16949459.html

离散对数&BSGS学习笔记