1. 모듈러 연산 (Modular Arithmetic) 이란?
ㅇ 유한개 원소 만으로 산술 연산을 하는 것
ㅇ 모듈로 n 연산 (Modulo-n Operation)
- 0 부터 n-1 까지의 제한된 정수 n개 만을 사용하는 연산
. n 이상은 다시 순환 됨 (즉, n => 0, n+1 => 1, ... 등)
- 이렇게, 순환되는 주기 n을,
. 모듈로 (Modulo 또는 Modulus,모듈러스, 법) 이라고 함
2. 모듈러 연산자 : mod
ㅇ mod => ( mod n ) => (a mod n) = r
- 여기서,
. mod : 모듈로 연산자 (modulo operator)
. a : 피 연산 입력 값 또는 피제수 (dividend)
. n : 모듈로 (modulus) 또는 제수 (divisor)
. r : 나머지 결과값 (remainder)
- 그 결과값이, 항상 n 보다 작은 양의 정수 값이 됨 (0 포함)
. 단, 결과값이 음수이면, 모듈로 값 n을 더해서 양수로 만듬 ☞ 아래 3.항 例) 참조
3. 모듈러 연산의 例
ㅇ 例) 11 (mod 3) = 2 또는 2 (mod 3) = 11 (mod 3)
- 입력 11에 대해, 3을 법으로하여 mod 연산을 하면, 출력은 2 임
- 11 이나 2 를 3 으로 나누면 나머지 2 가 되는 것이 같음 즉, 합동 임
ㅇ 例) −5 (mod 3) = 1
- 나머지가 -2가 되나, 나머지는 음수가 될 수 없으므로, 모률로 값인 3 만큼 더해서 1이 됨
- 즉, ...,-6(0),-5(1),-4(2),-3(0),-2(1),-1(2),0(0),1(1),2(2),3(0),4(1),5(2),...
ㅇ 例) −7 (mod 10) = 3
- 나머지가 -7이 되나, 모듈로 (10)을 더해, 나머지가 3이 됨
4. 모듈러 연산식, 나눗셈 관계식 간의 비교
※ 둘 간에 유사한 형식을 취하고 있으나,
- (나눗셈 관계식)은, 피제수,몫,나머지 등 요소 간에 연산 관계에 촛점을 맞춘 반면,
- (모듈러 연산)은, 오로지 나머지에 만 관심을 갖음
ㅇ 나눗셈 관계식
- a = q x n + r (입력 : a 피제수, n 제수, 출력 : q 몫, r 나머지)
- 결국, 2개 입력(a, n)과 2개 출력(q, r)을 갖는 4개 수 사이의 연산 관계식
* 대부분의 프로그래밍 언어에서는, /는 몫을 구하고, %을 나머지 연산 기호로 씀
ㅇ 모듈러 연산 : (위 나눗셈 관계식에서 오로지 나머지에 만 관심을 갖음)
- a = q x n + r = q x n + (a mod m) => r = (a mod m)
- 즉, 어떤 수를 수 n (divisor,modulus)으로 나눠 그 나머지 (residue)를 구하는 연산
- 이때, 몫 (quotient, q)은 전혀 관심을 두지 않고 오로지 나머지에 만 관심을 둠
- 결국, 2개의 입력 (제수 n 및 피제수 a)과 1개 출력 (나머지 r)을 생성하는 이항 연산 임
- 따라서, 2진수 두 개의 입력(제수,피제수)과 출력(나머지) 하나인, 이항 연산 형태로써 취급함
* 모듈러 연산의 응용 분야는,
. 수학의 정수론,추상대수학을 이용하여, 암호화,부호화 등의 특별한 응용 영역을 갖음
* 한편,
. 대부분의 프로그래밍 언어에서는, 모듈러 연산을 지원 않고,
. 모듈러 연산에 관한 로직에 대해서는, 별도로 구현해야 함
5. 모듈러 연산식, 합동식 간의 비교
※ 둘 간에 유사한 형식을 취하고 있으나,
- (모듈러 연산식)은, 연산의 결과에 중점을 둔 반면,
- (합동식)은, 방정식 처럼 취급됨
ㅇ (모듈러 연산식) b (mod n) = a, (합동식) a ≡ b (mod n)
- b : 피제수 (dividend), 정수 ← 입력
- mod : 모듈러 연산자 (modulo operator) ← 연산자
- n : 법 (法,모듈로,Modulus,Divisor), 양의 정수 ← 입력
- = : 등호 (Equivalence)
- ≡: 합동 (Congruence)
- a : 나머지 (Residue,Reminder), 0을 포함한 양의 정수 ← 결과
※ 위 관계식들은 아래 표현들과 동치/동등 임
- `정수 a,b의 차 (a - b)가 양의 정수 n 으로 나누어 떨어짐`
. 즉, n | (a - b) (☞ 약수 참조)
- `정수 a,b가, 양의 정수 n 으로 나누었을 때, 같은 나머지 r를 갖음`
. 즉, a = p n + r, b = q n + r
- `n을 법(法,Modulus)으로하여 a는 b와 합동`
. `a is congruent to b modulo n`
. `two integers a,b both are congruent modulo n`
. `a와 b는 (mod n)에 대해 합동 또는 동치 임`
- a = b + k n
. 나눗셈관계식으로써, k는 임의 정수
- `n을 법으로하는 a와 n을 법으로하는 b와 같음`
. (a mod n) = (b mod n)
6. [참고사항]
ㅇ 모듈러 2 연산, 모듈로 n 연산 ☞ mod-2 (모듈러-2 덧셈, 모듈러-2 곱셈), mod-n 참조
- (특히, mod-2 연산은 응용에서 많이 쓰임)
ㅇ 모듈로 연산의 결과는, 하나의 집합을 형성하게 되는데,
- 이때의 집합은, 모듈로 n에 대해 수많은 잉여류가 존재 함
. 각각의 모든 정수를 양의 정수 m 로 나누었을 때,
. 나머지가 r 이 되는 수들의 모음
. 즉, 나머지가 같게 되는 수많은 정수들의 집합 ☞ 잉여류, 잉여계 참조
ㅇ 모듈러 연산에서, 역원
- 종종, 모듈러 연산을 할 때에, 그 연산에 대해 어떤 수의 역원을 계산할 필요가 많음