夢に僕らで帆を張って
来るべき日のために夜を超え

标签 BSGS算法 下的文章

September 26, 2019

BSGS算法

BSGS(Baby Step Giant Step)算法一、BSGS算法求解高次同余方程$$A^x \equiv B \ (\bmod \ C)$$其中 $(A,C)=1$1.求解令 $x=im+j$此时方程转化为$$A^j \equiv B \cdot A^{-im} \ (\bmod \ C)$$首先对 $i \in [1,m-1]$ ,计算出 $A^i \% C$ 并将其存入hash表...