技能离散对数

技能离散对数 $^{[1]}$

若无特殊说明，模数 $m$ 是质数，$g$ 是一个原根，$\log$ 默认以 $g$ 为底。$p$ 是质数。

传统😯的离散对数🧮，就是 $^{[1]}$

先用 BSGS $^{[2]}$ 预处理出 $\sqrt m + 1$ 以内质数的离散对数，时间复杂度 $\Theta(\dfrac {m^{0.75}} {\log m})$，然后根据 $\log ab = \log a + \log b$ 计算出 $\sqrt m + 1$ 以内所有数的离散对数。查询时，对于 $x<\sqrt m$，可以直接查表。对于 $x>\sqrt m$，令 $y=\lfloor \dfrac m x \rfloor, z_1 = m-xy, z_2 = x(y+1)-m$，由于 $z_1+z_2=x$，较小值必不超过 $\dfrac x 2$。以 $z_1$ 为例，对 $m$ 取模，有 $z_1\equiv -xy \pmod m$，两侧取对数得到 $\log z_1 \equiv \log x + \log y + \log (-1) \pmod {m-1}$。移项可得 $\log x \equiv \log z_1 - \log y - \log (-1) \pmod {m-1}$，于是递归计算 $\log z_1$。在 $\log_2 m$ 轮以内，$x$ 将减少至 $\sqrt m$ 以下，查询复杂度为 $q\log m$。

好无聊😩，好无趣😫。$^{[1]}$

由于 BSGS 固有的 $\sqrt m$ 复杂度，该做法难以在算法竞赛常见时间内处理 $10^{18}$ 左右的模数。

而技能离散对数🤓☝，就是在传统的离散对数🧐加入 $^{[1]}$

Index Calculus 算法 $^{[3]}$，其核心思想是通过随机 $1\le k\le m-1$，并分解 $g^k\bmod m$，得到关于 $\log_g p_i$ 的线性方程。然后通过解线性方程直接得到离散对数，绕开 BSGS 过程。

具体而言，$g^k\bmod m$ 可以认为是 $m$ 以内的随机数。若希望建立 $B$ 以内质数的线性方程组，则随机 $k$ 可以得到线性方程当且仅当 $g^k\bmod m$ 是 $B\ -$ 光滑数（所有质因子不超过 $B$）。令 $u=\log_B m$，则 $\rho \approx u^{-u}$ $^{[4]}$，通过选取合适的 $B$ 可以平衡到一个不错的复杂度。在 $10^{18}$ 左右的模数下，可以选取 $B=1000$。

好好玩🥰🥰🥰，要爆了💥💥💥$^{[1]}$

将上述两个做法结合起来，再加入一点神秘小巧思。在随机出 $x=g^k\bmod m$ 后，不立即将它分解。选取合适的 $B_2=10^7$，预处理出 $B_2$ 以内哪些数是 $B\ -$ 光滑数。执行类似基于值域预处理的快速离散对数中的过程。若 $y,y+1$ 中有至少一个是 $B_2$ 以内的 $B\ -$ 光滑数，则可将 $x$ 减小。若二者都是，贪心地选择较小的 $z$。若都不是，结束这一过程。限定这一过程最多进行 $32$ 轮。

然后通过试除检验 $x$ 的 $B\ -$ 光滑性。若是，则得到一组关于 $B$ 以内质数离散对数的线性方程。随机很多轮，直到线性方程组有唯一解。根据光滑数密度近似公式可以看出，将 $x$ 减小这一操作可以提高其是 $B\ -$ 光滑数的概率，进而减少随机轮数，降低光滑性检验代价。

维护一个对数表，初始包含 $B_2$ 以内的所有 $B\ -$ 光滑数。

接下来，再随机 $7\times 10^5$ 轮。在每一轮中，允许使用对数表里的任何数作为 $y/y+1$ 减小 $x$。无法继续减小时，试除以剔除 $x$ 在 $B$ 以内的质因子。若剩余的 $x$ 是一个 $B_2$ 以内的质数，则求出了其离散对数。若其不在表中，试图将其和其倍数插入对数表。这一部分的均摊复杂度为 $B_2\ln B_2$。

查询一个数 $t$ 时，随机 $k$ 并计算 $t\gets tg^k\bmod m$。使用对数表内的数减小 $t$。若得到的 $t$ 剔除小于 $B$ 的质因子后在对数表内，就可以得到答案。