An algorithm for the inverse over Zp
Task number: 2610
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\).
