3.8 Inverting Matrices Mod n – Introduction to Cryptography with Coding Theory, 3rd Edition

3.8 Inverting Matrices Mod n

Finding the inverse of a matrix mod n can be accomplished by the usual methods for inverting a matrix, as long as we apply the rule given in Section 3.3 for dealing with fractions. The basic fact we need is that a square matrix is invertible mod n if and only if its determinant and n are relatively prime.

We treat only small matrices here, since that is all we need for the examples in this book. In this case, the easiest way is to find the inverse of the matrix is to use rational numbers, then change back to numbers mod n. It is a general fact that the inverse of an integer matrix can always be written as another integer matrix divided by the determinant of the original matrix. Since we are assuming the determinant and n are relatively prime, we can invert the determinant as in Section 3.3.

For example, in the 2×2 case the usual formula is

abcd1=1adbcdbca, 

so we need to find an inverse for adbc(modn).

Example

Suppose we want to invert 1234(mod11). Since adbc=2,  we need the inverse of 2 mod 11. Since 5×(2)1(mod11),  we can replace 1/2 by 5 and obtain

(1234)112(4231)5(4231)(9175)(mod11).

A quick calculation shows that

(1234)(9175)=(23115523)(1001)(mod11).

Example

Suppose we want the inverse of

M=(111123149)(mod11).

The determinant is 2 and the inverse of M in rational numbers is

12651682231.

(For ways to calculate the inverse of a matrix, look at any book on linear algebra.) We can replace 1/2 with 6 mod 11 and obtain

M1(3368410146)(mod11).

Why do we need the determinant and n to be relatively prime? Suppose MNI(modn),  where I is the identity matrix. Then

det(M)det(N)det(MN)det(I)1(modn).

Therefore, det(M) has an inverse mod n,  which means that det(M) and n must be relatively prime.