BSGS(Baby steps giant steps)算法学习笔记

离散对数(Discrete Logarithm)问题是这样一个问题,它是对于模方程

a^x=b(mod prime),求满足条件的X,或者得出不存在这样的X

最暴力的思路,那么就是枚举x? 根据费马小定理,只需要枚举[0,p-1)

但是还是很大…我们不禁想到把x写成x=A*m+B的形式,m=ceil(sqrt(p))

因此有 a^{A\lceil \sqrt{p} \rceil + B} \equiv b \pmod p ,变形得到 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^{-B} \pmod p

然后预处理一边存到map中,从小到大枚举另一边看是否存在…

 

我们可以设 x=A \lceil \sqrt{p} \rceil - B,其中 0 \leq B < \lceil \sqrt{p} \rceil,  0 < A \leq \lceil \sqrt{p} \rceil + 1,这样的话化简后的方程就是

 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^B \pmod p

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

 

其实在m=sqrt(p)的时候你可能就有预感了…

BSGS算法的本质,就是个分块啊,而分块的本质就是暴力乱搞…所以BSGS看起来很高大上的算法不过是暴力乱搞2333

而BSGS的名字也很贴切…A的变化是giant step?B的变化是baby step? (纯属yy…但是我感觉这样想很好理解啊?

需要注意的是,这里介绍的是常规的BSGS算法,

前提条件是a和P互质

前提条件是a和P互质

前提条件是a和P互质

放一个板子好了,poj 2417

 

参考资料:

一个很多BSGS算法初学者的误区

扩展大步小步法解决离散对数问题

大步小步算法与扩展大步小步算法

BSGS算法学习小记(大步小步算法)

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz