BSGS 算法

BSGS 算法全称 Baby Steps Giant Steps, 大小步算法,也有人成为拔山盖世算法,北上广深算法。是数论基本算法之一。

 

问题

已知 a b p, 求满足 a^{x}\ \equiv\ b\ (Mod\ p)x
 

算法

首先判断是否有解,即 a, p是否互质。不互质即无解。
不妨令 x\ =\ im\ -\ j, 其中 m\ =\ \lceil \sqrt{q} \rceil ,这样问题变为求得一组 i j 使得条件满足。
此时原式变为 a^{im-j}\ \equiv\ b\ (Mod\ p), 移项化简得 (a^m)^i\ \equiv\ ba^j\ (Mod\ p)
这个时候我们只需穷举 i,j 使得式子成立即可。
先从让 j[0, m] 中穷举,并用 hash 记录下 ba^j 对应的 j 值。相同的 ba^j 记录较大的 j.
接着让 i[1, m] 中穷举,如果 (a^m)^i 在 hash 表中有对应的 j 存在,则对应的 im-j 是一组解。
其中第一次出现的为最小的解。
 

例题

POJ 2417 Discrete Logging
直接运用 BSGS 算法求解。因为此题中 p 为质数,所以判断互质只需判断 a % p 是否为 0 即可。
用 map 作为 hash 表减少代码量。
 

代码

代码如下:

 

完结

参考博客:
http://blog.csdn.net/clove_unique/article/details/50740412 有详细问答。
http://blog.csdn.net/clover_hxy/article/details/50683832 有详细代码。

One thought on “BSGS 算法

  1. Pingback: [bzoj3239] Discrete Logging | 火药

发表评论

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