Moving Numbers To Upside Down: Extended Euclidean Algorithm

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.

stranger-things
Stranger Things

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.

3 x 0 = 0 mod 7

3 x 1= 3 mod 7

3 x 2 = 6 mod 7

3 x 3 = 9 mod 7 = 9 – 7 mod 7 = 2 mod 7

3 x 4 = 12 mod 7 = 12 – 7 mod 7 = 5 mod 7

3 x 5 = 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.

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.

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.

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

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

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
extended-euclidean-run
Running Extended Euclidean Algorithm

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.

1 Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s