#include #include using namespace std; //Source: extendedeuclideanalgorithm.com /* run this program using the console pauser or add your own getch, system("pause") or input loop */ //Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can /* Calculating the greatest common divisor using the Euclidean Algorithm (non-recursive). (Source: extendedeuclideanalgorithm.com/code) */ int gcd_iterative(int a, int b){ //Set default values for the quotient and the remainder int q = 0; int r = 1; /*In each iteration of the loop below, we calculate the new quotient, remainder, a and b. r decreases, so we stop when r = 0*/ while(r > 0){ //The calculations q = floor(a/b); r = a - q * b; //The values for the next iteration a = b; b = (r > 0)? r : b; } return abs(b); } /* Calculating the greatest common divisor using the Euclidean Algorithm (non-recursive) (Source: extendedeuclideanalgorithm.com/code) */ int gcd_iterative2(int a, int b){ //Set default values for the quotient and the remainder int q = 0; int r = 1; /*In each iteration of the loop below, we calculate the new quotient, remainder, a and b. r decreases, so we stop when r = 0*/ while(b > 0){ //The calculations q = floor(a/b); r = a - q * b; //The values for the next iteration a = b; b = r; } return abs(a); } /* Calculating the greatest common divisor using the Euclidean Algorithm (recursive) (Source: extendedeuclideanalgorithm.com/code) */ int gcd(int a, int b){ if(b == 0){ return abs(a); } int q = floor(a/b); int r = a - q * b; return (r == 0)? abs(b) : gcd(b, r); } //Global variables used by the Extended Euclidean Algorithm int s = 0; int t = 0; //Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can. /* Calculates the gcd and Bézout coefficients, using the Extended Euclidean Algorithm (non-recursive). (Source: extendedeuclideanalgorithm.com/code) */ int xgcd_iterative(int a, int b){ //Set default values for the quotient, remainder, //s-variables and t-variables int q = 0; int r = 1; int s1 = 1; int s2 = 0; int s3 = 1; int t1 = 0; int t2 = 1; int t3 = 0; /*In each iteration of the loop below, we calculate the new quotient, remainder, a, b, and the new s-variables and t-variables. r decreases, so we stop when r = 0*/ while(r > 0){ //The calculations q = floor(a/b); r = a - q * b; s3 = s1 - q * s2; t3 = t1 - q * t2; /* The values for the next iteration, (but only if there is a next iteration)*/ if(r > 0){ a = b; b = r; s1 = s2; s2 = s3; t1 = t2; t2 = t3; } } s = s2; t = t2; return abs(b); } //Can handle b=0 /* Calculates the gcd and Bézout coefficients, using the Extended Euclidean Algorithm (non-recursive). (Source: extendedeuclideanalgorithm.com/code) */ int xgcd_iterative2(int a, int b){ //Set default values for the quotient, remainder, //s-values and t-values int q = 0; int r = 1; int s1 = 1; int s2 = 0; int s3 = 1; int t1 = 0; int t2 = 1; int t3 = 0; /*In each iteration of the loop below, we calculate the new quotient, remainder, a, b, and the new s-values and t-values. r decreases, so we stop when r = 0*/ while(b > 0){ //The calculations q = floor(a/b); r = a - q * b; s3 = s1 - q * s2; t3 = t1 - q * t2; a = b; s1 = s2; t1 = t2; b = r; s2 = s3; t2 = t3; } s = s1; t = t1; return abs(a); } /* Calculates the gcd and Bézout coefficients, using the Extended Euclidean Algorithm (recursive). (Source: extendedeuclideanalgorithm.com/code) */ int xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1){ if(b == 0){ s = 1; t = 0; return abs(a); } int q = floor(a/b); int r = a - q * b; int s3 = s1 - q * s2; int t3 = t1 - q * t2; s = s2; t = t2; return (r == 0)? abs(b) : xgcd(b, r, s2, s3, t2, t3); } /* Calculates the multiplicative inverse of a number b mod n, using the Extended Euclidean Algorithm. If b does not have a multiplicative inverse mod n, then throw an exception. (Source: extendedeuclideanalgorithm.com/code) */ int multinv(int b, int n){ if(xgcd(n, b) == 1){ //t is a global variable that is assigned a value by xgcd return (t + n) % n; } else{ throw -1; } } int main(int argc, char** argv) { //Use your own values for a and b int a = 20; int b = 15; cout << gcd(a, b); //Euclidean Algorithm: //see the output of gcd(a, b) cout << "Euclidean Algorithm:" << endl; cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl; //------------------------------------------------------------- /*Extended Euclidean Algorithm: see the output of xgcd(a,b) and Bezout coefficients And verify that they are correct.*/ int my_gcd = xgcd(a, b); //xgcd will set global variables s and t int verification = abs(s*a+t*b); cout << "Extended Euclidean Algorithm:" << endl; cout << "The gcd of " << a << " and " << b << " is " << my_gcd << endl; cout << "And the Bezout coefficients: s=" << s << " and t=" << t << "." << endl; cout << "And " << s << " * " << a << " + " << t << " * " << b << " = " << verification << endl; if(my_gcd == verification){ cout << "So as we expect, s*a+t*b is equal to the gcd we found." << endl; } else{ cout << "Something went wrong" << endl; } //#------------------------------------------------------------ b = 15; int n = 10; /*Multiplicative Inverse: Try to compute the multiplicative inverse of b mod n. If that succeeds, verify that it's correct. If it doesn't succeed, show the error raised by the function.*/ try { cout << multinv(b, n) << endl; } catch (int n) { cout << "Error: there is no multiplicative inverse for the given numbers" << endl; } return 0; }