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.

```
/*
```

 * 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.

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

« Prev - C++ Program to Implement KMP Pattern Searching Algorithm

» Next - Z-Algorithm in C++

Related Posts:

Recommended Articles: