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.
/*
* C++ Program to Implement Extended Eucledian Algorithm
*/
#include <iostream>
#include <utility>
using namespace std;
/* return the gcd of a and b followed by the pair x and y of
equation ax + by = gcd(a,b)
*/
pair<int, pair<int, int> > extendedEuclid(int a, int b)
{
int x = 1, y = 0;
int xLast = 0, yLast = 1;
int q, r, m, n;
while (a != 0)
{
q = b / a;
r = b % a;
m = xLast - q * x;
n = yLast - q * y;
xLast = x;
yLast = y;
x = m;
y = n;
b = a;
a = r;
}
return make_pair(b, make_pair(xLast, yLast));
}
int modInverse(int a, int m)
{
return (extendedEuclid(a, m).second.first + m) % m;
}
//Main
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;
}
$ 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.
Next Steps:
- Get Free Certificate of Merit in C++ Programming
- Participate in C++ Programming Certification Contest
- Become a Top Ranker in C++ Programming
- Take C++ Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Buy C++ Books
- Apply for Computer Science Internship
- Apply for Information Technology Internship
- Buy Programming Books
- Buy Computer Science Books