Algoritmus pro inverzi nad Zp

Úloha číslo: 2588

Je správně následující návod?

Dotaz: "Zajímalo by mě, jak lze v Matlabu počítat v konečných tělesech.

Například, lze nějakým pěkným způsobem násobit nebo invertovat matice, jejichž koeficienty jsou z konečného tělesa, řekněme z tělesa zbytkových tříd modulo prvočíslo?"

Odpověď: "Kdysi jsem to potřeboval. Násobení není žádný problém. Vypočítej normální součin a výsledek vem modulo prvočíslo. To se snadno dokáže. Myslím, že jsem zkoušel podobný postup pro inverzi. Algoritmus (jestli se správně pamatuju) vypadal takto:

1. Spočítej inverzi;
2. Vynásob inverzi determinantem původní matice;
3. Výsledek přepočítej modulo prvočíslo.

Přišel jsem na tento algoritmus intuicí a nikdy jsem ho nezkusil dokázat, ale fungoval skvěle."

  • Řešení

    V druhém kroku je vypočtena \(\det(\mathbf A)\mathbf A^{-1}\), tedy adjungovaná matice nad \(\mathbb R\).

    Faktorizací podle \(p\) se ve třetím kroku získá adjungovaná matice nad \(\mathbb Z_p\).

    V případě, že \(\det(\mathbf A)\ne 1\), v našem případě \(\det(\mathbf A)\not\equiv 1 \pmod p\), jsou inverzní a adjungovaná matice různé.

    Abychom dostali inverzní matici nad \(\mathbb Z_p\) je třeba adjungovanou matici ještě vydělit determinantem.

    Algoritmus mohl fungovat skvěle leda tak nad \(\mathbb Z_2\)

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze