You might be familiar with the upside down if you watched Netflix series Stranger Things. Eleven shows the underside of a game board to analogize the upside down. Upside down refers inverse place to the earth in the series. Let’s imagine a number in the human earth, what would it be in the upside down? Actually, we often use inverse numbers in daily mathematics.
When a number multiplied by its inverse, the result would be equal to one. That’s the rule. The following demonstration is over real numbers.
a x (a)-1 = a x (1/a) = 1
Modular Inverse
On the other hand, modular arithmetic is defined over integer instead of real numbers. Numbers wrap around 0 and modulus. They still might have inverses. We are interested in modular inverses more! Let’s focus on different times 3 for modulus 7.
0 x 3 = 0 mod 7
1 x 3= 3 mod 7
2 x 3 = 6 mod 7
3 x 3 = 9 mod 7 = 9 – 7 mod 7 = 2 mod 7
4 x 3 = 12 mod 7 = 12 – 7 mod 7 = 5 mod 7
5 x 3 = 15 mod 7 = 15 – 7 = 8 – 7 = 1 mod 7
You might realize that 3 times 5 is equal to 1 for mod 7. Just like the rule of finding the inverse. This means that inverse of 3 is equal to 5, and vice versa inverse of 5 is equal to 3 in mod 7.
Herein, divisor in a dividing operation can be expressed as its modular inverse as multiplier. Let’s look at 2 over 5 in mod 7.
2/5 mod 7 = 2 x (1/5) mod 7 = 2 x (5)-1 mod 7 = 2 x 3 mod 7 = 6 mod 7
Basically, the number that we are going to invert can be multiplied with numbers from 0 to mod-1. If the result is equal to 1, then its modular inverse is found. You can run the following python code to find the modular inverse of a number.
Coding
def find_modular_inverse(number, mod):
for i in range(0, mod):
if (number * i) % mod == 1:
return i
raise ValueError('cannot be found an inverse')
But complexity of this approach is O(mod). And that would be a big problem for really large mod values. Particularly, we need multiplicative inverses in public key cryptography with very large integers (e.g. 3072 bit integer for RSA).
Finding Multiplicative Inverse Faster
Instead of checking all numbers between 0 and mod-1,we can narrow down the target set. Herein, Extended Euclidean Algorithm assists us to find modular inverse in a less complex way.
We would store ten different variables. The following table demonstrates initial values of these variables.
| q | x1 | x2 | x3 | y1 | y2 | y3 | t1 | t2 | t3 |
|---|---|---|---|---|---|---|---|---|---|
| q | 1 | 0 | mod | 0 | 1 | num | t1 | t2 | t3 |
Then, q and t values would always be calculated as shown below. Suppose that we would like to find modular inverse of 3 mod 7 again.
1st Iteration
q = int(x3 / y3) = int(7 / 3) = 2
t1 = x1 – q x y1 = 1 – 2 x 0 = 1
t2 = x2 – q x y2 = 0 – 2 x 1 = -2
t3 = x3 – q x y3 = 7 – 2 x 3 = 1
| q | x1 | x2 | x3 | y1 | y2 | y3 | t1 | t2 | t3 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 0 | 7 | 0 | 1 | 3 | 1 | -2 | 1 |
In the next line, y values will shift to x values, and t values will shift to y values.
Shifting
x1 = y1, x2 = y2, x3 = y3
y1 = t1, y2 = t2, y3 = t3
| q | x1 | x2 | x3 | y1 | y2 | y3 | t1 | t2 | t3 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 0 | 7 | 0 | 1 | 3 | 1 | -2 | 1 |
| 0 | 1 | 3 | 1 | -2 | 1 |
2nd Iteration
In the current line, q and t values will be calculated again based on the previously defined formulas.
q = int(x3 / y3) = int(3 / 1) = 3
t1 = x1 – q x y1 = 0 – 3 x 1 = -3
t2 = x2 – q x y2 = 1 – 3 x (-2) = 7
t3 = x3 – q x y3 = 3 – 3 x 1 = 0
| q | x1 | x2 | x3 | y1 | y2 | y3 | t1 | t2 | t3 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 0 | 7 | 0 | 1 | 3 | 1 | -2 | 1 |
| 3 | 0 | 1 | 3 | 1 | -2 | 1 | -3 | 7 | 0 |
We would create new lines recurrently while y3 is not equal to 1. When this condition fulfilled, the final value of y2 is the modular inverse. As seen, we found that condition in the second line.
(3)-1 mod 7 = -2 mod 7 = -2 + 7 mod 7 = 5 mod 7
Coding
The following python code finds the modular multiplicative inverse by applying extended euclidean algorithm.
def findModularInverse(a, mod):
while(a<0):
a = a + mod
x1 = 1; x2 = 0; x3 = mod
y1 = 0; y2 = 1; y3 = a
q = int(x3 / y3)
t1 = x1 - q*y1
t2 = x2 - q*y2
t3 = x3 - (q*y3)
if dump == True:
print("q\tx1\tx2\tx3\ty1\ty2\ty3\tt1\tt2\tt3")
print(q,"\t",x1,"\t",x2,"\t",x3,"\t",y1,"\t",y2,"\t",y3,"\t",t1,"\t",t2,"\t",t3)
while(y3 != 1):
x1 = y1; x2 = y2; x3 = y3
y1 = t1; y2 = t2; y3 = t3
q = int(x3 / y3)
t1 = x1 - q*y1
t2 = x2 - q*y2
t3 = x3 - (q*y3)
if dump == True:
print(q,"\t",x1,"\t",x2,"\t",x3,"\t",y1,"\t",y2,"\t",y3,"\t",t1,"\t",t2,"\t",t3)
print("-----------------------------------------------------------------------")
return y2
Complexity and Big O notation
Extended Euclidiean Algorithm runs in time O(log(mod)2) in the big O notation. That is a really big improvement.
Luckily, java has already served a out-of-the-box function under the BigInteger class to find the modular inverse of a number for a modulus.
BigInteger inverseNumber = number.modInverse(modulus);
So, we’ve toured around the upside down with numbers in this post. In contrast to Stranger Things, extended euclidean algorithm makes upside down secure even though for today’s computation power because it reduces the complexity dramatically.
Support this blog if you do like!
1 Comment
Comments are closed.