BSGS及其拓展

求解离散对数

bsgs

​ 北(ba)上(shan)广(gai)深(shi)算法,即B(beijing)S(shanghai)G(guangzhou)S(shenzhen)算法。是指类似于\(A^x\equiv B(mod\ C)\)的方程,已知\(A\),\(B\),\(C\),求\(x\)的算法.

一种朴素的方法,我们可以枚举\(x\),从0到\(C−2\)(若\(x=C−1\),那么\(A^{p−1}≡1(mod\ p)\),费马小定理)。

这样的复杂度为\(O(C)\),对于\(C\)比较小的时候,仍是可以承受的.

若在\(C\)比较大的情况下,我们就要使用\(BSGS\)算法了.

​ 设\(m=⌈\sqrt C⌉\),\(x=i*m+j\),然后\(A^x=(A^m)^i*A^j\),其中\(0\leq i<m,0\leq j<m\)

即对\(x\)分块

​ 所以我们枚举\(i\)即可,将时间复杂度降到\(\sqrt C\).

原式为\(A^{(i+1)m}*B^{−1}≡A^{m−j}(mod\ C)\),其中\(B^{−1}\)表示\(B\)的逆元,由于\(m−j≤m\),我们开一个数组哈希或\(map\)存即可.即可求出\(A^j\),只需要哈希查表即可得到\(j\).最后由\(x=i*m+j\)即可得到\(x\).

时间复杂度

\[O(1)->O(log_2C)\]

代码实现


exbsgs

​ 如果,如果不存在互质条件则需要去二线北上广深\(exbsgs\)

​ 一开始的方程为\(A^x*a+C*b=B~(a,b\in Z)\),设\(t=gcd(A,C)\),由裴蜀定理可知,\(B\)如果不能被\(t\)整除,就无解了。

​ 对于一个方程\((\frac{A}{t})^{x′}*a′+(\frac{C}{t})*b′=\frac{B}{t}\),两端乘\(t\),得到\(A^{x′+1}*a′+C*b′=B\)

可以通过算\(x′\),然后\(x=x′+1\).继续暴力迭代直至\(gcd(A,C)=1\),假设做了\(cnt\)次,那么\(x=x′+cnt\)。

然后我们用普通\(BSGS\)求出\(x′\)即可。简单吧

时间复杂度

\[log_2C\]

代码实现

在原来的bsgs上判断一下从两者不互质到互质差几次,然后正常bsgs就好了,最后的答案+差的次数.

BSGS及其拓展》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注