BSGS学习笔记

算法介绍

BSGS(Baby-Step Giant-Step)算法用于求如下方程的解:

axb  (mod  p),  p a^x \equiv b \; (mod \; p), \; p \ 为质数

m=pm = \lceil \sqrt p \rceil。根据费马小定理,有 ap11  (mod  p)a^{p - 1} \equiv 1\; (mod\; p),故若方程有解,则必然存在一个解满足 0x<p10 \leqslant x < p - 1。设该解为 x=im+jx = im + j,其中 0i, jm0 \leq i,\ j \leq m

方程可化为:

\begin{align} a^x &\equiv b\; (mod \; p) \\ a^{im + j} &\equiv b\; (mod\; p) \\ a^j &\equiv b a^{-im}\; (mod\; p) \\ a^j &\equiv b (a^{-m})^i (mod\; p) \\ \end{align}

我们只需要找到一组 iijj 使得最后一个式子成立即可。

枚举 jj,求出左边aj  mod  pa^j \; mod \; p 的所有取值,并将以(j,  aj)(j, \; a^j)的映射关系插入到一个表中。

之后,求出ama^m在模pp意义下的乘法逆元。枚举 ii,求出所有的 b(am)ib(a^{-m})^i,每得到一个值后,从表中查找该值,如果存在,取出其对应的jjx=im+jx = im + j即为一个解。

时间复杂度为 O(p)O(\sqrt p)

模板题

BZOJ 2242题解