Java BigInteger modInverse 및 modPow

Question

modPow 및 Java BigInteger 클래스의 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

BigInteger 클래스의 modPow() 및 modInverse() 동작을 이해하려면이 부분을 참조하십시오.

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

나는 혼란이 올 것 같아요에서

b.modInverse(n1) == 532804210 

때문에 (5 * 532804210) 모드 2,664,021,049 == 1 그

그 후

:

a.modPow(b, n1) == 32 

=> 32^b.modInverse (N1) 개조 2,664,021,049

=> 32^532,804,210 개조 2,664,021,049 == 4

Answer 3

단답형 : 모드 전환 bp-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하지만.

그러나 Fermat의 Little Theorem은 우리에게 해결책을 제시합니다. 양측이 0 합동 때문에 x 및 y 및 주요 계수 p 정수를 들어, 우리는 그 다음 y 모드 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)을 곱셈 역 z을 찾을 수 있습니다.

x !≡ 0 (mod p)이면 에서 x^(p-1) ≡ 1 (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 일 수 있습니다.