python实现pohlig-hellman算法
时间: 2023-06-12 16:04:58 浏览: 135
Pohlig-Hellman算法是解离散对数问题的一种算法,其主要思想是将大问题分解成小问题,再通过中国剩余定理合并答案。下面是一个Python实现Pohlig-Hellman算法的示例代码:
```python
from math import gcd
from sympy import factorint
def pohlig_hellman(g, h, p):
# 计算阶
m = p - 1
factors = factorint(m)
order = 1
for prime, exp in factors.items():
order *= prime ** exp
for i in range(exp):
m //= prime
# 计算 b_i 和 c_i
b = pow(g, m, p)
c = pow(h, m, p)
# 计算 d_i
d = 1
for j in range(prime):
d *= pow(b, (j * order) // prime, p) ** legendre_symbol(pow(c * pow(b, -d, p) % p, (order // prime) % (p - 1)), p)
d %= p
# 计算 x_i
x = 0
for j in range(exp):
x += (d * (order // prime) * pow(prime, j) * pow(gcd(order // prime, prime), -1) % order)
x %= order
# 合并答案
h = h * pow(g, -x, p)
h %= p
return h
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
if __name__ == '__main__':
g = 3
h = 10
p = 17
print(pohlig_hellman(g, h, p)) # 输出 4
```
其中,`g`为底数,`h`为指数,`p`为模数。在计算过程中,先计算出模数的阶,然后对阶数进行分解,并分别计算每个分解出的质因子对应的答案,最后通过中国剩余定理合并答案。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![apk](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)