大步小步算法（BSGS）及扩展 bzoj 2480

热度：68 发布时间：2024-01-05 02:18:27.0

大步小步算法用于解决离散对数问题：
求满足 $a^x \equiv y \pmod p$ 的最小自然数 $x$ ，其中 $a$ 、 $p$ 互质，或者报告无解。

根据欧拉定理， $a^\phi(p) \equiv 1 \pmod p$ ，所以，如果有解，必然有一个在 $[0, \phi(p))$ 内。为了简单起见，直接考察 $[0, p-1)$ 。

让我们运用meet-in-middle的思想。设 $x = km - r (1\le r \le m)$ ， $m$ 是某个选定的数，那么

(a m) k \equiv y a r (mod p)

$(a^m)^k \equiv ya^r \pmod p$
枚举

r=1,2,...,m $r = 1, 2, ..., m$ ，将

(yarmodp,r) $(ya^r \mod p, r)$ 存入一张表。枚举

k=1,2,...,ceiling(p

相关解决方案