Java BigInteger modInverse und modPow

Question

Ich versuche, das Verhalten von ModPow und modInverse der Java BigInteger-Klasse zu verstehen, da sie nicht so funktionieren, wie ich es erwarten würde. Vielleicht ist hier fehlt mir etwas einfach, so ein sehr einfaches Stück 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)); 

Der Ausgang ich erhalte, ist:

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

Jetzt würde ich die 4 dort in der letzten Zeile erwarten be 2, wie es ist (a^b)^(1/b) = a^(b*(1/b)) = a

Sollte dies auch in einem Modulo-Feld funktionieren?

Was mache ich falsch?

Answer 1

Verweise auf das Verhalten von modPow() und modInverse() der BigInteger-Klasse.

modPow:

BigInteger numOne = new BigInteger("5"); 
BigInteger numTwo = new BigInteger("20"); 
BigInteger exponent = new BigInteger("3"); 
BigInteger MP = numOne.modPow(exponent, numTwo); 
System.out.println(numOne + "^" + exponent + " mod " + numTwo + " = " + MP); 

modInverse:

BigInteger numOne = new BigInteger("7"); 
BigInteger numTwo = new BigInteger("20"); 
BigInteger MI = numOne.modInverse(numTwo); 
System.out.println(numOne + " ^-1 mod " + numTwo + " = " + MI); 

Answer 2

Ich denke, die Verwirrung kommt, daß

b.modInverse(n1) == 532804210 

weil (5 * 532804210) mod 2664021049 == 1

Danach:

a.modPow(b, n1) == 32 

=> 32^b.modInverse (n1) mod 2664021049

=> 32^532.804.210 mod 2664021049 == 4

Answer 3

Kurze Antwort: Invert b mod p-1, nicht mod p. (Wenn b nicht umkehrbar mod p-1 ist, ist das Problem unlösbar.)

---

Während es der Fall ist, wenn x ≡ y (mod p), dann x^z ≡ y^z (mod p) wir nicht dem Schluss, dass z^x ≡ z^y (mod p). Zum Beispiel durch Fermats kleinen Satz,

x^p ≡ x (mod p) 

obwohl p ≡ 0 (mod p) und x^0 = 1.

Aber Fermat's Little Theorem gibt uns eine Lösung. Für ganze Zahlen x und y und besten Modul p, wenn wir eine multiplikative Inverse z für y mod p-1, dann

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

Wenn x ≡ 0 (mod p), dann (x^(p-1))^k * x ≡ x (mod p), weil beide Seiten kongruent sind auf 0 zu finden.

Wenn x !≡ 0 (mod p), dann können wir x^(p-1) ≡ 1 (mod p) von x^p ≡ x (mod p) ableiten, und wir haben (x^(p-1))^k * x ≡ 1^k * x ≡ x (mod p).

So (x^y)^z ≡ x (mod p).

Auf der anderen Seite, wenn y nicht umkehrbar mod p-1 ist, dann stellt sich heraus, dass wir nicht x von x^y erholen kann, denn es gibt mehrere mögliche x Werte sind. Zum Beispiel haben wir mit x = 2, y = 3, p = 7x^y ≡ 1 (mod p), aber x könnte 1 gewesen sein.