모듈러 연산의 분배 법칙 (곱셈)

모듈러 연산의 분배 법칙

---

모듈러 연산의 분배 법칙에 따라 다음이 성립한다.

$(A \times B) \ mod \ N$ = $(A \ mod \ N) \times (B \ mod \ N) \ mod \ N$

증명

---

A와 B는 다음과 같이 쓸 수 있다.

$A = aC + m$

$B = bC + n$

(C는 몫, m과 n은 나머지)

따라서 $(A \times B) \ mod \ C$ 를 다음과 같이 표현할 수 있다.

= $((aC + m) \times (bC + n)) \ mod \ C$

= $((abC^2 + anC + bmC + mn)) \ mod \ C$

= $(mn) \ mod \ C$

(나머지 연산자의 성질에 따라 C로 묶인 값은 제거 된다)

→ C를 약수로 포함하고 있기 때문에 나머지가 0이 되고 mn만 남는다.

$(A \ mod \ N) \times (B \ mod \ N) \ mod \ N$

= $((aC + m) \ mod \ C) \times ((bC + n) \ mod \ C) \ mod \ C$

(마찬가지로 나머지 연산자의 성질에 따라 C로 묶인 값은 제거 된다)

= $(mn) \ mod \ C$

두 식 모두 $(mn) \ mod \ C$ 로 같기 때문에

$(A \times B) \ mod \ N$ = $(A \ mod \ N) \times (B \ mod \ N) \ mod \ N$ 이다.

참고자료

---

https://lypicfa.tistory.com/638

Uploaded by N2T