सी ++ प्रोग्राम फर्मेट के छोटे प्रमेय को लागू करने के लिए

फ़र्मेट की छोटी प्रमेय प्राथमिक संख्या सिद्धांत के मूलभूत परिणामों में से एक है और फ़र्मेट प्रारंभिक परीक्षण का आधार है। प्रमेय का नाम पियरे डी फ़र्मेट के नाम पर रखा गया है, जिन्होंने इसे 1640 में कहा था। प्रमेय कहता है कि यदि p एक अभाज्य संख्या है, तो किसी भी पूर्णांक a के लिए, संख्या a p–a, p का एक पूर्णांक गुणज है।

एल्गोरिदम

Begin
   Function power() is used to compute a raised to power b under modulo M
   function modInverse() to find modular inverse of a under modulo m :
   Let m is prime
   If a and m are relatively prime, then
      modulo inverse is a^(m - 2) mod m
End

उदाहरण कोड

#include <iostream>
using namespace std;
int pow(int a, int b, int M) {
   int x = 1, y = a;
   while (b > 0) {
      if (b % 2 == 1) {
         x = (x * y);
         if (x > M)
            x %= M;
      }
      y = (y * y);
      if (y > M)
         y %= M;
         b /= 2;
   }
   return x;
}
int modInverse(int a, int m) {
   return pow(a, m - 2, m);
}
int main() {
   int a, m;
   cout<<"Enter number to find modular multiplicative inverse: ";
   cin>>a;
   cout<<"Enter Modular Value: ";
   cin>>m;
   cout<<modInverse(a, m)<<endl;
}

आउटपुट

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
3