Hlavní obsah
Kurz: Informatika > Kapitola 1
Lekce 5: Modulární aritmetika- Co je to modulární aritmetika?
- Operátor modulo
- Výzva Modulo
- Kongruence modulo
- Kongruence modulo
- Relace ekvivalence
- Věta o dělení se zbytkem
- Modulární sčítání a odčítání
- Modulární sčítání
- Výzva modulo (sčítání a odčítání)
- Modulární násobení
- Modulární násobení
- Modulární mocnění
- Rychlé modulární umocňování
- Rychlé modulární umocňování
- Modulární inverze
- Euklidův algoritmus
Modulární inverze
Co je to inverze?
Vzpomeň si, že číslo, vynásobené svou inverzní (převrácenou) hodnotou, je rovno 1. Ze základní aritmetiky víme:
- Inverzní číslo (převrácená hodnota) k číslu A je 1/A, protože A * 1/A = 1 (např. převrácená hodnota 5 je 1/5)
- Všechna reálná čísla kromě 0 mají k sobě inverzní číslo.
- Násobení čísla převrácenou hodnotou A je ekvivalentní vydělením A (např. 10/5 je to samé jako 10* 1/5)
Co je modulární inverze?
V modulární aritmetice nemáme operaci dělení. Máme však modulární inverzi.
- Modulární inverze A (mod C) je A^-1.
- (A * A^-1) ≡ 1 (mod C) nebo ekvivalentně (A * A^-1) mod C = 1
- Jedině čísla nesoudělná s C (čísla, jejichž jediný společný dělitel s C je 1) mají modulární inverzi (mod C).
Jak nalézt modulární inverzi
Naivní metoda nalezení modulární inverze k A (mod C) je:
Krok 1. Spočítej A * B mod C pro hodnoty B od 0 do C-1.
Krok 2. Modulární inverze A mod C je taková hodnota B, pro kterou platí A * B mod C = 1.
Všimni si, že výraz B mod C může mít jen celočíselnou hodnotu od 0 do C-1, testování pro vyšší hodnoty B je tedy zbytečné.
Příklad: A=3, C=7
Krok 1. Spočítej A * B mod C pro hodnoty B od 0 do C-1.
3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ Nalezli jsme inverzi.
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Krok 2. Modulární inverze A mod C je hodnota B taková, pro kterou platí A * B mod C = 1
5 je modulární inverze 3 mod 7, jelikož 5*3 mod 7 = 1.
Jednoduché!
Spočítejme další příklad. Tentokrát se nám inverzi nepodaří najít.
Příklad: A=2 C=6
Krok 1. Spočítej A * B mod C pro hodnoty B od 0 do C-1
2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)
Krok 2. Modulární inverze A mod C je hodnota B taková, pro kterou platí A * B mod C = 1
Pro žádnou hodnotu B neplatí A * B mod C = 1. Proto A nemá modulární inverzi (mod 6).
To z toho důvodu, že 2 není nesoudělné s 6 (mají společného dělitele – 2).
To z toho důvodu, že 2 není nesoudělné s 6 (mají společného dělitele – 2).
Tato metoda se zdá býti pomalou…
Existuje mnohem rychlejší metoda hledání modulární inverze A (mod C), kterou probereme v dalších článcích o Eukleidově algoritmu.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.