Блог пользователя triploblastic

gaussian elimination modulo a prime
Автор triploblastic, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить