当我们计算有限域下高次根式的求解时AMMAdleman-Manders-Miller算法就派上了用场。AMM 算法是一种高效的算法可以在多项式时间内求解有限域下的高次根式问题这在密码学中有着重要的应用比如在 RSA 加密算法中求解模n nn下的e ee次根式问题。欢迎来到《密码学核心算法实战》的 AMM 算法专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。AMM 算法 AMM 算法是密码学中专门用于在有限域F p \mathbb{F}_pFp下求解高次根式的算法。给定一个质数p pp一个整数a aa和一个正整数e ee我们想要找到一个整数x xx使得x k ≡ a m o d p x^k \equiv a \mod pxk≡amodp。要解之前首先要先验满足条件a ≡ 0 m o d p a \equiv 0 \mod pa≡0modp此时x 0 x 0x0是一个解。a ≢ 0 m o d p a \not \equiv 0 \mod pa≡0modp要先验证解是否存在a p − 1 gcd ( e , p − 1 ) ≡ 1 m o d p a^{\frac{p-1}{\gcd(e, p-1)}} \equiv 1 \mod pagcd(e,p−1)p−1≡1modpAMM 算法的原理 首先设d gcd ( k , p − 1 ) d \gcd(k,p-1)dgcd(k,p−1)先验证解的存在过程就是上面的条件验证。找到p pp的一个原根g gg将a aa表示为原根的幂这一步本质是离散对数问题小素数可暴力找大素数需结合 BSGSa g m m o d p a g^m \mod pagmmodp同时也设x g X m o d p x g^X \mod pxgXmodp将求解的方程转化为g k X ≡ g m m o d p ⇒ k X ≡ m m o d p − 1 g^{kX} \equiv g^m \mod p \Rightarrow kX \equiv m \mod p-1gkX≡gmmodp⇒kX≡mmodp−1这里我们会注意到由一开始的验证条件可以推导a p − 1 gcd ( k , p − 1 ) ≡ g m ⋅ p − 1 gcd ( k , p − 1 ) ≡ 1 m o d p a^{\frac{p-1}{\gcd(k, p-1)}} \equiv g^{m \cdot \frac{p-1}{\gcd(k, p-1)}} \equiv 1 \mod pagcd(k,p−1)p−1≡gm⋅gcd(k,p−1)p−1≡1modp由于g gg是原根所以阶为p − 1 p-1p−1因此m ⋅ p − 1 gcd ( k , p − 1 ) ≡ 0 m o d p − 1 ⟺ m gcd ( k , p − 1 ) ∈ Z m \cdot \frac{p-1}{\gcd(k, p-1)} \equiv 0 \mod p-1 \Longleftrightarrow \frac{m}{\gcd(k, p-1)} \in \mathbb{Z}m⋅gcd(k,p−1)p−1≡0modp−1⟺gcd(k,p−1)m∈Z所以只有当d ∣ m d|md∣m时才存在解。对方程k X ≡ m m o d p − 1 kX \equiv m \mod p-1kX≡mmodp−1进行消去律约分得到k d ⋅ X ≡ m d m o d p − 1 d \frac{k}{d} \cdot X \equiv \frac{m}{d} \mod \frac{p-1}{d}dk⋅X≡dmmoddp−1由于gcd ( k d , p − 1 d ) 1 \gcd(\frac{k}{d}, \frac{p-1}{d}) 1gcd(dk,dp−1)1所以k d \frac{k}{d}dk的逆元t tt在模p − 1 d \frac{p-1}{d}dp−1下存在所以得到k ⋅ t ≡ d m o d p − 1 k \cdot t \equiv d \mod p-1k⋅t≡dmodp−1结合扩展欧几里得算法求t tt简单推一下式子k t X ≡ m t m o d p − 1 ⟺ X ≡ t m d − 1 m o d p − 1 k t X \equiv mt \mod p-1 \Longleftrightarrow X \equiv t m d^{-1} \mod p-1ktX≡mtmodp−1⟺X≡tmd−1modp−1最终推导出x xx的解为x ≡ g t m d − 1 m o d p x \equiv g^{t m d^{-1}} \mod px≡gtmd−1modpAMM 算法的实现 下面是 AMM 算法的一个简单实现fromsage.allimport*defamm_solve(k,a,p): 求解 x^k a (mod p) # 1. 如果 a 0 mod p直接返回解 0ifa%p0:return[0]dgcd(k,p-1)# 2. 验证解是否存在: a^((p-1)/d) 1 (mod p)ifpower_mod(a,(p-1)//d,p)!1:return[]# 无解# 3. 找到 p 的一个原根 ggprimitive_root(p)# 4. 求解离散对数: a g^m (mod p)mdiscrete_log(mod(a,p),mod(g,p))# 5. 验证 d | m只有这个时候才有解 (根据推导理论上一定成立)ifm%d!0:return[]# 6. 求解方程的降次转化: k*X m mod (p-1)# 两边同除以 d 得到: (k/d)*X (m/d) mod ((p-1)/d)k_primek//d m_primem//d p_prime(p-1)//d# 7. 计算 t, 即 (k/d) 在模 (p-1)/d 下的逆元tinverse_mod(k_prime,p_prime)# 8. 得到一个特解 X0X0(t*m_prime)%p_prime solutions[]# 9. 遍历找全所有可能的分支解因为模数被除了 d所以在原模 p-1 下有 d 个解foriinrange(d):XX0i*p_prime xpower_mod(g,X,p)solutions.append(x)returnsorted(list(set(solutions)))SageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimport*# sage环境中才生效defamm_solve(k,a,p): 求解 x^k a (mod p) # 在 SageMath 中可以直接使用 nth_root 方法来求高次剩余它内部实现了高效的算法如 Tonelli-Shanks / AMM 扩展等try:rootsmod(a,p).nth_root(k,allTrue)returnsorted([int(r)forrinroots])exceptValueError:return[]# 无解怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋
密码学算法 - AMM 算法
发布时间：2026/7/5 0:16:09
当我们计算有限域下高次根式的求解时AMMAdleman-Manders-Miller算法就派上了用场。AMM 算法是一种高效的算法可以在多项式时间内求解有限域下的高次根式问题这在密码学中有着重要的应用比如在 RSA 加密算法中求解模n nn下的e ee次根式问题。欢迎来到《密码学核心算法实战》的 AMM 算法专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。AMM 算法 AMM 算法是密码学中专门用于在有限域F p \mathbb{F}_pFp下求解高次根式的算法。给定一个质数p pp一个整数a aa和一个正整数e ee我们想要找到一个整数x xx使得x k ≡ a m o d p x^k \equiv a \mod pxk≡amodp。要解之前首先要先验满足条件a ≡ 0 m o d p a \equiv 0 \mod pa≡0modp此时x 0 x 0x0是一个解。a ≢ 0 m o d p a \not \equiv 0 \mod pa≡0modp要先验证解是否存在a p − 1 gcd ( e , p − 1 ) ≡ 1 m o d p a^{\frac{p-1}{\gcd(e, p-1)}} \equiv 1 \mod pagcd(e,p−1)p−1≡1modpAMM 算法的原理 首先设d gcd ( k , p − 1 ) d \gcd(k,p-1)dgcd(k,p−1)先验证解的存在过程就是上面的条件验证。找到p pp的一个原根g gg将a aa表示为原根的幂这一步本质是离散对数问题小素数可暴力找大素数需结合 BSGSa g m m o d p a g^m \mod pagmmodp同时也设x g X m o d p x g^X \mod pxgXmodp将求解的方程转化为g k X ≡ g m m o d p ⇒ k X ≡ m m o d p − 1 g^{kX} \equiv g^m \mod p \Rightarrow kX \equiv m \mod p-1gkX≡gmmodp⇒kX≡mmodp−1这里我们会注意到由一开始的验证条件可以推导a p − 1 gcd ( k , p − 1 ) ≡ g m ⋅ p − 1 gcd ( k , p − 1 ) ≡ 1 m o d p a^{\frac{p-1}{\gcd(k, p-1)}} \equiv g^{m \cdot \frac{p-1}{\gcd(k, p-1)}} \equiv 1 \mod pagcd(k,p−1)p−1≡gm⋅gcd(k,p−1)p−1≡1modp由于g gg是原根所以阶为p − 1 p-1p−1因此m ⋅ p − 1 gcd ( k , p − 1 ) ≡ 0 m o d p − 1 ⟺ m gcd ( k , p − 1 ) ∈ Z m \cdot \frac{p-1}{\gcd(k, p-1)} \equiv 0 \mod p-1 \Longleftrightarrow \frac{m}{\gcd(k, p-1)} \in \mathbb{Z}m⋅gcd(k,p−1)p−1≡0modp−1⟺gcd(k,p−1)m∈Z所以只有当d ∣ m d|md∣m时才存在解。对方程k X ≡ m m o d p − 1 kX \equiv m \mod p-1kX≡mmodp−1进行消去律约分得到k d ⋅ X ≡ m d m o d p − 1 d \frac{k}{d} \cdot X \equiv \frac{m}{d} \mod \frac{p-1}{d}dk⋅X≡dmmoddp−1由于gcd ( k d , p − 1 d ) 1 \gcd(\frac{k}{d}, \frac{p-1}{d}) 1gcd(dk,dp−1)1所以k d \frac{k}{d}dk的逆元t tt在模p − 1 d \frac{p-1}{d}dp−1下存在所以得到k ⋅ t ≡ d m o d p − 1 k \cdot t \equiv d \mod p-1k⋅t≡dmodp−1结合扩展欧几里得算法求t tt简单推一下式子k t X ≡ m t m o d p − 1 ⟺ X ≡ t m d − 1 m o d p − 1 k t X \equiv mt \mod p-1 \Longleftrightarrow X \equiv t m d^{-1} \mod p-1ktX≡mtmodp−1⟺X≡tmd−1modp−1最终推导出x xx的解为x ≡ g t m d − 1 m o d p x \equiv g^{t m d^{-1}} \mod px≡gtmd−1modpAMM 算法的实现 下面是 AMM 算法的一个简单实现fromsage.allimport*defamm_solve(k,a,p): 求解 x^k a (mod p) # 1. 如果 a 0 mod p直接返回解 0ifa%p0:return[0]dgcd(k,p-1)# 2. 验证解是否存在: a^((p-1)/d) 1 (mod p)ifpower_mod(a,(p-1)//d,p)!1:return[]# 无解# 3. 找到 p 的一个原根 ggprimitive_root(p)# 4. 求解离散对数: a g^m (mod p)mdiscrete_log(mod(a,p),mod(g,p))# 5. 验证 d | m只有这个时候才有解 (根据推导理论上一定成立)ifm%d!0:return[]# 6. 求解方程的降次转化: k*X m mod (p-1)# 两边同除以 d 得到: (k/d)*X (m/d) mod ((p-1)/d)k_primek//d m_primem//d p_prime(p-1)//d# 7. 计算 t, 即 (k/d) 在模 (p-1)/d 下的逆元tinverse_mod(k_prime,p_prime)# 8. 得到一个特解 X0X0(t*m_prime)%p_prime solutions[]# 9. 遍历找全所有可能的分支解因为模数被除了 d所以在原模 p-1 下有 d 个解foriinrange(d):XX0i*p_prime xpower_mod(g,X,p)solutions.append(x)returnsorted(list(set(solutions)))SageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimport*# sage环境中才生效defamm_solve(k,a,p): 求解 x^k a (mod p) # 在 SageMath 中可以直接使用 nth_root 方法来求高次剩余它内部实现了高效的算法如 Tonelli-Shanks / AMM 扩展等try:rootsmod(a,p).nth_root(k,allTrue)returnsorted([int(r)forrinroots])exceptValueError:return[]# 无解怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋
