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í mocnění
Nakonec prozkoumejme, jak se v modulární aritmetice umocňuje:
A^B mod C = ( (A mod C)^B ) mod C
Často potřebujeme spočítat A^B mod C pro velké hodnoty B.
A^B bohužel nabývá vysokých hodnot i pro relativně malé hodnoty B.
A^B bohužel nabývá vysokých hodnot i pro relativně malé hodnoty B.
Například:
2^90 = 1 237 940 039 290 000 000 000 000 000
7^256 = 2 213 595 400 050 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 83 794 038 078 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 721 264 246 243 000 000 000 000 000
Tyto velké hodnoty způsobují v kalkulačkách a počítačích chybu overflow, protože jsou mimo rozsah hodnot, se kterými si je daný počítač schopen poradit.
I kdyby tuto chybu neměly, trvalo by neuvěřitelně dlouho nalézt „mod“ takových velkých hodnot přímo.
I kdyby tuto chybu neměly, trvalo by neuvěřitelně dlouho nalézt „mod“ takových velkých hodnot přímo.
Co můžeme udělat, abychom snížili velikost zahrnutých členů a zrychlili tak výpočet?
Řekněme, že chceme spočítat 2^90 mod 13, ale naše kalkulačka nezvládne pracovat s hodnotami většími než 2^50.
Můžeme to vyřešit pomocí jednoduché strategie rozděl a panuj:
menší části
vlastnosti mocnin
2^90 = 2^50 * 2^40
mod C
každá část
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
2^40 mod 13 = 1099511627776 mod 13 = 3
vlastnosti násobení
zkombinování
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12
Jak lze snadno spočítat A^B mod C, je-li B mocnina čísla 2 ?
Jak lze spočítat 7^256 mod 13 pomocí kalkulačky, která nezvládne pracovat s čísly většími než 7^10 ?
Mohli bychom 7^256 rozdělit na 25 částí 7^10 a 1 část 7^6, ale to by nebylo příliš efektivní.
Je zde lepší způsob…
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.