简介
BSGS（baby-step giant-step），即大步小步算法，常用于求解离散对数问题。形式化地说，该算法可以在 \(O(\sqrt{p})\) 的时间内求解 \(a^x \equiv b \pmod p\) （\(a\perp p\)） 方程的解 \(x\) 满足 \(0 \le x < p\)。（在这里需要注意，只要 \(a\perp p\) 就行了，不要求 \(p\) 是素数）
扩展
对于\(a^x \equiv b \pmod p\)，\(a,p\)不一定互质，在模 \(p\) 意义下 \(a\) 不一定存在逆元，于是我们想办法让他们变得互质
我们设 \(d_1=\gcd(a,p)\)，如果 \(d_1\nmid b\)，则原方程无解。否则我们把方程同时除以 \(d_1\)，得到
如果\(a\not\perp \frac{p}{d_1}\)，就继续除，设 \(d_2=\gcd\left(a,\frac{p}{d_1}\right)\) ，如果 \(d_2\nmid \frac{b}{d_1}\)，则方程无解；否则同时除以 \(d_2\) 得到
\[\frac{a}{d_1\cdot d_2}\cdot a^{x-2}\equiv \frac{b}{d_1\cdot d_2} (\mod \frac{p}{d_1\cdot d_2}) \]重复上述操作，直到\(a\perp \frac{p}{d_1\cdot d_2 \dots d_k}\)
code
BSGS
il int bsgs(int a,int b,int p){
if(1%p==b%p) return 0;
int t=ceil(sqrt(p)),s=1,ss=0;
mp.clear();
for(ri int i=0;i<t;++i){
if(s==b) return i; // a^0=1
mp[s*b%p]=i,s=s*a%p;
}
ss=s;
for(ri int i=1;i<=t;++i){
if(mp.count(ss)) return i*t-mp[ss];
ss=ss*s%p;
}
return -1;
}
exBSGS
il int exbsgs(int a,int b,int p){
int d=1,nxtd=0,as=0,xi=1%p,k=0;
while(1){
nxtd=gcd(xi*a%p,p);
if(d==nxtd) break;
if(xi==b) return k;
++k,xi=xi*a%p,d=nxtd;
}
if(b%d) return -1;
xi/=d,p/=d,b/=d;
b=b*inv(xi,p)%p,as=bsgs(a,b,p);
return (~as)?k+as:as;
}
知识点
阶
-
定义：由欧拉定理可知，对\(a\in \mathbb{Z},m\in\mathbb{N^* }\)，若\(gcd(a,m)=1\) ，则 \(a^{\varphi(m)}\equiv 1\pmod m\)
因此满足同余式\(a^n\equiv 1\pmod m\)的最小正整数\(n\)存在，这个\(n\)称作\(a\)模\(m\)的阶，记作\(\delta_m(a)\) -
性质：
-
\(a^1,a^2,...,a^{\delta_m(a)}\)模\(m\)两两不同余
-
若\(a^n\equiv 1\pmod m\),则\(\delta_m(a)\mid n\)
推论1:若\(a^p\equiv a^q\),则有\(p\equiv q \pmod{\delta_m(a)}\)
推论2:若\(gcd(a,m)=1\),\(\delta_m(a)\mid\varphi(m)\) -
设\(m\in\mathbb{N^* },a,b\in\mathbb{Z},gcd(a,m)=gcd(b,m)=1\),则\(\delta_m(a\cdot b)=\delta_m(a)\cdot \delta_m(b)\) 的充分条件是\(gcd(\delta_m(a),\delta_m(b))=1\)
-
设\(k\in\mathbb{N},m\in\mathbb{N^* },a\in\mathbb{Z},gcd(a,m)=1\)，则\(\delta_m(a^k)=\frac{\delta_m(a)}{gcd(\delta_m(a),k)}\)
-
若\(p\) 为素数，则\(\delta_p(g^i)=\delta_p(g)\)的充要条件为\(gcd(\delta_p(g),i)=1 (g\in\mathbb{N^* })\)。\(\\g^i\)也可以表示为\(g^{gcd(\delta_p(g),i)\cdot r} (r\in\mathbb{N^* })\)
原根
-
定义：设\(m\in\mathbb{N^* },a\in\mathbb{Z}\),若\(gcd(a,m)=1\),且\(\delta_m(a)=\varphi(m)\),则称\(a\)为\(m\)的原根
-
定理：
-
原根判定定理：设\(m\geqslant3,gcd(a,m)=1\)，则\(a\)是模\(m\)的原根的充要条件是，对于\(\varphi(m)\)的每个素因数\(p\)，都有
$a^{\frac{\varphi(m)}{p}}\not\equiv1\pmod m $ -
原根个数：若一个数\(m\)有原根，则它原根的个数为\(\varphi(\varphi(m))\)
-
原根存在定理：
引理1：设\(a\)与\(b\)是与\(p\)互素的两个整数，则存在\(c\in\mathbb{Z}\)使得\(\delta_p(c)=lcm(\delta_p(a),\delta_p(b))\)
定理1：一个数\(m\)存在原根当且仅当\(m=2,4,p^\alpha,2\cdot p^\alpha\)，其中\(p\)为奇素数，\(\alpha\in\mathbb{N^* }\)
引理2：存在模\(p\)的原根\(g\)，使得\(g^{p-1}\not\equiv1\pmod{p^2}\)
定理2：对于奇素数\(p,\alpha\in\mathbb{N^* }\)，\(p^\alpha\) 有原根
定理3：对于奇素数\(p,\alpha\in\mathbb{N^* }\),\(2\cdot p^\alpha\) 的原根存在
定理4：对于\(m\ne2,4\)，且不存在奇素数\(p\)及\(\alpha\in\mathbb{N^* }\)使得\(m=p^\alpha,2\cdot p^\alpha\)，模\(m\)的原根不存在 -
若\(gcd(g,n)\)且(n>0)，则\(g\)为\(n\)的一个原根的充要条件为\(S=\{g^1,g^2...g^{\varphi(n)}\}\)为\(n\)的一组简化剩余系
-
若奇素数\(p\)的原根\(g\)满足\(g^{p-1}\not\equiv1\pmod {p^2}\)，则对于每一个\(a\geqslant2\)，有\(g^{\varphi(p^{a-1})}\not\equiv1\pmod {p^a}\)
-
若\(p\)为素数，\(a\)为整数且\(p\nmid a\)，则在一个模\(p\)的完全剩余系中恰有\(\varphi(\delta_p(a))\)个数模\(p\)的阶为\(\delta_p(a)\)
-
对于任意整数\(h\)使得\(\delta_p(h)=\delta_p(a)\)，定存在\(a^{d_i} (i\in[1,\varphi(\delta_p(a))\cap\mathbb{Z}])\)在模\(p\)意义下与\(h\)同余
-
若\(p\)为整数且有一个原根\(g\)，则\(p\)恰有\(\varphi(\varphi(p))\)个在模\(p\)意义下不同余的原根，它们由集合\(S=\{g^i|1\leqslant i\leqslant\varphi(p),gcd(p,i)=1\}\)中的数给出