Fő tartalom

Gyors moduláris hatványozás

Google Osztályterem

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?

Jelentkezz be

Rendezés:

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.

Számítástudomány

Tantárgy/kurzus: Számítástudomány > 2. témakör