Główna zawartość

Mnożenie modularne

Zbadajmy własności mnożenia w arytmetyce modulo

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

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

Sprawdźmy: (A * B) mod C = (A mod C * B mod C) mod C

LSR= Lewa Strona Równania

PSR= Prawa Strona Równania

LSR = (A * B) mod C

LSR = (4 * 7) mod 6

LSR = 28 mod 6

LSR = 4

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

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

PSR = (4 * 1) mod 6

PSR = 4 mod 6

PSR = 4

LSR = PSR = 4

Udowodnimy, że (A * B) mod C = (A mod C * B mod C) mod C

Musimy pokazać, że LSR = PSR

Korzystając z twierdzenia o dzieleniu z resztą możemy zapisać A i B jako:

A = C * Q1 + R1 gdzie 0 ≤ R1 < C i Q1 jest liczbą całkowitą. A mod C = R1

B = C * Q2 + R2 gdzie 0 ≤ R2 < C i Q2 jest liczbą całkowitą. B mod C = R2

LSR = (A * B) mod C

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

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

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

Stosując operację mod C możemy pozbyć się wielokrotności C

LHS = (R1 * R2) mod C

Następnie obliczmy RHS

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

RHS = (R1 * R2 ) mod C

A zatem, RHS = LHS

LHS = RHS = (R1 * R2 ) mod C

Sortuj według

Na razie brak głosów w dyskusji