JZTXT

初等数论（Ⅲ）：高次同余、阶和原根相关

发布时间 2023-05-27 08:17:05作者: Bloodstalk

前言

关于高次同余方程，有 \(a^x \equiv b(\text{mod} \ p)\) 和 \(x^a \equiv b(\text{mod} \ p)\) 两种类型，后者计算起来较为麻烦，下文就分别记述这两种高次同余方程。

离散对数问题

离散对数问题是在模 \(p\) 意义下求解 \(\log_ab\)，这等价于形如

\[a^x \equiv b(\text{mod} \ p) \]

的高次同余方程，其中 \(x\) 即为 \(\log_ab\)，\(x\) 是一个非负整数。

当 \(a \perp b\) 时，我们可以采用 BSGS 算法解决；当 \(a \not\perp b\) 时，可以采用 exBSGS 算法求解。

BSGS

大步小步算法，英文名为 Baby Step Giant Step，简称 BSGS。适用于 \(a\perp p\) 的情况。

算法流程

由扩展欧拉定理得

\[a^x \equiv a^{x \mod \varphi(p)}(\text{mod} \ p) \]

所以 \(a^x\) 模 \(p\) 意义下的循环节就是 \(\varphi(p)\)，又因 \(\varphi(p) < p\)，所以考虑 \(x\in[0,p]\) ，一定能找到最小整数 \(x\)。自此，问题缩小到了 \(O(p)\) 级别。如果 \(p\leq 2^{32}\)，那就超时了。这时候就要请出我们今天的主角----根号平衡闪亮登场！

我们令 \(x = im-j\)，其中 \(m=\lceil \sqrt{p} \ \rceil , i\in[1,m],j\in[0,m-1]\)。这样分配，\(im-j\) 就能取遍 \([1,p]\) 了，如果 \(x=0\)，说明 \(b=1\)，特判一下就行了。

我们把上式转换一下，则有

\[a^{im-j} \equiv b(\text{mod} \ p) \]

因为 \(a\perp p\) ，所以

\[(a^{m})^i \equiv ba^j(\text{mod} \ p) \]

是一个等价转换（除回去模数不变）。

然后枚举 \(i,j\)。

  1. 先枚举 \(j\)，把 \((ba^j \ \text{mod} \ p,j)\) 插入一个 Hash 表。如果 \(ba^j \ \text{mod} \ p\) 出现相等的情况，为了求最小解，显然用更大的 \(j\) 替代小的解。

  2. 然后枚举 \(i\) ，计算 \((a^m)^i \ \text{mod} \ p\)，到 Hash 表中判断是否有相等的 key，因为 \(i\times m\) 的变化量是比 \(j\) 大的，所以我们找到第一个就可以结束程序，最小的 \(x=im-j\) 就出来了。

这样，枚举 \(i,j\) 的次数都是 \(\sqrt p\) 的，总算法的复杂度也就是 \(O(\sqrt{p\ })\) 的。

map <int,int> Hash;

signed main()
{
	mod = read() , a = read(), b = read();
	if(b == 1) { return printf("0"),0; }//特判一下
	m = ceil(sqrt(mod));
	Hash[b] = 0/*j取0,ba^j就是b*/ , t = b;
	for(re int i=1;i<m;i++)//枚举ba^j
	{
		t = t * a % mod;
		Hash[t] = i;
	}
    
    
	val = ksm(a,m) , t = 1;
	for(re int i=1;i<=m;i++)//枚举(a^m)^i
	{
		t  = t * val % mod;
		if(Hash.count(t)) {  return printf("%lld",i*m-Hash[t]),0; }//有值直接输出
	}
	printf("no solution");
	return 0;
}

exBSGS

当 \(a\not\perp p\) 的时候，我们的 exBSGS 就要出场了。

化未知为已知，我们思考怎么操作能让 \(a,p\) 互质。

首先，原方程可以写作

\[a \cdot a^{x-1} \equiv b(\text{mod} \ p) \]

的形式，这就是把 \(a\) 提出来的一个过程。这也等价于求 \(a\cdot a^{x-1} + py = b\) 的解。

令 \(d_1 = \gcd(a,p)\)。如果 \(d_1\nmid b\)，则原方程无解。

否则由同余的性质得，同余方程就变成

\[\frac{a}{d_1}a^{x-1} \equiv \frac{b}{d_1}(\text{mod} \ \frac{p}{d_1}) \]

这启发我们要不断提取 \(a\) 出来，直到 \(a\) 和模数互质。

设 \(d_2 = \gcd(a,\frac{p}{d_1})\)，然后重复上述操作，直到互质。

当 \(a\perp \frac{p}{d_1\dots d_k}\) 时，我们就可以套用 BSGS 了。设 \(D = \prod_{i=1}^kd_i\)，原方程就变成了形如

\[\frac{a^k}{D}a^{x-k} \equiv \frac{b}{D}(\text{mod} \ \frac{p}{D}) \]

的形式。因为 \(a\perp \frac{p}{D}\)，所以 \(\frac{a^k}{D}\perp \frac{p}{D}\)，那么就可以求个逆元，把 \(\frac{a^k}{D}\) 消掉，然后再套一个 BSGS 就可以了。

注意，BSGS 结束后算出来的是 \(x-k\) 而非 \(x\)，别忘了把 \(k\) 加上。

实际上，\(\frac{a^k}{D}\) 也可以不用求逆元，只要在 BSGS 枚举 \(i\) 的时候把初值设为 \(\frac{a^k}{D}\) 即可。

code

il int BSGS(int a,int b,int mod,int k)
{
	Hash.clear();
	m = ceil(sqrt(mod));
	Hash[b] = 0 , t = b;
	for(re int i=1;i<m;i++)
	{
		t = 1ll * t * a % mod;
		Hash[t] = i;
	}
	val = ksm(a,m,mod) , t = k;//初值设为k
	for(re int i=1;i<=m;i++)
	{
		t  = 1ll * t * val % mod;
		if(Hash.count(t)) {  return i*m-Hash[t]; }
	}
	return -1;
}

il void exBSGS()
{
	a = read() , mod = read() , b = read();
	if(!a && !mod && !b) exit(0);
	a %= mod , b %= mod;//先模再特判
	if(b == 1 || mod == 1) { puts("0"); return ; }
	cnt = d = 0 , k = 1;
	while((d=gcd(a,mod)) != 1)
	{
		if(b % d) { puts("No Solution"); return; }//无解情况
		cnt++;//不知道为什么这个放在if上面就wa一个点，很怪
		b /= d , mod /= d;//逐渐往下找
		k = 1ll * k * (a / d) % mod;//a^{x-k}前的系数
		if(k == b) { printf("%d\n",cnt); return ; }//k==b说明a^{x-k} = 1,x=k
	}
	ans = BSGS(a,b,mod,k);
	if(ans == -1) puts("No Solution");
	else printf("%d\n",ans+cnt);
}