C++ में अभाज्य संख्या के मॉड्यूलो के तहत घात की घात खोजें

इस समस्या में हमें चार मान A, B, C, M(एक अभाज्य संख्या) दिए गए हैं। हमारा कार्य अभाज्य संख्या के मॉड्यूलो के तहत घात की घात खोजना है।

हमें बस (A ^ (B ^ C)) (mod M) का मान ज्ञात करना है।

आइए एक उदाहरण से इस समस्या को समझते हैं,

इनपुट

A = 3, B = 6, C = 2, M = 11

आउटपुट

3

व्याख्या

(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ (36))(mod 11) = 3

समाधान दृष्टिकोण

इस समस्या का एक सरल समाधान (A ^ (B ^ C)) के मानों की सीधे गणना करना है, जो पहले (B^C) का मान निकालकर और फिर (A ^ (B ^ C)) निकालकर फिर उसका मॉड लेकर किया जाता है। (B^C) का परिणाम एक विशाल आंकड़ा होगा जिसे स्टोर करना एक कार्य हो सकता है। और गणना से ओवरफ्लो हो सकता है।

तो, एक अधिक कुशल दृष्टिकोण फर्मेट के लिटिल प्रमेय का उपयोग करके मान ढूंढना होगा।

प्रमेय है,

a^(m-1) = 1 (mod M) जहां m एक अभाज्य संख्या है।

इसका उपयोग करके हम अपनी समस्या के bc को एक संख्या के रूप में परिवर्तित करेंगे,

x*(M-1) + y, हमारे दिए गए M के मान के लिए।

फर्मेट के प्रमेय का उपयोग करके, भाग A^(x*(M-1)) 1 बन जाता है।

यह गणना को कम कर देगा, A^y का मान ढूंढने के लिए।

y का मान इस प्रकार गणना किया जा सकता है,

B^c = x*(M-1) + y

यह y को शेषफल बनाता है जब हम B^c को (M-1) से विभाजित करते हैं,

तो, y = B^c % (M-1)

यह परिणाम को काफी आसान बनाता है क्योंकि हमें ढूंढना है,

(A ^ ((B^C) %( M-1)) % M

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

उदाहरण

#include<iostream> using namespace std; int calcPowerMod(int x, int y, int p) {    int powMod = 1;    x = x % p;    while (y > 0) {       if (y & 1)          powMod = (powMod*x) % p;       y /=2; // y = y/2       x = (x*x) % p;    }    return powMod; } int findPowerOfPowerMod(int A, int B, int C, int M) {    return calcPowerMod(A, calcPowerMod(B, C, M-1), M); } int main() {    int A = 3, B = 6, C = 2, M = 11;    cout<<"The power of power under modulo is "<<findPowerOfPowerMod(A, B, C, M);    return 0; }

आउटपुट

The power of power under modulo is 3