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."

[http://www.mathworks.com/matlabcentral/newsreader/view\_\,thread/1353]

  • Resolution

    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\).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email