모듈러 연산

모듈러 연산 (나머지 연산)은 알고리즘에서 자주 쓰이는 개념입니다.

모듈러 연산은 정수론에서 나온 개념이라 깊게 이해하려면 정수론을 조금 들여봐야하나, 지금의 저는 수학자가 아니에요.

 

간단하게 개념들만 알아봅시다.

---

모듈러 연산(%) 이란?

나머지를 구하는 연산.

10 % 3 == 1 -> 10을 3으로 나누었을 때의 나머지, 즉 1

4 % 2 == 0 -> 4를 2로 나누었을 때의 나머지, 즉 0

 

혹은 %를 mod 라고 표현하기도 합니다.

10 mod 3 == 1

4 mod 2 == 0

 

---

모듈러 연산의 합동 법칙 (Modular congruent)

어떤 두 정수 a, b가 모듈러 m에 대해 합동이라면, 아래와 같이 나타낼 수 있습니다.

a ≡ b (mod m)

 

이를 더 풀어서 설명하면, 결국 모듈러 연산에서 합동이란 같은 m으로 나누었을 때, 나머지가 같다는 것을 의미합니다.

a mod m == b mod m (즉, a와 b를 각각 m으로 나누었을 때, 나머지가 같다!)

 

이런 모듈러 연산의 합동 관계로 인해 덧셈, 뺄셈, 곱셈 등의 연산이 합동 관계를 유지하게 됩니다.

 

1. 덧셈 : (a ≡ b (mod m)) 이고 (c ≡ d (mod m)) ⇒ (a + c) ≡ (b + d) (mod m) 

2. 뺄셈: (a ≡ b (mod m)) 이고 (c ≡ d (mod m)) ⇒ (a − c) ≡ (b − d) (mod m)

3. 곱셈: (a ≡ b (mod m)) 이고 (c ≡ d (mod m)) ⇒ (a ⋅c) ≡ (b ⋅ d) (mod m)

 

1번의 경우만 예시를 들어볼게요. 

7 ≡ 2 (mod5), 11 ≡ 1 (mod 5) 이면,

(7 + 11) ≡ (2 + 1) (mod 5)

즉, 18 ≡ 3 (mod 5) 가 됩니다. 

 

사실 조금만 논리적으로 생각해봐도 당연한 말들이긴 합니다.

같은 나머지끼리 더하거나, 빼거나, 곱한것에 모듈러 연산을 적용하면 당연히 같은 결과가 나오겠죠.

 

 

참고로, a와 b의 합동 관계를 나머지 연산을 해볼 필요 없이 더욱 쉽게 알아내는 방법이 있습니다.

a − b = kn

 

가 성립하면 됩니다. 증명은 2가지 방법으로 간단하게 할 수 있습니다.

(1) 위의 식의 양변은 a - b 가 결국 n의 배수라는 것을 의미합니다.
그리고 이는, a와 b의 나머지가 같다는 뜻이며 합동으로 귀결됩니다.

 

(어떤 숫자의 배수라는 것은 나머지가 0이라는 뜻이고, a - b 가 나머지가 없으려면 a와 b의 나머지가 같기 때문에, 

a의 나머지 - b의 나머지 = 나머지 0 이 되는 것이 됩니다)

 

 혹은 나머지 연산을 직접 적용하여 생각해볼 수도 있습니다.

 

(2) 위의 식 양변에 % n을 적용하면 (a - b) % n == 0 이 됩니다. 
이 또한 마찬가지로 a와 b의 나머지가 같다는 뜻이며 합동으로 귀결됩니다.

 

---

모듈러 연산의 특징 (덧셈, 뺄셈, 나눗셈)

당연히 모듈러 m이 0이 되면 안되고,

단순한 형태의 분배 법칙은 성립하지 않습니다. 즉, (a + b) % c !== (a % c) + (b % c) 입니다.

 

그냥 3가지 기억하면 됩니다.

 

1. (a+b) % m = ((a % m) + (b % m)) % m

2. (a−b) % m = ((a%m) − (b%m) + m) % m

3. (a×b) % m = ((a % m)×(b % m)) %m

 

여기서 참고할만한 점은 2번입니다. 2번에 m은 왜 더할까요? (실수는 아닙니다)

원리 설명은 미루고 결론만 말하자면 음수인 나머지가 도출되는 경우를 방지하기 위해서입니다.

 

---

컴퓨터 공학에서 모듈러 연산을 사용하기 위한 핵심 개념

모듈러 연산은 1번을 하든, 100번을 하든 결과는 같다는 것입니다.

특정 수 a를 %n을 한다면, 그 결과는 항상 0~(n-1) 중 하나입니다. 

그리고 그 결과를 %n하면 값이 변하진 않겠죠. 따라서 몇번이든 할 수 있습니다.

 

그럼에도 불구하고 위의 모듈려 연산 법칙이 존재하는 이유는, 중간 중간 모듈러 연산을 해줄 수 있다라는 것을 인지하기 위해서입니다.

만약 10억 * 10억이면 long long 타입으로도 커버가 안되는 매우 큰 수가 탄생하는데, 그 전에 각각에 모듈러 연산을 하고 전체에 모듈러 연산을 한번 더 적용하는 연산 법칙을 적용하면 숫자를 충분히 다룰 수 있게 되죠.

---

컴퓨터 공학에서 모듈러 연산을 사용하는 경우 

 

• 짝수/홀수 판별
• 배수 판별
• 요일 계산
• 원형 큐에서 인덱스 순환
• 큰 수 연산에서 모듈러 연산 사용 (오버플로우 방지)

 

대충 감이 오시나요?

물론 해시값 도출, 암호화 알고리즘 등 다양한 곳에서 쓰이지만 기본적이고 범용적으로 쓰이는 용도만 정리해봤어요.

 

---

 

모듈러 역원을 구하는 방식(나누기에 모듈러 연산을 적용하는 방식), 음수에 모듈러 연산을 적용하는 방식은 필요하면 정리하겠습니다. 글 여기서 마치겠습니다.