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

Gyors moduláris hatványozás

Hogyan tudjuk gyorsan kiszámolni A^B mod C-t, ha B 2 hatványa?

A moduláris szorzás szabályát alkalmazva:
azaz A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
Ezt felhasználva gyorsan ki tudjuk számolni 7^256 mod 13 értékét
7^1 mod 13 = 7
7^2 mod 13 = (7^1 · 7^1) mod 13 = (7^1 mod 13 · 7^1 mod 13) mod 13
Az 7^1 mod 13-ra kapott előző eredményt behelyettesítjük ebbe az egyenletbe.
7^2 mod 13 = (7 · 7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
A 7^2 mod 13-ra kapott előző eredményt behelyettesítjük ebbe az egyenletbe.
7^4 mod 13 = (10 · 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 · 7^4) mod 13 = (7^4 mod 13 · 7^4 mod 13) mod 13
A 7^4 mod 13-ra kapott előző eredményt behelyettesítjük ebbe az egyenletbe.
7^8 mod 13 = (9 · 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
Igy folytatjuk, mindig behelyettesítjük az előző eredményt az egyenletbe.
...5 iteráció után célhoz érünk:
7^256 mod 13 = (7^128 · 7^128) mod 13 = (7^128 mod 13 · 7^128 mod 13) mod 13
7^256 mod 13 = (3 · 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
Sikerült szert tenni egy olyan eljárásra, amivel gyorsan ki tudjuk számolni A^B mod C-t, ha B 2 hatványa.
De abban az esetben is szükségünk van egy gyors eljárásra, ha B nem 2 hatványa.

Hogyan tudjuk A^B mod C-t gyorsan kiszámolni tetszőleges B esetén?

1. lépés: oszd fel B-t 2 hatványaira úgy, hogy átváltod binárisra!

Kezdd a jobb szélső számjeggyel, legyen k=0, és minden egyes számjegyre:
  • Ha a számjegy 1, akkor szükség lesz egy 2^k összetevőre, egyébként nem.
  • Növeld meg k-t 1-el, és vedd a következő számjegyet!

2. lépés: számold ki a B-nél kisebb vagy egyenlő 2-hatványok mod C értékeit!

5^1 mod 19 = 5
5^2 mod 19 = (5^1 · 5^1) mod 19 = (5^1 mod 19 · 5^1 mod 19) mod 19
5^2 mod 19 = (5 · 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 · 5^2) mod 19 = (5^2 mod 19 · 5^2 mod 19) mod 19
5^4 mod 19 = (6 · 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 · 5^4) mod 19 = (5^4 mod 19 · 5^4 mod 19) mod 19
5^8 mod 19 = (17 · 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 · 5^8) mod 19 = (5^8 mod 19 · 5^8 mod 19) mod 19
5^16 mod 19 = (4 · 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 · 5^16) mod 19 = (5^16 mod 19 · 5^16 mod 19) mod 19
5^32 mod 19 = (16 · 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 · 5^32) mod 19 = (5^32 mod 19 · 5^32 mod 19) mod 19
5^64 mod 19 = (9 · 9) mod 19 = 81 mod 19
5^64 mod 19 = 5

3. lépés: használd a moduláris szorzás szabályát a kiszámolt mod C értékek kombinálásához!

5^117 mod 19 = ( 5^1 · 5^4 · 5^16 · 5^32 · 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 · 5^4 mod 19 * 5^16 mod 19 · 5^32 mod 19 · 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 · 17 · 16 · 9 · 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1

Megjegyzés:

Léteznek más optimalizációs eljárások, de ezek kívül esnek a jelen lecke fókuszán. Amikor a kriptográfiában moduláris hatványozást végzünk, gyakran előfordul B > 1000 bit hosszú kitevő.

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.