Conţinutul principal

Înmulțirea modulară (modulo sau în clase de resturi)

Să explorăm proprietățile înmulțirii în contextul aritmeticii modulare:

(A * B) mod C = (A mod C * B mod C) mod C

Fie A=4, B=7, C=6

Hai să verificăm dacă: (A * B) mod C = (A mod C * B mod C) mod C

PSE= Partea Stângă a Ecuației

PDE= Partea Dreaptă a Ecuației

PSE = (A * B) mod C

PSE = (4 * 7) mod 6

PSE = 28 mod 6

PSE = 4

PDE = (A mod C * B mod C) mod C

PDE = (4 mod 6 * 7 mod 6) mod 6

PDE = (4 * 1) mod 6

PDE = 4 mod 6

PDE = 4

PSE = PDE = 4

Vom demonstra că (A * B) mod C = (A mod C * B mod C) mod C

Trebuie să arătăm că PSE = PDE

A = C * Q1 + R1, unde 0 ≤ R1 < C și Q1 este un număr întreg. A mod C = R1

B = C * Q2 + R2, unde 0 ≤ R2 < C și Q2 este un număr întreg. B mod C = R2

PSE = (A * B) mod C

PSE = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

PSE = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

PSE = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

Putem elimina multiplii lui C când efectuăm operația modulo C

PSE = (R1 * R2) mod C

În continuare, hai să calculăm PDE

PDE = (A mod C * B mod C) mod C

PDE = (R1 * R2 ) mod C

Prin urmare, PDE = PSE

PSE = PDE = (R1 * R2 ) mod C

Ordonare după:

Nici o postare încă.