# Extended Euclid’s Algorithm C Code

Before going through this article, please look at my previous article about Euclid’s Algorithm. The Extended Euclid’s algorithm solves the following equation.

\[GCD(a, b) = d = ax + by\]

In addition to calculating a GCD, it calculates coefficients x and y such that satisfies the above equation. These coefficients x and y are important for calculating modular multiplicative inverses. The Extended Euclid’s algorithm is used in a much practical application specifically in cryptography.

The following C code presents an efficient algorithm to solve the Extended Euclid’s algorithm. The code is also available on GitHub.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <stdio.h> #include <math.h> typedef struct { int d; int x; int y; } EE; EE extended_euclid(int a, int b) { EE ee1, ee2, ee3; if (b == 0) { ee1.d = a; ee1.x = 1; ee1.y = 0; printf("%d %d %d %d %d\n", a, b, ee1.d, ee1.x, ee1.y); return ee1; } else { ee2 = extended_euclid(b, a % b); ee3.d = ee2.d; ee3.x = ee2.y; ee3.y = ee2.x - floor(a / b) * ee2.y; printf("%d %d %d %d %d\n", a, b, ee3.d, ee3.x, ee3.y); return ee3; } } int main(int argc, char* argv[]) { int a = 287, b = 288; EE ee = extended_euclid(a, b); printf("GCD = %d\n", ee.d); printf("x = %d\n", ee.x); printf("y = %d\n", ee.y); return 0; } |