如何在Python中根据pow(a,b,c)结果、b和c求解a？

嘿，这个问题本质上是求模运算下的b次根——也就是找整数a，满足a^b ≡ res mod c。不过得先明确：不是所有输入组合都有解，而且解的数量可能不止一个，得分场景慢慢拆解：

一、先判断是否存在解 #

在动手求解前，得先确认有没有解，不然白费功夫：

• 如果c是质数p：
  • 若res ≡ 0 mod p，那解就是a ≡ 0 mod p（毕竟0的任何正整数次方还是0）。
  • 若res ≠ 0 mod p，解存在的条件是res^((p-1)/gcd(b, p-1)) ≡ 1 mod p。这是基于费马小定理和循环群的结论：模p的乘法群是阶为p-1的循环群，只有当res落在b次幂构成的子群里时，才有对应的根。
• 如果c是合数：
  可以用中国剩余定理，先把c分解成质因数幂的乘积（比如c = p₁^k₁ * p₂^k₂ * ... * pₙ^kₙ），分别判断每个模p_i^k_i下的方程是否有解，只有所有子方程都有解时，原方程才有解。

二、有解时的求解方法 #

场景1：c是质数p，且res ≠ 0 mod p #

假设已经确认有解，步骤如下：

1. 计算d = gcd(b, p-1)，再用扩展欧几里得算法找到整数k、m，使得b*k + (p-1)*m = d（这一步是为了找b在模(p-1)/d下的逆元）。
2. 找模p的一个原根g（原根是指能生成模p所有非零元素的数，比如模7的原根是3），把res表示为g的幂：res = g^t mod p（小质数可以直接试，大质数需要离散对数算法求解）。
3. 原方程转化为：(g^x)^b ≡ g^t mod p → g^(x*b) ≡ g^t mod p，根据循环群的性质，等价于x*b ≡ t mod (p-1)。
4. 解这个线性同余方程，得到x ≡ t*k/d mod ((p-1)/d)，其中k是步骤1中得到的系数。
5. 最终的a就是g^x mod p，而且总共有d个不同的解：g^(x + s*(p-1)/d) mod p，其中s=0,1,...,d-1。

举个实际例子：p=7，b=3，res=6。

• p-1=6，d=gcd(3,6)=3，检查6^((7-1)/3)=6^2=36≡1 mod7，满足解的存在条件。
• 取原根g=3，res=6=3^3 mod7（因为3^3=27≡6 mod7），所以t=3。
• 方程变为3x ≡3 mod6，解为x≡1 mod2，即x=1、3、5。
• 对应的a值：3^1=3，33=6，3^5=243≡5 mod7。验证一下：3^3=27≡6，63=216≡6，5^3=125≡6，都符合要求。

场景2：c是质数幂p^k #

如果c是质数的幂次，情况会复杂一点：

• 若res ≡0 mod p^k，那么a必须是p的倍数。设a=p^m * t（t与p互质），代入方程得p^(m*b)*t^b ≡0 mod p^k，只要m*b ≥k就行。比如k=4，b=2，那m≥2，t可以是任何与p互质的数，都是解。
• 若res与p互质，先求解模p的方程得到基础解a₀，再用亨泽尔引理把解提升到模p^{k的情况。如果`b*a₀^(b-1)`不被p整除，那么存在唯一的解可以提升到模p}k；如果被p整除，可能有多个解或者无法提升。

场景3：c是任意合数 #

用中国剩余定理拆分问题：

1. 把c分解为质因数幂的乘积c=∏p_i^k_i。
2. 分别求解每个模p_i^k_i下的方程a^b≡res mod p_i^k_i，得到每个模的解集合。
3. 用中国剩余定理把每个模的解组合起来，得到模c下的所有解。

三、Python中的实现思路 #

如果要写代码实现，可以结合pow函数和扩展欧几里得算法，比如先实现扩展欧几里得求逆元：

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extended_gcd(b, a % b)
        return (g, y, x - (a // b) * y)

对于质数场景，还需要实现原根查找和离散对数求解的逻辑；对于合数场景，得先做质因数分解，再结合中国剩余定理合并解。

不过要注意，当c是很大的合数时，质因数分解会非常耗时，这时候求解难度会陡增。

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