Conţinutul principal
Curs: Teoria informației și criptografie > Unitatea 2
Lecția 5: Clase de resturi- Să învățăm despre operatorul modulo!
- Operatorul modulo
- Congruența modulo
- Relația de congruență
- Relații de echivalență
- Teorema împărțirii cu rest
- Adunarea și scăderea claselor de resturi modulo n
- Adunarea modulară (modulo sau clase de resturi)
- Înmulțirea modulară (modulo sau în clase de resturi)
- Înmulțirea modulară (modulo sau în clase de resturi)
- Ridicare la putere și resturi
- Ridicare rapidă la putere modulară
- Inverse modulare
- Algoritmul lui Euclid
© 2024 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
Ridicare rapidă la putere modulară
Cum putem calcula rapid A^B mod C dacă B este o putere a lui 2?
Folosind regulile de la înmulțirea modulară:
ex. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
Putem folosi această regulă pentru a calcula 7^256 mod 13 rapid
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
Putem înlocui rezultatul nostru anterior cu 7^1 mod 13 în această egalitate.
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
Putem înlocui rezultatul nostru anterior cu 7^2 mod 13 în această egalitate.
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
Putem înlocui rezultatul nostru anterior cu 7^4 mod 13 în această egalitate.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
Continuăm în acest mod, înlocuind rezultatele anterioare în ecuaţiile noastre.
...după 5 iterații obținem:
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
Acum avem o metodă de a calcula rapid A^B mod C, cu condiția ca B să fie o putere a lui 2.
Cu toate acestea, avem nevoie și de o metodă pentru ridicarea la putere modulară rapidă atunci când B nu este o putere a lui 2.
Cum putem calcula rapid A^B mod C pentru orice B?
Pasul 1: Împărțim B în puteri ale lui 2 prin scrierea în format binar (în baza doi)
Începând de la cea mai din dreapta cifră, se consideră k=0 iar pentru fiecare cifră:
- Dacă cifra este 1, avem nevoie de o parte pentru 2^k, altfel nu
- Adunăm 1 la k și ne mutăm spre stânga, la următoarea cifră
Pasul 2: Calculăm mod C din puterile lui doi ≤ B
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
Pasul 3: Utilizăm proprietățile înmulțirii modulare, pentru a combina valorile mod C deja calculate
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
Observații:
Există și alte tehnici de optimizare, dar acestea nu fac obiectul acestui articol. Trebuie menționat că pentru ridicarea la putere modulară, în criptografie, se pot folosi exponenți B > 1000 biți.
Vrei să te alături conversației?
Nici o postare încă.