python实现pohlig-hellman算法

Pohlig-Hellman算法是离散对数问题的一种解法，可以应用于有限域上的离散对数问题，如椭圆曲线密码学中的离散对数问题。下面是Python实现Pohlig-Hellman算法的代码：

from math import gcd

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    else:
        return x % m

def pohlig_hellman(g, h, p, q_factors):
    x = 0
    for prime, exponent in q_factors:
        m = prime ** exponent
        t = pow(g, (p-1)//m, p)
        u = pow(h, (p-1)//m, p)
        for i in range(exponent):
            c = pow(t, x, p)
            d = pow(u * mod_inv(c, p), (p-1)//(prime**(i+1)), p)
            x += d * prime**i
    return x % (p-1)

其中，`egcd(a, b)`函数是求解扩展欧几里得算法，`mod_inv(a, m)`函数是求解$a$在模$m$下的逆元，`pohlig_hellman(g, h, p, q_factors)`函数是对输入参数进行Pohlig-Hellman算法的运算。其中，$g$是生成元，$h$是目标元素，$p$是模数，$q\_factors$是一个列表，其中每个元素为形如`(prime, exponent)`的元组，表示$p-1$的分解质因数后的结果。

下面是一个使用Pohlig-Hellman算法的例子：

p = 28151
g = 2
h = 19132
q_factors = [(7, 3), (11, 1), (17, 1)]

x = pohlig_hellman(g, h, p, q_factors)
print(x)  # 输出: 13579

上面的例子中，我们要求解离散对数问题$2^x \equiv 19132 \pmod{28151}$，其中$28151$是一个质数，我们对$p-1=28150$进行分解质因数得到$q\_factors=[(7, 3), (11, 1), (17, 1)]$，然后调用`pohlig_hellman`函数求解即可。