BSGS - syysongyuyang's blog

BSGS,解决离散对数问题

$BSGS$:解决离散对数问题

例题：

求$a^x\equiv b \pmod p$的最小正整数解$x$

性质：$\gcd(a,p)=1$

解法：

~~自然是可以大力枚举$x$！再套上指令集+循环展开就可以切了~~

我们定义$x=A\left \lceil p \right \rceil - B$

所以原式变成了$a^{A\left \lceil p \right \rceil-B}\equiv b \pmod p$

容易发现，$a^{-B}$可以移到式子的右边

所以式子变成了$a^{A\left \lceil p \right \rceil} \equiv a^{B}b \pmod p$

并且，容易发现$A,B$均小于等于$\sqrt p$

所以我们首先枚举$B$，将$a^ib \bmod p$的值用map或hash或unordered_map存储下来

然后再枚举$A$，找到的第一个就是最小的，答案为$i\times\left \lceil p \right \rceil-k$

所以我们就找到了$a^x\equiv b \pmod p$的最小整数解$x$

代码:

inline int BSGS()
{
    int m,a,b,q;
    m=ceil(sqrt(p));
    for (int i=0,t=b;i<=m;i++,t=t*a%p) rec[t]=i;
    for (int i=1,tt=ksm(a,m),t=tt;i<=m;i++,t=t*tt%p) 
    	if (rec[t]) return i*m-rec[t];
   	return -1;
}

进阶

众所周知，数论中的算法总会有个EX++++++++++的版本

而这个超进化，从~~阉割版~~正常版变成~~普通版~~EX版的条件一般是模数$p$与某数是否互质或$p$为素数

例题：

求$a^x\equiv b \pmod p$的最小正整数解$x$

要求：$\gcd(a,p)$不一定等于$1$

和$exLucas$很像，我们首先得想办法将$\gcd(a,b)$变成$1$

具体的，我们令$d_1=\gcd(a,p)$，若$d_1 \nmid b$，无解

~~咕咕咕~~

然后每次我们将$a’=a\div d_1,p’=p\div d_1,b’=b\div d_1$，直到$\gcd(a’,p’)=1$，假设进行了$k$次

不妨设$D=\prod\limits_{i=1}^{k}d_i$

这个式子就变成了$\frac {a} {D}\times a^{x-k}\equiv\frac {b} {D} \pmod{\frac {p} {D}}$

此时$\gcd(\frac {a}{D},\frac {p} {D})=1$，跑一次阉割普通版$BSGS$就可以了，最后答案要加$k$

代码：

inline int ksm(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;
}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int BSGS(int a,int n,int p,int ad)
{
	rec.clear();
	int m=std::ceil(std::sqrt(p));
	int s=1;
	for(int i=0;i<m;i++,s=1ll*s*a%p) rec[1ll*s*n%p]=i;
	for(int i=0,tmp=s,s=ad;i<=m;i++,s=1ll*s*tmp%p)
		if(rec.find(s)!=rec.end())
			if(1ll*i*m-rec[s]>=0) return 1ll*i*m-rec[s];
	return -1;
}
inline int exBSGS(int a,int n,int p)
{
    a%=p,n%=p;
    if (n==1 || p==1) return 0;
    int cnt=0,d=1,ad=1;
    while ((d=gcd(a,p))^1)
    {
        if (n%d) return -1;
        cnt++;n/=d,p/=d;
        ad=(1ll*ad*a/d)%p;
		if(ad==n) return cnt;
    }
    int res=BSGS(a,n,p,ad);
    if (res==-1) return res;
    return res+cnt;
}

题目：124 OJ 1226