Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 5: Arytmetyka modularna- Co to jest arytmetyka modularna?
- Operator modulo
- Wyzwanie modulo
- Przystawanie modulo
- Relacja przystawania
- Relacje równoważności
- Twierdzenie o reszcie z dzielenia
- Dodawanie i odejmowanie modularne
- Dodawanie modularne
- Wyzwanie modulo (dodawanie i odejmowanie)
- Mnożenie modularne
- Mnożenie modularne
- Potęgowanie modularne
- Szybkie potęgowanie modularne
- Szybkie potęgowanie modularne
- Odwrotność modularna
- Algorytm Euklidesa
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Mnożenie modularne
Zbadajmy własności mnożenia w arytmetyce modulo
(A * B) mod C = (A mod C * B mod C) mod C
Przykład mnożenia:
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
Dowód mnożenia modularnego
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
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji