Fermat’s Little Theorem in C++

This C++ Program demonstrates the implementation of Fermat’s Little Theorem. For the modular multiplicative inverse to exist, the number and modular must be coprime.

Here is source code of the C++ Program to implement Fermat’s Little Theorem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Fermat's Little Theorem
  3.  */
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. /* calculates (a^b)%MOD */
  8. int pow(int a, int b, int MOD) 
  9. {
  10.     int x = 1, y = a;
  11.     while (b > 0) 
  12.     {
  13.         if (b % 2 == 1) 
  14.         {
  15.             x = (x * y);
  16.             if (x > MOD) 
  17.                 x %= MOD;
  18.         }
  19.         y = (y * y);
  20.         if (y > MOD) 
  21.             y %= MOD;
  22.         b /= 2;
  23.     }
  24.     return x;
  25. }
  26.  
  27. int modInverse(int a, int m) 
  28. {
  29.     return pow(a, m - 2, m);
  30. }
  31. //Main
  32. int main()
  33. {
  34.     int a, m;
  35.     cout<<"Enter number to find modular multiplicative inverse: ";
  36.     cin>>a;
  37.     cout<<"Enter Modular Value: ";
  38.     cin>>m;
  39.     cout<<modInverse(a, m)<<endl;
  40. }

$ g++ fermat_little.cpp
$ a.out
 
Enter number to find modular multiplicative inverse: 1111
Enter Modular Value: 331
216
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.