数论 - BSGS 算法推导

2017/02/25

写在前面(的废话)

BSGS 的用途是解离散对数,复杂度
主要参考了 hzwerclover_hxy 的文章。

但是貌似 hzwer 的那篇不太容易懂,clover_hxy 的这个坠吼了。

其他的一些补充:离散对数这类问题没有快速解法,所以说可以用来做公钥加密 (ElGamal,特地咨询了 Asterisk)

那么 BSGS 呢?其实也是属于一种密码学攻击手段,叫做 Meet-in-the-middle attack, 属于用空间换时间,最早是针对 DES-3 的。

BSGS 推导


设一个常数 ,令

那么可以通过预处理所有的 存到一个数据结构中 (比如蛤希表),枚举 计算 来求解。

最终答案就是

显然 坠吼

一点问题

所以说 , 如何保证这里面一定有解?

可以证明 用到费马小定理的一个结论

可以看作 ,原式化为

根据费马小定理 (其中 为指数, )得到

总结 BSGS 的一般形式

求解离散对数问题 求最小

得到
预处理所有的 ,枚举 计算
求最小的满足上式的
此时