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 la putere și resturi
În sfârșit, hai să explorăm restul unei puteri:
A^B mod C = ( (A mod C)^B ) mod C
De multe ori vrem să calculăm A^B mod C pentru valori mari ale lui B.
Din păcate, A^B devine foarte mare chiar și pentru valori destul de mici ale lui B.
Din păcate, A^B devine foarte mare chiar și pentru valori destul de mici ale lui B.
De exemplu:
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
Aceste valori uriașe determină calculatoarele noastre să returneze erori de tip overflow.
Chiar și dacă nu s-ar întâmpla asta, ar fi nevoie de mult timp pentru a găsi direct restul împărțirii acestor numere imense.
Chiar și dacă nu s-ar întâmpla asta, ar fi nevoie de mult timp pentru a găsi direct restul împărțirii acestor numere imense.
Ce putem face pentru a reduce mărimea factorilor implicați și pentru a face calculul mai rapid?
Să presupunem că vrem să calculăm 2^90 mod 13, dar avem un calculator care nu poate stoca numere mai mari de 2^50.
Iată o strategie simplă, numită împarte și cucerește (în engleză, divide and conquer):
părți mai mici
reguli pentru puteri
2^90 = 2^50 * 2^40
mod C
fiecare parte
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
2^40 mod 13 = 1099511627776 mod 13 = 3
proprietăți ale înmulțirii
combinăm părțile
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
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
Cum putem calcula rapid A^B mod C dacă B este o putere a lui 2 ?
Cum putem calcula 7^256 mod 13 folosind un calculator care nu poate stoca numere mai mari de 7^10 ?
Am putea împărți 7^256 în 25 părți de 7^10 și o parte de 7^6, dar acest lucru nu ar fi foarte eficient.
Există o metodă mai bună....
Vrei să te alături conversației?
Nici o postare încă.