Writing an Extended Euclidean Calculator that calculates the inverse of a modulus can get pretty difficult. However writing a good algorithm and going through step by step can make the process so much easier. So we want to find a’ or inverse of a so that a * a’ [=] 1 (mod b). In other words we are trying to find an integer (a’) when multiplied by a and then divided by b gives you a remainder of 1. In order to find this number(a’), we have to work the Euclidean Algorithm backwards which is referred to as the Extended Euclidean Algorithm.
So let’s begin with writing out an example in order to explore and discover a working algorithm. This probably could be done recursively but for better understanding we will work sequentially. Lets say we want to find the inverse of: 120 (mod 23) ——–> 120 * a’ [=] 1 (mod 23) .
Euclidean Algorithm
| gcd(a,b) | x[0] = 0 | y[0] = 1 | |
| gcd(120, 23) | 120 = 5 * 23 + 5 | x[1] = 1 | y[1] = -5 |
| gcd(23, 5) | 23 = 4 * 5 + 3 | x[2] = -4 | y[2] = 21 |
| gcd(5, 3) | 5 = 1 * 3 + 2 | x[3] = 5 | y[3] = -26 |
| gcd(3, 2) | 3 = 1 * 2 + 1 | x[4] = -9 | y[4] = 47 |
| gcd(2, 1) | 2 = 2 * 1 + 0 |
Extended Euclidean Algorithm
5 = 1(120) -5(23)
3 = [-4(5) + 1(23)] -> -4(120) +21(23)
2 = [-1(3) + 1(5)] -> 5(120) -26(23)
1 = [-1(2) + 1(3)] -> -9(120) +47(23)
So the inverse of 120 (mod 23) is -9. Likewise The inverse of 23 (mod 120) is 47.
Quotient = a / b
Notice that when (i > 1), x[i] is (quotient * -1 * x[i -1]) + x[i -2]
So x[2] is ( 4 * -1 * 1 ) + 0 = -4
Likewise for y, y[i] is (quotient * -1 * y[i -1]) + y[i -2]
So y[2] is ( 4 * -1 * -5 ) + 1 = 21
Continue until the remainder is zero.
x[i -1] is inverse of a and y[i – 1] is inverse of b
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 | /***************************************************************************** * Finds an integer i such that ai [=] 1 (mod b) * Since we know a and b it uses Euclidean Algorithm to find the inverse of a * Note ai + bj = 1 Considering i is inverse of a and j is inverse of b *******************************************************************************/ int findInverse(int a, int b) { int x[3]; int y[3]; int quotient = a / b; int remainder = a % b; x[0] = 0; y[0] = 1; x[1] = 1; y[1] = quotient * -1; int i = 2; for (; (b % (a%b)) != 0; i++) { a = b; b = remainder; quotient = a / b; remainder = a % b; x[i % 3] = (quotient * -1 * x[(i - 1) % 3]) + x[(i - 2) % 3]; y[i % 3] = (quotient * -1 * y[(i - 1) % 3]) + y[(i - 2) % 3]; } //x[i - 1 % 3] is inverse of a //y[i - 1 % 3] is inverse of b return x[(i - 1) % 3]; } |