[컴퓨터구조] 모듈러 연산

캐시 기억 장치의 설계를 공부하던 중 직접 사상에서 모듈러 연산 개념이 나왔다. 이 개념에 대해 알아보고자 글을 작성한다.

 

Goal

• 모듈로 연산에 대한 이해
• 모듈로 덧셈, 뺄셈, 곱셈 연산에 대한 이해

---

모듈로 연산(Modulo Operation)이란?

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.

 

정수론에서 모듈라 연산(modular arithmetic)이란,

정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다.

 

*나눗셈 정리(division theorem)

두 정수로부터 몫과 나머지를 얻는 연산

나머지 있는 나눗셈(division with remainders) 또는 유클리드 나눗셈(Euclidean division)이라고도 한다.

 

*정의

정수 a와 양의 정수 b에 대하여

• a=bq+ra=bq+r을 만족하는 q, r이  유일하게 존재한다. (q는 몫, r은 나머지)
• 0≤r<b0≤r<b , 즉, r은 0보다 같거나 큰 정수(0또는 양의 정수)이다.

 

a : 제수(devidend)

b : 피제수(divisor)

q : 몫(quotient) => a div b == (a/b)

r : 나머지(remainder) => a mod b == (a%b)

 

 

*modular arithmetic 용어 정리

모듈로(modulo)

modulo operation에서 연산자를 의미 (mod 라고 표현, C++ 에서 %연산자가 이 역할을 한다.)

 

모듈로 연산(modulo operation)

나머지를 구하는 연산으로 A mod B 와 같은 형태로 표현한다.

 

modulus

나누는 수(제수)로 A mod B 에서, B가 modulus에 해당한다.

 

참고) modulo operation vs modular arithmetic

modulo operation : 단순히 연산만을 의미한다.

modular arithmetic : 더 포괄적인 개념으로, modulo operation을 사용한 덧셈, 뺄셈, 곱셈, 나눗셈과 같은 연산과 합동 관계 등을 포함한 개념이다.

굳이 둘의 차이를 두지 않고 같은 의미로 사용되기도 한다.

 

---

모듈로 합동(congruent modulo)

두 정수 A, B와 양의 정수 C에 대해, 다음이 성립하면 모듈로 합동이라고 한다.

• A  = B + K * C (K는 정수)

 

다음 식은 모듈로 합동의 동치이다. (기호 ≡ 로 표시)

• A ≡ B (mod C)
• A mod C = B mod C
• A = B + K * C (K는 정수) <=> A - B = K * C

*모듈로 합동이 아닌 경우 A ≢≢ B (mod C) 로 표시

 

동치 관계(equivalence relation)

동치 관계 : '논리적으로 같은' 이항관계

쉽게 말하면 '그게 그거' 라는 말이다. ('같다' 는 개념의 일반화)

 

예를 들어 다음은 동치 관계이다.

2323 와 4646 는 서로 동치이다. 약분을 했냐 안했느냐의 차이지 사실상 같은 수이기 때문이다.

 

마찬가지로, modulo 연산에서도 다음 두 수 A, B는 mod C에 대해서 동치 관계이다.

A mod C = B mod C 이면, A, B는 동치 관계에 있다.

 

동치 관계의 표기 : A ~ B
~~ 표기는 A, B가 특정 동치 관계에 의해 동치 원소가 됨을 나타냄

 

동치 관계의 성립 조건

x,y,z∈Xx,y,z∈X 에 대하여 다음 조건이 성립하면 동치 관계에 있다고 한다.

• 반사관계(reflexive) : x∼xx∼x
• 대칭관계(symmetric) : x∼yx∼y 이면 y∼xy∼x 이다.
• 추이관계(transitive) : x∼yx∼y 이고 y∼zy∼z 라면, x∼zx∼z 이다.

동치 관계의 주요 성질

• 어떤 집합을 서로 공통 부분이 없으면서도(disjoint)
• 공집합이 아닌 클래스(equivalence class)들로
• 완벽하게 분할(partition) 가능

반사적,대칭적,추이적인 세 조건을 만족한다면, (즉, 동치 관계)

이 연산으로 이루어진 각 분할들은 동치류를 이루게 됨

 

*집합에서의 분할(partition) : 모든 원소가 각자 정확히 하나의 부분집합에 속하게끔 하는 것이다.

이 부분 집합은 다음을 만족한다.

• 공집합이 아니다.
• 각 부분 집합은 서로소 집합이다. (disjoint set)
• 모든 부분 집합을 모으면 전체 집합이 된다.

 

동치류(equivalence class) : 동치 관계에 있는 값들의 집합

즉, 그게 그거인 애들끼리 모아놓은 것이다.

표기 : [x]

 

예를 들어, mod 5에서 나머지가 1인 원소들의 집합 A에서 각 원소들은 동치류이다. (같은 집합에 속해있다)

A = {... , -4, 1, 6, ...}

 

다음 그림을 통해 모듈로 합동과 동치 관계에 대해 알아보자.

위 그림은 (mod C) 에 대한 연산을 나타낸다.

이때, 조각(동치류)의 개수는 C개(0 ~ C-1)이다.

• [0] : {..., -2C, -C, 0, C, 2C, ...}
• [1] : {..., -2C+1, -C+1, 1, C+1, 2C+1, ...}
• ...
• [C-1] : {..., -3C-1, -2C-1, C-1, -1, C-1, ...}

즉, (mod M)은 0 ~ C-1 숫자에 C의 배수를 더한 값의 집합이다.

 

위 그림에서 mod C에 대한 모듈로 합동은 다음 조건을 만족 시킨다.

• 반사성 : A ≡ A (mod C)
• 대칭성 : A ≡ B (mod C) 이면, B ≡ A (mod C)
• 추이성 : A ≡ B (mod C) 이고, B ≡ C (mod C) 이면, A ≡ C (mod C) 이다.

따라서, 모듈로 합동(congruent modulo)은 동치 관계(equivalence relation)이다.

이는 분할(partition)이 가능하고 분할된 원소들이 동치류(equivalence class)를 이룸을 의미한다.

---

모듈로 연산 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)

덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현)

• 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M
• 뺄셈 : (a-b) % M = ((a%M) - (a%M)) % M
• 곱셈 : (a*b) % M = ((a%M) * (a%M)) % M

나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다.

모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b와 M이 서로소(coprime)일 때만 존재한다.

 

곱셈 역원은 다음과 같은 방법으로 구할 수 있다. 

• 페르마의 소정리 (Fermat’s Little Theorem)
• 확장 유클리드 호제법 (Extended Euclidean Algorithm)