Java BigInteger modInverse i modPow

Question

Próbuję zrozumieć zachowanie modPow i modInverse klasy BigInteger Java, ponieważ nie działają tak, jak bym się spodziewał. Może brakuje mi coś prostego, więc tutaj jest bardzo prosty kawałek kodu:

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

Wyjście pojawia się:

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

Teraz chciałbym oczekiwać 4 tam w ostatnim wierszu do być 2, jak to jest (a^b)^(1/b) = a^(b*(1/b)) = a

Czy to również działa w polu modulo?

Co robię źle?

Answer 1

Skorzystaj z tego, aby zrozumieć zachowanie modPow() i modInverse() klasy BigInteger.

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

Chyba zamieszanie pochodzi, że

b.modInverse(n1) == 532804210 

ponieważ (5 * 532804210) mod 2664021049 == 1

Następnie:

a.modPow(b, n1) == 32 

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

=> 32^532804210 mod 2664021049 == 4

Answer 3

Krótki odpowiedź: Odwracanie b mod p-1, nie mod p. (Jeśli nie jest odwracalna b mod p-1, problem jest nierozwiązywalny.)

---

Chociaż prawdą jest, że jeśli x ≡ y (mod p), następnie x^z ≡ y^z (mod p), my można stwierdzić, że niez^x ≡ z^y (mod p). Na przykład, przez małe twierdzenie Fermata,

x^p ≡ x (mod p) 

chociaż p ≡ 0 (mod p) i x^0 = 1.

Jednak Małe twierdzenie Fermata daje nam rozwiązanie. Dla liczb całkowitych x i y i głównego modułu p, czy możemy znaleźć Liczba odwrotna z dla y mod p-1, następnie

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

If x ≡ 0 (mod p), potem (x^(p-1))^k * x ≡ x (mod p) ponieważ obie strony są przystające do 0.

Jeśli x !≡ 0 (mod p), możemy wywnioskować x^(p-1) ≡ 1 (mod p) z x^p ≡ x (mod p), a my mamy (x^(p-1))^k * x ≡ 1^k * x ≡ x (mod p).

Tak więc, (x^y)^z ≡ x (mod p).

Z drugiej strony, jeśli nie jest odwracalna y mod p-1, a potem okazuje się, że nie można odzyskać x z x^y, ponieważ istnieje wiele możliwych wartości x. Na przykład z x = 2, y = 3, p = 7, mamy x^y ≡ 1 (mod p), ale x może być 1.