나머지 연산 (Modular Arithmetic)
어떠한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산
일반적으로 두 정수(A, B)를 나누면 몫(Q)과 나머지(R)가 구해진다.
A / B = Q 나머지 R
나머지 연산은 나눈 값에서 나머지만 구하는 연산으로, 모듈러 연산자를 사용하여 다음과 같이 표현한다.
A mod B = R
이때 A 모듈러 B는 R과 같다, 라고 말한다. (B는 모듈)
프로그래밍 언어에서는 %를 사용하여 A % B
으로 표현한다.
시계로 이해하기
A를 1씩 증가시키며 B로 나누면 나머지 값이 0
부터 B-1
까지 반복된다.
이는 시계에서 시침이 돌아가는 과정와 유사하다. (1 mod 12 = 1, 2 mod 12 = 2, 11 mod 12 = 11, 12 mod 12 = 0, 13 mod 12 = 1)
- 아날로그 시계는 원에 1부터 12까지 시간이 적혀있다. 여기서 12를 0으로 바꾸면 모듈(B)이 12인 원이 된다.
- A를 3이라고 하면, 0에서 시작하여 3만큼 시침을 돌린다. (양수면 시계 방향, 음수면 반시계 방향)
- 멈추는 지점에 위치한 숫자가 해가 된다. (3 mod 12 = 3)
- 음수 계산 예시: -3 mod 5 = -(3 mod 5) + 5 = -3 + 5 = 2
합동 (Congruent)
두 숫자 A와 B를 C로 각각 모듈러 연산을 했을 때 결과값이 같다면 A와 B는 모듈 C에 대한 합동 관계라고 한다.
A mod C = B mod C
가 성립하면 합동 관계 A ≡ B mod C
로 표현할 수 있다.
동치 관계
모듈로 연산을 통해 파이(원)를 동일한 크기를 가진 조각으로 나누는 개념
파이를 어떻게 조각들(동치류)로 분할할지 규정한다.
파이를 모듈 C로 나누었을 때 같은 조각(동치류)에 속하는 숫자들은 동치 관계를 갖는다.
한 조각 안에 있는 어떤 두 값의 차이는 C의 배수이다.
파이 조각들은 모듈 C에 대한 합동 관계를 가지며, 이것이 동치 관계를 형성한다.
특성
- 반사성 (Reflexivity): A가 A와 관계가 있다.
A ≡ A mod C
- 대칭성 (Symmetry): A가 B와 관계가 있다면, B도 A와 관계가 있다.
A ≡ B mod C 이면 B ≡ A mod C
- 추이성 (Transitivity): A가 B와 관계가 있고, B와 D가 관계가 있다면, A와 D도 관계가 있다.
A ≡ B mod C 이고 B = D mod C 이면 A ≡ D mod C
분배 법칙
덧셈 또는 뺄셈과 나머지 연산 사이의 관계를 설명하는 수학적 법칙
두 숫자 A와 B를 C로 나누었을 때 몫과 나머지를 표현하면 다음과 같다.
A = Q1 * C + R1
B = Q2 * C + R2
덧셈/뺄셈/곱셈 분배 법칙 성질
(A ± B) mod C = (A mod C ± B mod C) mod C
(A × B) mod C = (A mod C × B mod C) mod C
- 증명
LHS = 식의 좌변
RHS = 식의 우변
LHS = (A ± B) mod C
= (C(Q1 ± Q2) ± R1 ± R2) mod C // 나머지 연산이므로 몫은 0
= (R1 ± R2) mod C
RHS = (A mod C ± B mod C) mod C
= (R1 ± R2) mod C
LHS = RHS = (R1 ± R2) mod C
거듭제곱 성질
A^B mod C = ((A mod C)^B) mod C
- B 값에 따라 오버플로우가 발생할 수 있어 분할 정복을 사용해야 한다.
Reference
https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic
https://gosamy.tistory.com/75
https://dev-min.tistory.com/1
https://developer-mac.tistory.com/84
https://codingram.tistory.com/26
https://velog.io/@yyeonggg/모듈러-연산Modular-Arithmetic
https://velog.io/@gidskql6671/나머지Modulo-연산-분배법칙
https://gliver.tistory.com/5
https://www.crocus.co.kr/1231
https://sskl660.tistory.com/75
https://velog.io/@sw801733/나머지-연산-분배법칙-모듈러-연산