Java BigInteger modInverse 和 modPow

Question

我正在尝试了解 Java 的 BigInteger 类的 modPow 和 modInverse 的行为，因为它们并不像我预期的那样工作。也许我遗漏了一些简单的东西，所以这里有一段非常简单的代码:

BigInteger a = BigInteger.valueOf(2);
BigInteger b = BigInteger.valueOf(5);

BigInteger n1 = new BigInteger(32, 100, new SecureRandom());
System.out.println("n = " + n1);

System.out.println("a^b = " + a.modPow(b, n1) + " ;; (a^b)^(b^-1) = " + a.modPow(b, n1).modPow(b.modInverse(n1), n1));

我得到的输出是:

n = 2664021049    (This is a random prime, can change each run)
a^b = 32 ;; (a^b)^(b^-1) = 4

现在，我希望最后一行的 4 是 2，因为它是 (a^b)^(1/b) = a^(b*(1/b)) = a

这也适用于模域吗？

我做错了什么？

Answer 1

简答:反转b国防部 p-1 , 不是模组 p . (如果 b 不是可逆模 p-1 ，则问题无解。)

---

如果 x ≡ y (mod p) 是这样的话, 然后 x^z ≡ y^z (mod p) ，我们不能得出结论 z^x ≡ z^y (mod p) .例如，由费马小定理，

x^p ≡ x (mod p)

即使p ≡ 0 (mod p) , 和 x^0 = 1 .

然而，费马小定理给了我们一个解决方案。对于整数 x和 y和素模 p ，如果我们能找到一个乘法逆元 z对于 y mod p-1 ，然后

(x^y)^z = x^(yz)
        = x^(k(p-1) + 1) for some k
        = (x^(p-1))^k * x

如果x ≡ 0 (mod p) , 然后 (x^(p-1))^k * x ≡ x (mod p)因为两边都等于 0。

如果x !≡ 0 (mod p) , 那么我们可以导出 x^(p-1) ≡ 1 (mod p)来自 x^p ≡ x (mod p) ，我们有 (x^(p-1))^k * x ≡ 1^k * x ≡ x (mod p) .

因此，(x^y)^z ≡ x (mod p) .

另一方面，如果y不是可逆模组 p-1 ，然后事实证明我们无法恢复 x来自 x^y ，因为有多个可能的 x值。例如，使用 x = 2, y = 3, p = 7 , 我们有 x^y ≡ 1 (mod p) ，但是 x本来可以是 1 .