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