The extended Euclidean algorithm is used for efficiently finding the multiplicat
ID: 3859004 • Letter: T
Question
The extended Euclidean algorithm is used for efficiently finding the multiplicative inverse (when it exists; Note that when we are looking for the multiplicative inverse of a mod n, gcd(a,n) needs to be 1.) We run the Euclidean algorithm as before but in addition to q1,q2,...r1,r2,... we also compute si and ti where;
Write a C++ program that takes two positive integers as input. First, it checks if the
gcd of them is 1, if so, then it should return the multiplicative inverse of the
second input argument. You need to print a trace of your program as well. For
example, if your input values are 28; 75, the multiplicative inverse of 28 mod 75
is -8 =75 67 and the trace table looks like the following.
i
qi
ri
ri + 1
ri +2
si
ti
1
2
75
28
19
1
0
2
1
28
19
9
0
1
3
2
19
9
1
1
-2
4
9
9
1
0
-1
3
5
1
3
-8
i
qi
ri
ri + 1
ri +2
si
ti
1
2
75
28
19
1
0
2
1
28
19
9
0
1
3
2
19
9
1
1
-2
4
9
9
1
0
-1
3
5
1
3
-8
9-2-qj-29-1 J >2 6-2-%-2tj-1 J >2 122 122 10 01Explanation / Answer
#include <iostream>
using namespace std;
#define DEBUG
void exteuclid(long a, long b, long *x,
long *y, long *d)
/* calculates gcd(a, b)*/
{
long q, r, x1, x2, y1, y2;
if (b == 0) {
*d = a, *x = 1, *y = 0;
return;
}
x2 = 1, x1 = 0, y2 = 0, y1 = 1;
#ifdef DEBUG
cout<<"------------------------------";
cout<<"------------------- ";
cout<<"qi ri ri+1 ri+2 si ti ";
#endif
while (b > 0) {
q = a / b, r = a - q * b;
*x = x2 - q * x1, *y = y2 - q * y1;
a = b,
b = r;
x2 = x1,
x1 = *x,
y2 = y1,
y1 = *y;
#ifdef DEBUG
cout<<q<<" "<<a<<" ";
cout<<b<<" "<<r<<" ";
cout<<y2<<" "<<x2<<endl;
#endif
}
*d = a, *x = x2, *y = y2;
#ifdef DEBUG
cout<<"------------------------------";
cout<<"------------------- ";
#endif
}
int main(void)
{
long a = 28, b = 75, d, x, y;
exteuclid(a, b, &x, &y, &d);
cout<<"x = "<<x<<" y = "<<y<<" d = "<<d;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.