Hlavní obsah
Informatika
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í násobení
Prozkoumejme vlastnost násobení pro modulární aritmetiku:
(A * B) mod C = (A mod C * B mod C) mod C
Příklad násobení:
Nechť A=4, B=7, C=6
Ověřme: (A * B) mod C = (A mod C * B mod C) mod C
LSR= Levá strana rovnice
PSR= Pravá strana rovnice
LSR = (A * B) mod C
LSR = (4 * 7) mod 6
LSR = 28 mod 6
LSR = 4
PSR = (A mod C * B mod C) mod C
PSR = (4 mod 6 * 7 mod 6) mod 6
PSR = (4 * 1) mod 6
PSR = 4 mod 6
PSR = 4
LSR = PSR = 4
Důkaz vztahu pro modulární násobení
Dokážeme platnost (A * B) mod C = (A mod C * B mod C) mod C.
Musíme ukázat, že platí LHS = RHS.
Z Věty o dělení se zbytkem lze psát A a B jako:
A = C * Q1 + R1, kde 0 ≤ R1 < C a Q1 je celé číslo. A mod C = R1
B = C * Q2 + R2, kde 0 ≤ R2 < C a Q2 je celé číslo. B mod C = R2
LSR = (A * B) mod C
LSR = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LSR = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
LSR = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C
Násobků C se zbavíme působením mod C.
LSR = (R1 * R2) mod C
Nyní se pusťme do PSR.
PSR = (A mod C * B mod C) mod C
PSR = (R1 * R2 ) mod C
Tedy PSR = LSR
LSR = PSR = (R1 * R2 ) mod C
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.