## An algorithm for the inverse over Zp

Is the following approach correct?

Question: "I would like to know how to perform calculations in finite fields using Matlab.

For example, is there a nice way to multiply or invert matrices whose components lie in a finite field, say the field of the integers modulo a prime number?"

Answer: "I have done some work on that a long time ago. Multiplication is no problem. You just do normal multiplication an take the result modulo a prime. It is easy to prove theoretically. I think I tried a similar approach with the inverse. The algorithm (as I remeber) is like this:

1. Calculate the inverse;
2. Multiply the inverse by the determinant of the original matrix;
3. Calculate it modulo a prime.

I use came to this algorithm intuitively and never tried to prove it, but it worked just fine."

• #### Solution

In the second step is calculated $$\det(\mathbf A)\mathbf A^{-1}$$, i.e. the adjoint matrix over $$\mathbb R$$.

The factorization over $$p$$ in the third step yields the adjoint matrix over $$\mathbb Z_p$$.

When $$\det(\mathbf A)\ne 1$$, in our case $$\det(\mathbf A)\not\equiv 1 \pmod p$$, are the inverse and the adjoint matrices distinct.

To get the inverse matrix over $$\mathbb Z_p$$ it is necessary to divide the adjoint matrix by the determinant.

The algorithm would work fine only over $$\mathbb Z_2$$.