Modular Arithmetic
모듈러 연산은 어떤 수를 특정한 값(모듈러, modulus)으로 나눈 나머지를 계산하는 연산으로, 쉽게 말해 나머지 연산이다.
A mod B = R- A : 나눠지는 수 (피제수, Dividend)
- B : 나누는 수 (제수, Modulus)
- R : 나머지 (Remainder)
덧셈, 뺄셈, 곱셈의 모듈러 연산
모듈러 연산에서 덧셈, 뺄셈, 곱셈은 분배 법칙을 따른다. 연산 후 모듈러를 취하는 것과, 각각 모듈러를 취한 후 연산하는 것이 동일하다는 뜻이다.
- 덧셈
(A + B) mod C = [(A mod C) + (B mod C)] mod C- 뺄셈 (음수가 나올 경우, C를 더해서 양수로 만들 수 있음)
(A - B) mod C = [(A mod C) - (B mod C) + C] mod C- 곱셈
(A * B) mod C = [(A mod C) * (B mod C)] mod C
거듭제곱(지수 연산)의 모듈러 연산
(A^B) mod C = [(A mod C)^B] mod C
예제
- 모듈러 연산 X
(6⁴) mod 5
= (6 * 6 * 6 * 6) mod 5
= 1296 mod 5
= 1
- 모듈러 연산
(6⁴) mod 5
= [(6 mod 5)⁴] mod 5
= (1⁴) mod 5
= 1
모듈러 역원 (Modular Inverse)
어떤 수 A에 대해 다음을 만족하는 X를 찾는 것을 뜻한다. 즉, A를 곱해서 1이 되는 숫자 X가 모듈러 역원이다. 모듈러 역원이 존재하려면 A와 M의 서로소(최대공약수)가 1이어야 한다.
A * X = 1 mod M
활용
(1) 큰 수 연산 (빠른 거듭제곱)
- 시간복잡도가 O(log n)
(2) 암호학 (RSA 암호 알고리즘)
- RSA 암호화에서 공개 키와 개인 키를 생성할 때 모듈러 연산을 사용한다.
- 큰 소수를 기반으로 하기 때문에 해킹이 어려운, 보다 강력한 보안을 제공한다.
(3) 해싱과 데이터 구조
- 해시 테이블에서 충돌 방지를 위해 모듈러 연산을 사용한다.
- 원형 큐나 해시 함수 등 특정한 범위 안에서 값이 순환하는 데이터 구조에서 사용된다.
알고리즘
728x90
반응형