सी ++ में एक प्राइम के मोड के तहत शक्ति की शक्ति पाएं

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

हमें बस (ए ^ (बी ^ सी)) (मॉड एम) का मूल्य खोजने की जरूरत है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

आउटपुट

3

स्पष्टीकरण

(ए ^ (बी ^ सी)) =(3 ^ (6 ^ 2)) =(3 ^ (36)) (मोड 11) =3

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

समस्या का एक सरल समाधान (ए ^ (बी ^ सी)) के मूल्यों की सीधे गणना करना है, जो पहले (बी ^ सी) और फिर (ए ^ (बी ^ सी)) के मूल्य की गणना करके किया जाता है। अपना मोड ले रहा है। (बी ^ सी) के परिणामस्वरूप एक विशाल आंकड़ा भंडारण होगा जो एक कार्य हो सकता है। और गणना से अतिप्रवाह हो सकता है।

इसलिए, मूल्यों को खोजने के लिए फ़र्मेट के लिटिल थ्योरम का उपयोग करना एक अधिक कुशल तरीका होगा।

प्रमेय है,

a^(m-1) = 1 (mod M) where m is a prime number.

इसका उपयोग करके हम अपनी समस्या के bc को कई रूपों में बदल देंगे,

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

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

यह ए ^y . का मान ज्ञात करने के लिए गणना को कम कर देगा ।

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

बी ^c =एक्स*(एम-1) + वाई

जब हम B ^c . को विभाजित करते हैं तो इससे y शेष बचता है द्वारा (एम-1),

तो, y =B ^c % (एम-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