当我们计算有限域下高次根式的求解时，AMM（Adleman-Manders-Miller）算法就派上了用场。AMM 算法是一种高效的算法，可以在多项式时间内求解有限域下的高次根式问题，这在密码学中有着重要的应用，比如在 RSA 加密算法中求解模 $n$ 下的 $e$ 次根式问题。

欢迎来到《密码学核心算法实战》的 AMM 算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

AMM 算法 🌟

AMM 算法是密码学中专门用于在有限域 $\mathbb{F}_p$ 下求解高次根式的算法。给定一个质数 $p$，一个整数 $a$ 和一个正整数 $e$，我们想要找到一个整数 $x$，使得 $x^k \equiv a \mod p$。

要解之前，首先要先验满足条件：

  • $a \equiv 0 \mod p$，此时 $x = 0$ 是一个解。
  • $a \not \equiv 0 \mod p$，要先验证解是否存在：

AMM 算法的原理 😵

首先设 $d = \gcd(k,p-1)$，先验证解的存在，过程就是上面的条件验证。

找到 $p$ 的一个原根 $g$，将 $a$ 表示为原根的幂（这一步本质是离散对数问题，小素数可暴力找，大素数需结合 BSGS）：

同时也设 $x = g^X \mod p$，将求解的方程转化为：

这里我们会注意到，由一开始的验证条件可以推导：

由于 $g$ 是原根，所以阶为 $p-1$ ，因此：

所以，只有当 $d|m$ 时，才存在解。对方程 $kX \equiv m \mod p-1$ 进行消去律约分，得到：

由于 $\gcd(\frac{k}{d}, \frac{p-1}{d}) = 1$，所以 $\frac{k}{d}$ 的逆元 $t$ 在模 $\frac{p-1}{d}$ 下存在，所以得到：

结合扩展欧几里得算法求 $t$，简单推一下式子：

最终推导出 $x$ 的解为：

AMM 算法的实现 🙃

下面是 AMM 算法的一个简单实现：

from sage.all import *

def amm_solve(k, a, p):
    """
    求解 x^k = a (mod p) 
    """
    # 1. 如果 a = 0 mod p，直接返回解 0
    if a % p == 0:
        return [0]

    d = gcd(k, p - 1)

    # 2. 验证解是否存在: a^((p-1)/d) == 1 (mod p)
    if power_mod(a, (p - 1) // d, p) != 1:
        return [] # 无解

    # 3. 找到 p 的一个原根 g
    g = primitive_root(p)

    # 4. 求解离散对数: a = g^m (mod p)
    m = discrete_log(mod(a, p), mod(g, p))

    # 5. 验证 d | m，只有这个时候才有解 (根据推导理论上一定成立)
    if m % d != 0:
        return []

    # 6. 求解方程的降次转化: k*X = m mod (p-1)
    # 两边同除以 d 得到: (k/d)*X = (m/d) mod ((p-1)/d)
    k_prime = k // d
    m_prime = m // d
    p_prime = (p - 1) // d

    # 7. 计算 t, 即 (k/d) 在模 (p-1)/d 下的逆元
    t = inverse_mod(k_prime, p_prime)

    # 8. 得到一个特解 X0
    X0 = (t * m_prime) % p_prime

    solutions = []
    # 9. 遍历找全所有可能的分支解（因为模数被除了 d，所以在原模 p-1 下有 d 个解）
    for i in range(d):
        X = X0 + i * p_prime
        x = power_mod(g, X, p)
        solutions.append(x)

    return sorted(list(set(solutions)))

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import * # sage环境中才生效
def amm_solve(k, a, p):
    """
    求解 x^k = a (mod p) 
    """
    # 在 SageMath 中，可以直接使用 nth_root 方法来求高次剩余，它内部实现了高效的算法（如 Tonelli-Shanks / AMM 扩展等）
    try:
        roots = mod(a, p).nth_root(k, all=True)
        return sorted([int(r) for r in roots])
    except ValueError:
        return [] # 无解

怎么样，是不是非常简单？🤣👉🤡

上一章：密码学算法 - BSGS算法二 👈
下一章：
回到开始：关于我 👈

相关链接：
密码学数学基础 - 群论基础 👈
密码学算法 - 欧几里得算法 👈
密码学算法 - BSGS一 算法 👈