技能离散对数

lovelyseele · 2026-10-09 13:37:13 · 算法·理论

技能离散对数 ^{[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 的质因子后在对数表内，就可以得到答案。

Upd 2026/8/20 22:30：插入 i 时若 ij 已记录而 j 未记录，推得 j。同时允许将合数插入对数表。这可以带来微乎其微的常数优（存疑）化。

技能离散对数，飞沙走石🌪️^{[1]}

这个做法实测跑得比较优秀，可以在 1.5 秒内预处理一个模数并查询 2^{17} 个离散对数。

技能离散对数，力拔山兮💪🏻^{[1]}

https://qoj.ac/submission/2300547

技能离散对数，飞沙走石🌪️^{[1]}

这个做法实测跑得比较优秀，可以在 1.5 秒内预处理一个模数并查询 2^{17} 个离散对数。

技能离散对数，时光倒流⏰^{[1]}

对不起，我暂时没有找到运行技能离散对数算法可能导致时光倒流的依据。要不要我为你整理离散对数在密码学中的常规应用或相关时间悖论的科普信息？

参考文献