密码学系列｜2.9 The Pohlig–Hellman Algorithm

  除了作为一个定理和算法，我们还要向读者建议，中国剩余定理也可以作为一种思想。如果  是两两互素数的乘积，那么根据中国剩余定理，解一个模  的同余方程或多或少等同于解一个模  的同余方程组，因为它告诉我们如何把模  的解组合在一起，得到一个模  的解。

  在离散对数问题中，我们需要求解方程  。此时  是一个素数，看起来和中国剩余定理没什么关系。但是，注意到  是在模  下的，这意味  的因子分解将影响 𝕡 下 DLP 的困难度。更一般地说，如果  是任意群  是一个  阶元素，那么  中  的解由  确定，所以  的素因子分解还是有一定作用的。这个想法正是 Pohlig–Hellman 算法的核心。

定理 2.31 (Pohlig–Hellman Algorithm) 设有群 ，假设我们拥有一个算法解决群  中具有素数阶元素的 DLP问题，具体地说，如果  有阶 ，那么我们可以在  步内解出 。（比如在命题 2.21 中我们可以将  替换为  ，见 注 2.32 展开更多讨论。）

  现在我们假设  为阶为  的元素， 可以分解为 ，那么离散对数问题 可以解决于

1. 对于 ，设 。注意到  有阶 ，使用已知算法解决  ，设解为 
2. 使用中国剩余定理求出满足下列同余式组的解 ：

• 证明：首先运行时间没什么问题，因为步骤（1）需要  步，而步骤（2）通过中国剩余定理需要 步。在实际运算中，与离散对数的计算相比，中国剩余定理所需要的计算开销其实可以忽略不计。那么接下来我们需要证明步骤 1，2 给出的确实是  的解。我们设  是上式的解，那么对于每个  ，我们有

  那么 

  两边取一个对数有 ，这里注意到我们的模数是 ，因为  就是原来群的单位元了。

  接下来我们看到 ，显然他们是除了 1 没有其他公因子。那么根据拓展欧几里得算法（定理 1.11）我们能够找到 ，使得

  现在我们在式子  两边分别乘上  并求和，得到

  根据  的定义，所以我们有 ，因此  满足 ，证毕。

注 2.32 Pohlig–Hellman算法或多或少地将任意阶元素的离散对数问题简化为有素数幂次阶元素的离散对数问题。我们将在本节后面的讨论中进一步细化，实质上将问题简化为素数阶元素。更准确地说，在定理2.31的表示法中，运算时间可以由   转化为  

  因此，Pohlig–Hellman算法告诉我们，如果群  的阶是小素数幂的乘积，则群  中的离散对数问题是不安全的。更一般地说，如果元素  的阶是小素数幂的乘积，则  很容易求解。这尤其适用于𝕡 中（如果  可以分解为小素数的幂）的离散对数问题。因为  总是偶数，我们能做的最好的事情就是取素数  以及素数 ，并使用阶为  的元素 。那么 命题2.21 中描述的碰撞算法的运行时间是。但是，在第3.8节中描述的指数演算方法的运行时间是次指数的，所以即使 ，素数  也必须选择得相对大。我们现在解释将素数幂次元素的离散对数问题简化为素数阶元素的离散对数问题的算法。想法很简单：如果  有阶，那么的阶是。诀窍是重复这个过程几次，然后将信息组合成最终答案。

命题 2.33 设由群 ，素数 ，并假设我们知道一个算法能够在  步内解出离散对数问题 ， 有素数阶 ，那么设  为拥有阶  的元素。那么我们可以在 内解决  。

• 证明：证明这个命题的关键思想是把未知指数  写成 ，然后依次确定 ，首先我们注意到  有阶 ，所以我们可以计算

（因为 ）

  因为  是群  中具有阶  的元素，所以等式  是一个底的阶为  的离散对数问题。那么根据假设我们能在  步内解决，然后我们就能够知道 ，满足 。接着我们回到原式，这次两边升个  幂次，

  此时我们知道 ，然后  的阶为 ，所以计算 ，即解决离散对数问题

  根据假设我们能够在 内计算出 ，所以在  步内，我们能够计算出  满足

  同理我们能够通过解决离散对数问题

  计算出 

  最终，在我们计算出 ，那么  则通过解决离散对数问题

  上述每个离散对数问题的底都是具有阶  的元素，所以都可以在  步内被解决。因此在  步内我们可以计算出  ，满足 。即完成了原始离散对数问题的求解。

注 3.34 由命题 2.21我们有  ，所以根据命题2.23，意味着我们可以在 解决离散对数问题。注意到如果我们直接对上述问题应用命题 2.21，那么运行时间就要来到 ，当 ，这个值就很大了。

例 2.35 我们再通过一个例子来阐述 命题 2.33 的算法流程。我们需要计算

  素数  由性质： 被  整除，并且可以计算  有阶 ，所以第一步，我们需要计算

  即 ，这个很简单，，下一步，

  即 ，注意到这里我们只需要遍历一下 就可以了，但如果  比较大，那就需要用到命题 2.21 的算法（BSGS） 了（或更快的算法）。不管哪种算法，这里我们能算出 ，所以现在 

  继续

  即 ，因此 ，所以仍然 。

  最后一步，我们计算

  即 ，解得 ，所以 

  可以验证 

  定理 2.31中说到 Pohlig–Hellman algorithm 最后有用到中国剩余定理解决离散对数。那么下面的例子将阐述完整版本的Pohlig–Hellman algorithm。

例 2.36 求解 

  底  是𝟙𝟙𝟚𝟝𝟙 下的一个原根，即其有阶 ，因为 ，是小素数的乘积，所以比较适合 Pohlig–Hellman algorithm。根据定理 2.31，我们设

  那么第一步我们需要解决三个子离散对数问题，结果见下表

  注意到，第一个子问题没啥意义，第三个问题就是我们的例 2.35的解。但无论如果，这三个子问题都可以根据命题 2.33 进行求解。

  第二步就是用中国剩余定理解决同余式方程组

  解得最小得值为 

  经检查，确实满足 

附录

Pohlig–Hellman algorithm Sagemath代码示例

def bsgs(alpha, beta, modulus, upper_bound=None):
    if not upper_bound:
        upper_bound = Mod(alpha, modulus).multiplicative_order()
    m = ceil(sqrt(upper_bound))
    S = {pow(alpha, j, modulus):j for j in range(m + 1)}
    gs = Mod(alpha, modulus)^(-m)
    for i in range(m + 1):
        if beta in S:
            return (i * m + S[beta])
        beta = (beta * gs) % modulus
    return None

def pohlig_hellman(beta, alpha, N):
    beta, alpha = Mod(beta, N), Mod(alpha, N)
    ord = 787354636631
    f = ord.factor()
    prime_order_mod = [0] * len(f)
    for i, (p, r) in enumerate(f):
        for j in range(r):
            pmod = bsgs(alpha^(ord // p), (beta / alpha^prime_order_mod[i])^(ord // p^(j+1)), N, p - 1)
            prime_order_mod[i] += pmod * (p**j)
    return crt(prime_order_mod, [p**r for (p, r) in f])


# g^x = h mod p
x = pohlig_hellman(h,g,p)