모듈러 산술

모듈러 산술 (Modular Arithmetic) 은 정수를 특정 수(모듈러스, modulus)로 나눈 나머지에 주목하여 수행하는 산술 체계이다. 시계 산술이라고도 불리며, 정수론의 핵심적인 개념 중 하나이자 컴퓨터 과학, 암호학 등 다양한 분야에서 널리 응용된다.

정의

정수 a와 b가 있고, 양의 정수 m(모듈러스)이 주어졌을 때, a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같다면, a와 b는 모듈러 m에 대해 합동(congruent)이라고 정의한다. 이를 수식으로 표현하면 다음과 같다:

a ≡ b (mod m)

이는 (a - b)가 m의 배수라는 의미와 동치이다. 즉, 어떤 정수 k에 대해 a - b = km 이 성립한다.

연산

모듈러 산술에서는 일반적인 산술 연산(덧셈, 뺄셈, 곱셈)을 모듈러 연산과 함께 수행할 수 있다. 모듈러 연산은 연산 결과를 모듈러스로 나눈 나머지를 취하는 것이다.

• 덧셈: (a + b) mod m ≡ (a mod m + b mod m) mod m
• 뺄셈: (a - b) mod m ≡ (a mod m - b mod m) mod m
• 곱셈: (a * b) mod m ≡ (a mod m * b mod m) mod m

나눗셈의 경우, 모듈러 역원을 사용하여 곱셈으로 변환하여 수행한다. a의 모듈러 m에 대한 역원(modular inverse)은 a * x ≡ 1 (mod m)을 만족하는 x이다. 모듈러 역원은 a와 m이 서로소일 때만 존재하며, 확장 유클리드 알고리즘 등을 사용하여 구할 수 있다.

응용

모듈러 산술은 다양한 분야에서 응용된다.

• 암호학: RSA 암호, 타원 곡선 암호 등 현대 암호 시스템의 핵심적인 요소이다.
• 컴퓨터 과학: 해시 테이블, 오류 검출 코드 등 다양한 알고리즘에 사용된다.
• 정수론: 합동 방정식, 중국인의 나머지 정리 등 정수론의 여러 문제 해결에 활용된다.
• 시계 산술: 시간을 계산하거나 주기적인 현상을 모델링하는 데 사용된다.

예시

17 ≡ 5 (mod 12) : 17을 12로 나눈 나머지는 5이다. 시계에서 17시는 5시와 같다.

같이 보기

• 합동식
• 중국인의 나머지 정리
• 페르마의 소정리
• 오일러 정리
• 확장 유클리드 알고리즘