Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
5. lecke: Moduláris aritmetika- Mi a moduláris aritmetika?
- Modulo művelet
- Játék a modulóval
- Maradékosztály
- Kongruencia reláció
- Ekvivalence reláció
- Maradékos osztásra vonatkozó tétel
- Moduláris összeadás és kivonás
- Moduláris összeadás
- Moduláris kihívás (összeadás és kivonás)
- Moduláris szorzás
- Moduláris szorzás
- Moduláris hatványozás
- Gyors moduláris hatványozás
- Gyors moduláris hatványozás
- Moduláris inverz
- Az euklideszi algoritmus
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Moduláris hatványozás
Végül vizsgáljuk meg a hatványozás tulajdonságát!
A^B mod C = ( (A mod C)^B ) mod C
Gyakran kell nagy értékű B-re kiszámítani A^B mod C-t.
Sajnos A^B nagyon nagy lesz már viszonylag kis B esetén is.
Sajnos A^B nagyon nagy lesz már viszonylag kis B esetén is.
Például:
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
Ezek a hatalmas értékek gyakran túlcsordulási hibához vezetnek a számítógépen vagy a számológépen.
Még ha nem is jön elő a hiba, sok idő kell az ilyen nagy számok mod értékének közvetlen megkereséséhez.
Még ha nem is jön elő a hiba, sok idő kell az ilyen nagy számok mod értékének közvetlen megkereséséhez.
Mit tehetünk azért, hogy csökkentsük a kifejezések méretét, és felgyorsítsuk a számításokat?
Tegyük fel, hogy ki akarjuk számolni 2^90 mod 13 értékét, de csak olyan számológépünk van, amelyik nem tud 2^50-nél nagyobb számot ábrázolni.
Íme egy egyszerű oszd meg és uralkodj stratégia:
kisebb részekre bontás
hatványozási szabályok
2^90 = 2^50 * 2^40
mod C
az egyes részek:
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
2^40 mod 13 = 1099511627776 mod 13 = 3
szorzási szabály:
a részek egyesítése:
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
Hogyan tudjuk gyorsan kiszámolni A^B mod C értékét, ha B 2 hatványa?
Hogyan tudjuk kiszámolni 7^256 mod 13-t olyan számológéppel, amelyik nem tud kezelni 7^10-nél nagyobb számot?
Feloszthatjuk 7^256-t 25, egyenként 7^10 részre és 1 olyan részre, mely értéke 7^6, de ez nem tűnik nagyon hatékonynak.
Van egy jobb módszer ...
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.