跳转至

# 离散对数

## 定义

前置知识：阶与原根．

离散对数的定义方式和对数类似．取有原根的正整数模数 𝑚 m，设其一个原根为 𝑔 g. 对满足 (𝑎,𝑚) =1(a,m)=1 的整数 𝑎 a，我们知道必存在唯一的整数 0 ≤𝑘 <𝜑(𝑚)0≤k<φ(m) 使得

𝑔 𝑘≡𝑎(m o d 𝑚)g k≡a(mod m)

我们称这个 𝑘 k 为以 𝑔 g 为底，模 𝑚 m 的离散对数，记作 𝑘 =i n d 𝑔⁡𝑎 k=ind g⁡a，在不引起混淆的情况下可记作 i n d⁡𝑎 ind⁡a.

显然 i n d 𝑔⁡1 =0 ind g⁡1=0，i n d 𝑔⁡𝑔 =1 ind g⁡g=1.

## 性质

离散对数的性质也和对数有诸多类似之处．

性质

设 𝑔 g 是模 𝑚 m 的原根，(𝑎,𝑚) =(𝑏,𝑚) =1(a,m)=(b,m)=1，则：

1. i n d 𝑔⁡(𝑎 𝑏) ≡i n d 𝑔⁡𝑎 +i n d 𝑔⁡𝑏(m o d 𝜑(𝑚))ind g⁡(a b)≡ind g⁡a+ind g⁡b(mod φ(m))

   进而 (∀𝑛 ∈𝐍), i n d 𝑔⁡𝑎 𝑛 ≡𝑛 i n d 𝑔⁡𝑎(m o d 𝜑(𝑚))(∀n∈N), ind g⁡a n≡n ind g⁡a(mod φ(m))

2. 若 𝑔 1 g 1 也是模 𝑚 m 的原根，则 i n d 𝑔⁡𝑎 ≡i n d 𝑔 1⁡𝑎 ⋅i n d 𝑔⁡𝑔 1(m o d 𝜑(𝑚))ind g⁡a≡ind g 1⁡a⋅ind g⁡g 1(mod φ(m))

3. 𝑎 ≡𝑏(m o d 𝑚) ⟺ i n d 𝑔⁡𝑎 =i n d 𝑔⁡𝑏 a≡b(mod m)⟺ind g⁡a=ind g⁡b

证明

1. 𝑔 i n d 𝑔⁡(𝑎 𝑏) ≡𝑎 𝑏 ≡𝑔 i n d 𝑔⁡𝑎 𝑔 i n d 𝑔⁡𝑏 ≡𝑔 i n d 𝑔⁡𝑎+i n d 𝑔⁡𝑏(m o d 𝑚)g ind g⁡(a b)≡a b≡g ind g⁡a g ind g⁡b≡g ind g⁡a+ind g⁡b(mod m)

2. 令 𝑥 =i n d 𝑔 1⁡𝑎 x=ind g 1⁡a，则 𝑎 ≡𝑔 𝑥 1(m o d 𝑚)a≡g 1 x(mod m). 又令 𝑦 =i n d 𝑔⁡𝑔 1 y=ind g⁡g 1，则 𝑔 1 ≡𝑔 𝑦(m o d 𝑚)g 1≡g y(mod m).

   故 𝑎 ≡𝑔 𝑥 𝑦(m o d 𝑚)a≡g x y(mod m)，即 i n d 𝑔⁡𝑎 ≡𝑥 𝑦 ≡i n d 𝑔 1⁡𝑎 ⋅i n d 𝑔⁡𝑔 1(m o d 𝜑(𝑚))ind g⁡a≡x y≡ind g 1⁡a⋅ind g⁡g 1(mod φ(m))

3. 注意到

   i n d 𝑔⁡𝑎=i n d 𝑔⁡𝑏⟺i n d 𝑔⁡𝑎≡i n d 𝑔⁡𝑏(m o d 𝜑(𝑚))⟺𝑔 i n d 𝑔⁡𝑎≡𝑔 i n d 𝑔⁡𝑏(m o d 𝑚)⟺𝑎≡𝑏(m o d 𝑚)ind g⁡a=ind g⁡b⟺ind g⁡a≡ind g⁡b(mod φ(m))⟺g ind g⁡a≡g ind g⁡b(mod m)⟺a≡b(mod m)

## 大步小步算法

目前离散对数问题仍不存在多项式时间经典算法（离散对数问题的输入规模是输入数据的位数）．在密码学中，基于这一点人们设计了许多非对称加密算法，如 Ed25519．

在算法竞赛中，BSGS（baby-step giant-step，大步小步算法）常用于求解离散对数问题．形式化地说，对 𝑎,𝑏,𝑚 ∈𝐙+a,b,m∈Z+，该算法可以在 𝑂(√𝑚)O(m) 的时间内求解

𝑎 𝑥≡𝑏(m o d 𝑚)a x≡b(mod m)

其中 𝑎 ⟂𝑚 a⟂m．方程的解 𝑥 x 满足 0 ≤𝑥 <𝑚 0≤x<m.（注意 𝑚 m 不一定是素数）

### 算法描述

令 𝑥 =𝐴⌈√𝑚⌉ −𝐵 x=A⌈m⌉−B，其中 0 ≤𝐴,𝐵 ≤⌈√𝑚⌉0≤A,B≤⌈m⌉，则有 𝑎 𝐴⌈√𝑚⌉−𝐵 ≡𝑏(m o d 𝑚)a A⌈m⌉−B≡b(mod m)，稍加变换，则有 𝑎 𝐴⌈√𝑚⌉ ≡𝑏 𝑎 𝐵(m o d 𝑚)a A⌈m⌉≡b a B(mod m).

我们已知的是 𝑎,𝑏 a,b，所以我们可以先算出等式右边的 𝑏 𝑎 𝐵 b a B 的所有取值，枚举 𝐵 B，用 `hash`/`map` 存下来，然后逐一计算 𝑎 𝐴⌈√𝑚⌉a A⌈m⌉，枚举 𝐴 A，寻找是否有与之相等的 𝑏 𝑎 𝐵 b a B，从而我们可以得到所有的 𝑥 x，𝑥 =𝐴⌈√𝑚⌉ −𝐵 x=A⌈m⌉−B.

注意到 𝐴,𝐵 A,B 均小于 ⌈√𝑚⌉⌈m⌉，所以时间复杂度为 Θ(√𝑚)Θ(m)，用 `map` 则多一个 l o g log.

为什么要求 𝑎 a 与 𝑚 m 互质

注意到我们求出的是 𝐴,𝐵 A,B，我们需要保证从 𝑎 𝐴⌈√𝑚⌉ ≡𝑏 𝑎 𝐵(m o d 𝑚)a A⌈m⌉≡b a B(mod m) 可以推回 𝑎 𝐴⌈√𝑚⌉−𝐵 ≡𝑏(m o d 𝑚)a A⌈m⌉−B≡b(mod m)，后式是前式左右两边除以 𝑎 𝐵 a B 得到，所以必须有 𝑎 𝐵 ⟂𝑚 a B⟂m 即 𝑎 ⟂𝑚 a⟂m.

## 扩展 BSGS 算法

对 𝑎,𝑏,𝑚 ∈𝐙+a,b,m∈Z+，求解

𝑎 𝑥≡𝑏(m o d 𝑚)a x≡b(mod m)

其中 𝑎,𝑚 a,m 不一定互质．

当 (𝑎,𝑚) =1(a,m)=1 时，在模 𝑚 m 意义下 𝑎 a 存在逆元，因此可以使用 BSGS 算法求解．于是我们想办法让他们变得互质．

具体地，设 𝑑 1 =(𝑎,𝑚)d 1=(a,m). 如果 𝑑 1 ∤𝑏 d 1∤b，则原方程无解．否则我们把方程同时除以 𝑑 1 d 1，得到

𝑎 𝑑 1⋅𝑎 𝑥−1≡𝑏 𝑑 1(m o d 𝑚 𝑑 1)a d 1⋅a x−1≡b d 1(mod m d 1)

如果 𝑎 a 和 𝑚 𝑑 1 m d 1 仍不互质就再除，设 𝑑 2 =(𝑎,𝑚 𝑑 1)d 2=(a,m d 1). 如果 𝑑 2 ∤𝑏 𝑑 1 d 2∤b d 1，则方程无解；否则同时除以 𝑑 2 d 2 得到

𝑎 2 𝑑 1 𝑑 2⋅𝑎 𝑥−2≡𝑏 𝑑 1 𝑑 2(m o d 𝑚 𝑑 1 𝑑 2)a 2 d 1 d 2⋅a x−2≡b d 1 d 2(mod m d 1 d 2)

同理，这样不停的判断下去，直到 𝑎 ⟂𝑚 𝑑 1 𝑑 2⋯𝑑 𝑘 a⟂m d 1 d 2⋯d k.

记 𝐷 =∏𝑘 𝑖=1 𝑑 𝑖 D=∏i=1 k d i，于是方程就变成了这样：

𝑎 𝑘 𝐷⋅𝑎 𝑥−𝑘≡𝑏 𝐷(m o d 𝑚 𝐷)a k D⋅a x−k≡b D(mod m D)

由于 𝑎 ⟂𝑚 𝐷 a⟂m D，于是推出 𝑎 𝑘 𝐷 ⟂𝑚 𝐷 a k D⟂m D. 这样 𝑎 𝑘 𝐷 a k D 就有逆元了，于是把它丢到方程右边，这就是一个普通的 BSGS 问题了，于是求解 𝑥 −𝑘 x−k 后再加上 𝑘 k 就是原方程的解啦．

注意，不排除解小于等于 𝑘 k 的情况，所以在消因子之前做一下 Θ(𝑘)Θ(k) 枚举，直接验证 𝑎 𝑖 ≡𝑏(m o d 𝑚)a i≡b(mod m)，这样就能避免这种情况．

## 习题

- SPOJ MOD 模板
- SDOI2013 随机数生成器
- SGU261 Discrete Roots 模板
- SDOI2011 计算器 模板
- Luogu4195【模板】exBSGS/Spoj3105 Mod 模板
- Codeforces - Lunar New Year and a Recursive Sequence
- LOJ6542 离散对数 index calculus 方法，非模板

本页面部分内容以及代码译自博文 Дискретное извлечение корня 与其英文翻译版 Discrete Root．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

## 参考资料

1. Discrete logarithm - Wikipedia
2. 潘承洞，潘承彪．初等数论．
3. 冯克勤．初等数论及其应用．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, StudyingFather, sshwy, Steaunk, Great-designer, H-J-Granger, Enter-tainer, MegaOwIer, Tiphereth-A, c-forrest, countercurrent-time, Henry-ZHR, Konano, ksyx, NachtgeistW, ouuan, stevebraveman, Xeonacid, Alpha1022, AngelKitty, CCXXXI, Chrogeek, ChungZH, cjsoft, diauweb, Early0v0, ezoixx130, FFjet, GavinZhengOI, GekkaSaori, Gesrua, hly1204, hsfzLZH1, iamtwz, isdanni, Kelatte, kxccc, Lampese, LovelyBuggies, lychees, Makkiy, Marcythm, mgt, minghu6, P-Y-Y, Peanut-Tang, PotassiumWings, purple-vine, SamZhangQingChuan, SukkaW, Suyun514, weiyong1024, xyf007, YOYO-UIAT
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用