Pohlig-Hellman算法python

Pohlig-Hellman算法的实现需要用到模重复平方法和中国剩余定理，以下是一个用Python实现Pohlig-Hellman算法的示例代码：

from math import sqrt
from sympy import primefactors

def mod_pow(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

def mod_inv(number, modulus):
    x, y = 0, 1
    a, b = modulus, number
    while b != 0:
        x, y = y, x - (a // b) * y
        a, b = b, a % b
    return x % modulus

def pohlig_hellman(g, h, p):
    factors = primefactors(p - 1)
    x = 0
    for factor in factors:
        q = factor
        e = (p - 1) // q
        # calculate g^e mod p
        ge = mod_pow(g, e, p)
        # calculate h^(p-1)/q mod p
        hq = mod_pow(h, (p - 1) // q, p)
        # calculate (g^e)^x mod p
        for i in range(q):
            if mod_pow(ge, i, p) == hq:
                x = x + i * (p - 1) // q * mod_inv(e, q)
                break
    return x % (p - 1)

# example usage
g = 2
h = 1024
p = 65537
x = pohlig_hellman(g, h, p)
print(x)

在这个示例中，首先使用`primefactors`函数计算出模数`p-1`的因数分解，然后对于每个因子`q`，计算出`g^e mod p`和`h^(p-1)/q mod p`，并使用模重复平方法找到一个`x`，满足`(g^e)^x mod p = h^(p-1)/q mod p`。最后，使用中国剩余定理将`x`合并为一个结果。