离散对数

Summary

求 a 的 x 次方模 p 等于 b 的最小非负整数 x，称为离散对数问题。当 a 与 p 互质时用大步小步算法 BSGS 求解：设 m 取根号 p 上取整，令 x=im−j，方程化为 a 的 im 次方等于 b 乘 a 的 j 次方；先枚举 j 把右侧的值存入哈希表作为小步，再枚举 i 计算左侧查表作为大步，时间复杂度为 O(根号 p)。当 a 与 p 不互质时改用扩展 BSGS 处理。

参考资料

• 离散对数 - OI Wiki

简介

求 $a^x\equiv b\pmod p$ 的最小非负整数 $x$ 称为 离散对数 问题。当 $\gcd(a,p)=1$ 时，用 BSGS（Baby-Step Giant-Step，大步小步）求解。

设 $m=\lceil\sqrt p\rceil$，令 $x=im-j$（$0\le i,j<m$），则方程化为 $a^{im}\equiv b\cdot a^{j}\pmod p$。先枚举 $j$ 把 $b\cdot a^j$ 存入哈希表（小步），再枚举 $i$ 计算 $a^{im}$ 查表（大步），时间复杂度 $O(\sqrt p)$。当 $\gcd(a,p)\ne 1$ 时用扩展 BSGS。

例题

洛谷 P3846 【模板】BSGS / [TJOI2007] 可爱的质数

给定质数 $p$ 与整数 $b,n$，求最小的非负整数 $l$，使 $b^l\equiv n\pmod p$；无解则报告。