Lets start with

M = 5  8
    17 3

and modulo 26.

1. Calculate inverse matrix

det(M) = 5*3 - 8*17 = -121
MI = 1      | 3  -8 |
     ---- * | -17 5 |
     -121
   = ?

2. How to deal with fractional number

• Apply modulo to each element in the inverse matrix.
• So we want to solve
  • (3 / -121) mod 26
  • = -3 * 121^(-1) mod 26
  • To evaluate 121^(-1), we should calculate Modular Inverse.

3. What is Modular Inverse?

In a number system without modulo...

• If ax = 1, then x is a multiplicative inverse.
  • x = 1/a. easy.

In a number system with modulo...

• If ax ≡ 1 mod M, then x is a modular multiplicative inverse and x ≡ a^(-1) mod M.

  • tedious but solvable.

• Let's try 3x ≡ 1 mod 5.

  • 3 * 0 ≡ 0 (x)
  • 3 * 1 ≡ 3 (x)
  • 3 * 2 ≡ 1 (o)
  • x ≡ 3^(-1) ≡ 2.

• For better solution, take a look at Extended Euclidean Algorithm.

4. Extended Euclidean Algorithm

• this is just for an introduction.

Euclidean Algorithm

• is an algorithm to calculate greatest common divisor. (a.k.a. GCD)

Extended Euclidean Algorithm

• is an algorithm to calculate GCD and x, y from Bezout's identity.

• Bezout's identity?

  • If GCD(a,b)=d, then ax + by = d has a solution x and y.

• Tracking Euclidean Algorithm...

  • a = b * q[0] + r[1]
  • b = r[1] * q[1] + r[2]
  • r[1] = r[2] * q[2] + r[3]
  • ...
  • r[i-1] = r[i] * q[i] + r[i+1]
  • => r[i+1] = r[i-1] - r[i] * q[i]