Baby-step giant-step

现在的位置: 首页 > 综合 > 正文

Baby-step giant-step

2018年04月05日 ⁄ 综合 ⁄ 共 549字 ⁄ 字号小中大 ⁄ 评论关闭

转自：http://qinz.maybe.im/?p=50398

不知道为什么这算法会有这么诡异的名字，比“舞蹈链”（Dancing link）还诡异。但话说回来，这算法确实是我数论学习上的Baby-step giant-step，另外发现自己似乎很久没写月志了，就写篇纪念下吧~（其实算是Wikipedia上这篇文章的简单翻译-_-b）

定理的条件：m为质数　　

众所周知， $a^b \equiv c \pmod m$ ，其中m为质数，式中已知a、b、m求c很方便，用快速模取幕可以在 $O(\log_2 m)$ 的时间复杂度求出来。但如果已知a、c、m求b就不是那么容易求了，简单地枚举需要 $O(m)$ 的时间，但在竞赛中这时间复杂度基本不可能通过。而Baby-step
giant-step算法利用 $b=in+j \,,n=\lceil \sqrt{m} \rceil \,,0 \leq i < m \,,0 \leq j < m$ 把 $a^b \equiv c \pmod m$ 转化为 $c(a^{-n})^i \equiv a^j \pmod m$ ，利用Hash（或者二分查找）很强势地使时间复杂度降到了 $O(\sqrt m)$ ，这种时间复杂度下对于 $m<2^{32}$ 的数据范围来说是绰绰有余的。下面就来介绍下这种神奇又简单的算法（如果m是个合数的话还有一种更快的算法叫Pohlig-Hellman
algorithm，大致思路是把合数分解再用中国剩余定理合并起来，本文不作讨论）：