Java BigInteger modInverse and modPow

Question

I am trying to understand the behavior of modPow and modInverse of Java's BigInteger class as they do not work as I would expect. Maybe I am missing something simple, so here is a very simple piece of code:

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));

The output I get is:

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

Now, I would expect the 4 there in the last line to be 2, as it is (a^b)^(1/b) = a^(b*(1/b)) = a

Should this also work in a modulo field?

What am I doing wrong?

Answer 1

Short answer: Invert b mod p-1, not mod p. (If b isn't invertible mod p-1, the problem is unsolvable.)

---

While it is the case that if x ≡ y (mod p), then x^z ≡ y^z (mod p), we cannot conclude that z^x ≡ z^y (mod p). For example, by Fermat's Little Theorem,

x^p ≡ x (mod p)

even though p ≡ 0 (mod p), and x^0 = 1.

However, Fermat's Little Theorem gives us a solution. For integers x and y and a prime modulus p, if we can find a multiplicative inverse z for y mod p-1, then

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

If x ≡ 0 (mod p), then (x^(p-1))^k * x ≡ x (mod p) because both sides are congruent to 0.

If x !≡ 0 (mod p), then we can derive x^(p-1) ≡ 1 (mod p) from x^p ≡ x (mod p), and we have (x^(p-1))^k * x ≡ 1^k * x ≡ x (mod p).

Thus, (x^y)^z ≡ x (mod p).

On the other hand, if y is not invertible mod p-1, then it turns out we can't recover x from x^y, because there are multiple possible x values. For example, with x = 2, y = 3, p = 7, we have x^y ≡ 1 (mod p), but x could have been 1.