जावा बिगइन्टर मोड इनवर्क्स और मोडपा

Question

मैं मोड के व्यवहार और जावा के बिगइंटर वर्ग के 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) आधुनिक २६६४०२१०४९ == 1

इस के बाद:

a.modPow(b, n1) == 32 

=> 32^b.modInverse (n1) आधुनिक 2664021049

=> 32^532,804,210 आधुनिक २६६४०२१०४९ == 4

Answer 3

लघु जवाब: उलटें 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 आधुनिक 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^y से x वापस नहीं ले पाता, कई संभव x मूल्यों देखते हैं क्योंकि। उदाहरण के लिए, x = 2, y = 3, p = 7 के साथ, हमारे पास x^y ≡ 1 (mod p) है, लेकिन x1 हो सकता था।