주요 내용
모듈로 곱셈
모듈러 연산의 곱셈 성질을 알아봅시다:
(A * B) mod C = (A mod C * B mod C) mod C
곱하기 예제
A=4, B=7, C=6일 때
(A * B) mod C = (A mod C * B mod C) mod C 가 맞는지 알아봅시다
LHS= 식의 좌변
RHS = 식의 우변
LHS = (A * B) mod C
LHS = (4 * 7) mod 6
LHS = 28 mod 6
LHS = 4
RHS = (A mod C * B mod C) mod C
RHS = (4 mod 6 * 7 mod 6) mod 6
RHS = (4 * 1) mod 6
RHS = 4 mod 6
RHS = 4
LHS = RHS = 4
모듈로 곱셈의 증명
(A * B) mod C = (A mod C * B mod C) mod C임을 증명해 봅시다
LHS = RHS임을 보여야 합니다.
몫-나머지 정리(quotient remainder theorem)에 의해서 A와 B 를 다음과 같이 쓸 수 있습니다:
A = C * Q1 + R1 이때 0 ≤ R1 < C 이고 Q1는 정수이다. A mod C = R1
B = C * Q2 + R2 이때 0 ≤ R2 < C이고 Q2 는 정수이다. B mod C = R2
LHS = (A * B) mod C
LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C
mod C로 정리하면 C의 배수를 없앨 수 있습니다.
LHS = (R1 * R2) mod C
다음은 RHS를 정리해봅시다.
RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C
따라서 RHS = LHS 입니다.
LHS = RHS = (R1 * R2 ) mod C