Code: Select all
#include<iostream>
#include<conio.h>
using namespace std;
typedef unsigned long ulong;
long eeuclid(long m, long b, long *inverse){ /// eeuclid( modulus, num whose inv is to be found, variable to put inverse )
long A1 = 1, A2 = 0, A3 = m,
B1 = 0, B2 = 1, B3 = b,
T1, T2, T3, Q;
cout<<endl<<"eeuclid() started"<<endl;
while(1){
if(B3 == 0){
*inverse = 0;
return A3; // A3 = gcd(m,b)
}
if(B3 == 1){
*inverse = B2; // B2 = b^-1 mod m
return B3; // A3 = gcd(m,b)
}
Q = A3/B3;
T1 = A1 - Q*B1;
T2 = A2 - Q*B2;
T3 = A3 - Q*B3;
A1 = B1; A2 = B2; A3 = B3;
B1 = T1; B2 = T2; B3 = T3;
}
cout<<endl<<"ending eeuclid() "<<endl;
}
int main(){
long a, b, c, d=0, e, inverse = 0;
int ch;
cout<<"Preparing extended Euclid ---> "<<endl;
cout<<"m >> ";
cin >> a;
cout<<"b >> ";
cin >> b;
cout<<"gcd("<<a<<","<<b<<") = "<<eeuclid(a, b, &inverse);
cout<<" and inverse = "<<inverse<<endl;
cout<<endl<<"Press q to quit ... "<<endl;
return 0;
}
Code: Select all
cout<<"gcd("<<a<<","<<b<<") = "<<eeuclid(a, b, &inverse);
cout<<" and inverse = "<<inverse<<endl;
Code: Select all
cout<<"gcd("<<a<<","<<b<<") = "<<eeuclid(a, b, &inverse)<<" and inverse = "<<inverse<<endl;
Why is that??