모듈러 연산 (Modular Arithmetic)
쉽게 풀면
시계를 생각해보면 쉽습니다. 9시에서 5시간이 지나면 14시가 아니라 2시라고 말합니다. 12시간이 지나면 다시 원점(0)으로 돌아가기 때문입니다. 이것이 바로 "12로 나눈 나머지"로 시각을 표현하는 모듈러 연산입니다. 수학적으로는 "14를 12로 나눈 나머지가 2"이므로 14와 2는 "12를 법으로 하여 합동(congruent)"이라고 표현합니다. 이 개념은 무한히 커지는 숫자를 정해진 범위 안의 값으로 순환시켜 다루고 싶을 때 매우 유용합니다.
왜 중요한가
모듈러 연산은 정수론의 기초 도구일 뿐 아니라, 공개키 암호화, 해시 함수, 오류 검출 부호 등 현대 컴퓨터과학의 여러 핵심 기술을 떠받치는 수학적 토대이기 때문에 폭넓게 다뤄집니다. 특히 큰 수의 곱셈이나 거듭제곱을 유한한 범위 안에서 안전하고 효율적으로 계산할 수 있게 해주는 성질 덕분에, RSA 같은 암호 체계와 대규모 데이터를 다루는 해싱 기법 연구에서 없어서는 안 될 개념으로 자리 잡고 있습니다.
논문에서는 이렇게 쓰입니다
이 문장은 해시 함수가 나머지 연산을 이용해 입력 데이터를 정해진 크기의 테이블 안에 고르게 흩어지도록 만든다는 뜻입니다. 모듈러 연산은 해시 테이블, 암호화, 순환 버퍼 인덱싱 등 데이터를 일정한 범위 안에서 순환시켜야 하는 거의 모든 계산 분야에서 핵심 도구로 쓰입니다.
암호학 분야에서는 큰 수의 소인수분해가 어렵다는 성질과 모듈러 거듭제곱 연산을 결합해 안전한 공개키 암호 체계를 설계하는 데 이 개념이 핵심적으로 쓰인다는 뜻입니다.
통신 및 데이터 저장 분야에서는 전송 중 발생한 오류를 검출하기 위한 부호를 설계할 때도 모듈러 연산의 나머지 개념이 응용된다는 뜻입니다.
조금 더 깊게 보면
모듈러 연산에서 자주 함께 등장하는 개념으로 합동식(congruence), 모듈러 역원(어떤 수를 곱했을 때 법에 대해 1이 되는 수), 그리고 오일러 정리와 페르마 소정리처럼 거듭제곱의 주기성을 다루는 정리들이 있으며, 이런 정리들이 바로 RSA 암호화의 수학적 안전성을 뒷받침합니다. 큰 지수를 다룰 때는 매번 곱한 뒤 나머지를 구하는 대신, 지수를 반씩 줄여가며 계산하는 빠른 거듭제곱(modular exponentiation) 기법이 실제 구현에서 표준적으로 쓰입니다. 논문을 읽을 때는 어떤 법(modulus)을 선택했는지, 그리고 그 법이 소수인지 합성수인지가 알고리즘의 안전성이나 효율성에 어떤 영향을 미치는지를 함께 살펴보는 것이 도움이 됩니다.
주의할 점
모듈러 연산의 결과(나머지)는 항상 0 이상 법(modulus) 미만의 값을 가져야 하지만, 프로그래밍 언어에 따라 음수를 나눌 때 나머지의 부호를 다르게 처리하는 경우가 있어 구현 시 주의가 필요합니다. 모듈러 연산으로 최대공약수를 구하는 절차는 유클리드 호제법과 직접 연결됩니다.