- 算法
- Python实现
在讲之前，首先说明什么是离散对数。离散对数就是给定的一个方程：
a
x
≡
b
(
m
o
d
m
)
a^xequiv b;(mod;m)
ax≡b(modm)
方程中a和b以及m都是已知数，a和m互质，求未知数x，这个x就是离散对数。求离散对数使用的算法叫做小步大步算法，英文为Baby-step giant-step algorithm，是Shanks于1971年提出的一种中路相逢算法meet-in-the-middle algorithm。
该算法就是将方程中的x写成
x
=
n
p
−
q
x=np-q
x=np−q的形式，其中p就是大步giant step，而q就是小步baby step。
既然把x写成
x
=
n
p
−
q
x=np-q
x=np−q，那么方程就变成了：
a
n
p
−
q
≡
b
(
m
o
d
m
)
a^{np-q}equiv b;(mod;m)
anp−q≡b(modm)
把
a
−
q
a^{-q}
a−q移动到等式右边，就变成了：
a
n
p
≡
b
a
q
(
m
o
d
m
)
a^{np}equiv ba^q;(mod;m)
anp≡baq(modm)
p的范围取值范围是
[
1
,
⌈
m
n
⌉
]
[1,lceilfrac{m}{n}rceil]
[1,⌈nm⌉]，而q的取值范围就是
[
0
,
n
]
[0,n]
[0,n]。在p和q在各自取值范围内不断求值，然后遍历匹配，然后匹配到了就可以返回了。对于模幂运算，完全可以使用蒙哥马利乘法，而匹配的话，我直接使用python自带的字典进行。
我直接引用了我之前的蒙哥马利乘法模块。
# _*_ coding:utf-8 _*_
import math
import montgomery
def resolve(a, b, m):
a = a % m
b = b % m
n = round(math.sqrt(m)) + 1
giants = {}
for p in range(1, n + 1):
giants[montgomery.Montgomery.power(a, p * n, m)] = p
for q in range(0, n + 1):
baby = b * montgomery.Montgomery.power(a, q, m) % m
if baby in giants:
return giants[baby] * n - q
raise RuntimeError('无解')
if __name__ == '__main__':
a, x, m = 9, 99, 7
b = montgomery.Montgomery.power(a, x, m)
x2 = resolve(a, b, m)
print(x2, montgomery.Montgomery.power(a, x2, m), b)
