If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

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.

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.

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
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

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.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.