triploblastic's blog

gaussian elimination modulo a prime
By triploblastic, history, 9 years ago, In English

I have read about gaussian elimination technique from this link. http://e-maxx-eng.github.io/linear_algebra/linear-system-gauss.html . But how do we solve the equations given a prime modulo? do i need to calculate the multiplicative inverse every time i have to divide the row with a number or is there another way to do that without using multiplicative inverse?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Multiplicative inverse can be easily calculated using Euler's theorem, I don't know a reason not to use it.

It is possible to at least partially avoid multiplicative inverse by using (not extended) Euclidean algorithm on rows, but that only hides the value multiplicative inverse. It performs the same as actions as when calculating modular inverse with extended Euclidean algorithm, but without any variable containing value of modular inverse.

Even then you will probably need to calculate modular inverse to transform diagonal matrix into identity matrix. So it is easier to use it for everything.

→ Reply