如何快速计算模根x^(1/y) mod m？

这个问题本质上是模根求解（Modular Root Finding）——也就是找满足 x1^y ≡ x2 mod m 的x1，算是模幂运算的逆过程。不过得先说明：不是随便给个x2、y、m都有解，而且求解的快慢很大程度上取决于m的结构，下面分场景给你拆解可行的方案：

一、先判断是否存在解 #

这是第一步，避免做无用功：

• 如果m是质数p：
  计算 d = gcd(y, p-1)，当且仅当 x2^((p-1)/d) ≡ 1 mod p 时，方程有解。
• 如果m是合数：
  先把m分解为质幂乘积 m = p₁^k₁ * p₂^k₂ * ... * pₙ^kₙ，然后对每个质幂 pᵢ^kᵢ 分别判断是否有解（判断逻辑类似质数场景的扩展），只有所有质幂都有解时，原方程才有解。

二、分场景的快速求解方案 #

1. 最简单的场景：y与φ(m)互质（φ是欧拉函数） #

如果 gcd(y, φ(m)) = 1，那直接求y在模φ(m)下的逆元d（即满足 y*d ≡ 1 mod φ(m) 的正整数d），然后计算：

x1 = x2^d mod m

原理很直观：(x1^y)^d = x1^(y*d) ≡ x1^1 mod m（根据欧拉定理，当x1与m互质时成立；如果x1与m不互质，这个结论在y和φ(m)互质的前提下依然成立，只需额外验证即可）。

举个例子：m=7（φ(7)=6），y=5（gcd(5,6)=1），逆元d=5（因为5*5=25≡1 mod6），如果x2=2（即x1^5≡2 mod7），那x1=2^5 mod7=32 mod7=4，验证一下4^5=1024 mod7=2，完全正确。

2. m是质数p的情况 #

如果y和p-1不互质：

1. 先计算 d = gcd(y, p-1)，验证解存在（用前面的判断条件）。
2. 找p的一个原根g（原根是指能生成模p所有非零元素的数，比如p=7的原根是3）。
3. 用离散对数算法（比如Baby-step Giant-step）找到k，使得 g^k ≡ x2 mod p。
4. 解线性同余方程 y*t ≡ k mod (p-1)，这个方程会有d个解。
5. 每个解t对应的 x1 = g^t mod p 都是原方程的解。

如果p-1的因子比较小，用Pohlig-Hellman算法求解离散对数会比Baby-step Giant-step快很多。

3. m是质数幂p^k的情况 #

先求解模p的根x0，然后用Hensel引理把解从模p提升到模p^k：

• 如果y和p互质，且x0^y ≡x2 mod p，那么可以通过迭代计算得到模p^k的解：x_{n+1} = x_n - (x_n^y - x2) * y^{-1} mod p^{n+1}，其中y^{-1}是y模p的逆元。
• 如果p整除y，情况会更复杂，需要额外判断x2是否满足特定的幂次条件。

4. m是任意合数的情况 #

用**中国剩余定理（CRT）**拆分求解：

1. 把m分解为质幂乘积 m = p₁^k₁ * p₂^k₂ * ... * pₙ^kₙ。
2. 对每个质幂 pᵢ^kᵢ，求解 x1 ≡ aᵢ mod pᵢ^kᵢ（用上面质数幂的方法）。
3. 用中国剩余定理把所有aᵢ合并，得到x1 mod m的解。

三、关于"快速计算"的关键点 #

• 模根求解的最大瓶颈通常是m的质因数分解，如果m是大合数（比如1024位），分解会非常慢，这也是很多密码学方案（比如RSA）的安全性基础。
• 对于通用场景，推荐使用Adleman-Manders-Miller算法，它能处理任意m、y、x2的情况，是目前比较高效的通用模根求解算法。
• 如果是你描述的A、B通信这类密码学场景，通常会预先约定m的结构（比如m是两个大质数的乘积，且y与φ(m)互质），这样可以直接用逆元的方法快速求解，避免复杂的离散对数计算。

内容的提问来源于stack exchange，提问作者R M