离散对数
定义
前置知识:阶与原根。
离散对数的定义方式和对数类似。取有原根的正整数模数 𝑚
,设其一个原根为 𝑔
. 对满足 (𝑎,𝑚) =1
的整数 𝑎
,我们知道必存在唯一的整数 0 ≤𝑘 <𝜑(𝑚)
使得
𝑔𝑘≡𝑎(mod𝑚)
我们称这个 𝑘
为以 𝑔
为底,模 𝑚
的离散对数,记作 𝑘 =ind𝑔𝑎
,在不引起混淆的情况下可记作 ind𝑎
.
显然 ind𝑔1 =0
,ind𝑔𝑔 =1
.
性质
离散对数的性质也和对数有诸多类似之处。
性质
设 𝑔
是模 𝑚
的原根,(𝑎,𝑚) =(𝑏,𝑚) =1
,则:
-
ind𝑔(𝑎𝑏) ≡ind𝑔𝑎 +ind𝑔𝑏(mod𝜑(𝑚))
进而 (∀𝑛 ∈𝐍), ind𝑔𝑎𝑛 ≡𝑛ind𝑔𝑎(mod𝜑(𝑚))
-
若 𝑔1
也是模 𝑚
的原根,则 ind𝑔𝑎 ≡ind𝑔1𝑎 ⋅ind𝑔𝑔1(mod𝜑(𝑚))
- 𝑎 ≡𝑏(mod𝑚) ⟺ ind𝑔𝑎 =ind𝑔𝑏

证明
- 𝑔ind𝑔(𝑎𝑏) ≡𝑎𝑏 ≡𝑔ind𝑔𝑎𝑔ind𝑔𝑏 ≡𝑔ind𝑔𝑎+ind𝑔𝑏(mod𝑚)

-
令 𝑥 =ind𝑔1𝑎
,则 𝑎 ≡𝑔𝑥1(mod𝑚)
. 又令 𝑦 =ind𝑔𝑔1
,则 𝑔1 ≡𝑔𝑦(mod𝑚)
.
故 𝑎 ≡𝑔𝑥𝑦(mod𝑚)
,即 ind𝑔𝑎 ≡𝑥𝑦 ≡ind𝑔1𝑎 ⋅ind𝑔𝑔1(mod𝜑(𝑚))
-
注意到
ind𝑔𝑎=ind𝑔𝑏⟺ind𝑔𝑎≡ind𝑔𝑏(mod𝜑(𝑚))⟺𝑔ind𝑔𝑎≡𝑔ind𝑔𝑏(mod𝑚)⟺𝑎≡𝑏(mod𝑚)
大步小步算法
目前离散对数问题仍不存在多项式时间经典算法(离散对数问题的输入规模是输入数据的位数)。在密码学中,基于这一点人们设计了许多非对称加密算法,如 Ed25519。
在算法竞赛中,BSGS(baby-step giant-step,大步小步算法)常用于求解离散对数问题。形式化地说,对 𝑎,𝑏,𝑚 ∈𝐙+
,该算法可以在 𝑂(√𝑚)
的时间内求解
𝑎𝑥≡𝑏(mod𝑚)
其中 𝑎⟂𝑚
。方程的解 𝑥
满足 0 ≤𝑥 <𝑚
.(注意 𝑚
不一定是素数)
算法描述
令 𝑥 =𝐴⌈√𝑚⌉ −𝐵
,其中 0 ≤𝐴,𝐵 ≤⌈√𝑚⌉
,则有 𝑎𝐴⌈√𝑚⌉−𝐵 ≡𝑏(mod𝑚)
,稍加变换,则有 𝑎𝐴⌈√𝑚⌉ ≡𝑏𝑎𝐵(mod𝑚)
.
我们已知的是 𝑎,𝑏
,所以我们可以先算出等式右边的 𝑏𝑎𝐵
的所有取值,枚举 𝐵
,用 hash
/map
存下来,然后逐一计算 𝑎𝐴⌈√𝑚⌉
,枚举 𝐴
,寻找是否有与之相等的 𝑏𝑎𝐵
,从而我们可以得到所有的 𝑥
,𝑥 =𝐴⌈√𝑚⌉ −𝐵
.
注意到 𝐴,𝐵
均小于 ⌈√𝑚⌉
,所以时间复杂度为 Θ(√𝑚)
,用 map
则多一个 log
.
为什么要求 𝑎
与 𝑚
互质
注意到我们求出的是 𝐴,𝐵
,我们需要保证从 𝑎𝐴⌈√𝑚⌉ ≡𝑏𝑎𝐵(mod𝑚)
可以推回 𝑎𝐴⌈√𝑚⌉−𝐵 ≡𝑏(mod𝑚)
,后式是前式左右两边除以 𝑎𝐵
得到,所以必须有 𝑎𝐵⟂𝑚
即 𝑎⟂𝑚
.
进阶篇
对 𝑎,𝑏 ∈𝐙+
,𝑝 ∈𝐏
,求解
𝑥𝑎≡𝑏(mod𝑝)
该问题可以转化为 BSGS 求解的问题。
由于式子中的模数 𝑝
是一个质数,那么 𝑝
一定存在一个原根 𝑔
. 因此对于模 𝑝
意义下的任意的数 $x~(1\le x
本页面最近更新:2024/10/9 22:38:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Ir1d, StudyingFather, sshwy, Steaunk, Great-designer, H-J-Granger, Enter-tainer, MegaOwIer, countercurrent-time, Henry-ZHR, Konano, ksyx, NachtgeistW, ouuan, stevebraveman, Tiphereth-A, 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 协议之条款下提供,附加条款亦可能应用