Extended Euclidean Algorithm in C++

This C++ Program demonstrates the implementation of Extended Eucledian Algorithm. For the modular multiplicative inverse to exist, the number and modular must be coprime.

Here is source code of the C++ Program to implement Extended Eucledian Algorithm. 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 Extended Eucledian Algorithm
  3.  */
  4. #include <iostream>
  5. #include <utility> 
  6.  
  7. using namespace std;
  8. /* return the gcd of a and b followed by the pair x and y of 
  9.   equation ax + by = gcd(a,b)
  10. */
  11. pair<int, pair<int, int> > extendedEuclid(int a, int b) 
  12. {
  13.     int x = 1, y = 0;
  14.     int xLast = 0, yLast = 1;
  15.     int q, r, m, n;
  16.     while (a != 0) 
  17.     {
  18.         q = b / a;
  19.         r = b % a;
  20.         m = xLast - q * x;
  21.         n = yLast - q * y;
  22.         xLast = x; 
  23.         yLast = y;
  24.         x = m; 
  25.         y = n;
  26.         b = a; 
  27.         a = r;
  28.     }
  29.     return make_pair(b, make_pair(xLast, yLast));
  30. }
  31.  
  32. int modInverse(int a, int m) 
  33. {
  34.     return (extendedEuclid(a, m).second.first + m) % m;
  35. }
  36.  
  37. //Main
  38. int main()
  39. {
  40.     int a, m;
  41.     cout<<"Enter number to find modular multiplicative inverse: ";
  42.     cin>>a;
  43.     cout<<"Enter Modular Value: ";
  44.     cin>>m;
  45.     cout<<modInverse(a, m)<<endl;
  46. }

$ g++ eucledian.cpp
$ a.out
 
Enter number to find modular multiplicative inverse: 133
Enter Modular Value: 135
67
 
------------------
(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.