코딩 테스트 준비를 위해 알고리즘 문제들을 풀다보면 수학적 논리가 필요한 문제를 마주치게 된다 이번 글에선 이럴 때 필요한 수학적 논리 중 개인적으로 가장 처음에 맞닥드린 모듈러 연산에 대해 알아보려 한다

모듈러 연산이란?

모듈러 연산은 수학에서 중요한 개념으로 연산 결과를 특정한 값으로 나눈 나머지를 구하는 것을 의미하는데 주로 정수들 간의 산술 연산에서 사용되며 앞에서 말했듯이 어떤 정수를 다른 정수로 나눈 후에 나머지를 구하는 것이다

말로만 해서는 잘 이해가 되지 않을 수 있으니 식으로 보여주면

a mod b

이런 식으로 주로 나타내며

a % b

이렇게 나타내기도 한다

모듈러 연산의 역사

그렇다면 이러한 모듈러 연산은 언제부터 등장한 개념일까? 모듈러 연산은 생각보다 매우 오래 전부터 사용되었을 거라고 추측 되는데 초기에는 시간, 날짜 계산 및 천문학적인 계산에서 활용되었으며

후에 지금처럼 모듈러 연산이 현대적으로 더 널리 사용되고 이해되기 시작한 것은 19세기에 수학자 카를 프리드리히 가우스와 레온하르트 오일러 등이 관련 아이디어를 발전시키면서라고 한다 현재에는 이러한 모듈러 연산을 암호학, 컴퓨터 과학, 그래픽스 등 다양한 분야에서 사용되고 있다

모듈러 연산의 중요한 성질

이 글에서 제일 중요한 부분 모듈러 연산의 중요한 성질들에 대해 소개하겠다 이러한 성질들은 모듈러 연산이 다양한 수학적 응용에서 유용하게 활용되는데 기여하기에 핵심 부분이기에 꼭 알고 있어야 한다

성질 1: 교환법칙 (Commutative Property)

모듈러 연산은 교환법칙이 성립한다 즉

a mod b = b mod a 

이렇게 두 수를 나누는 순서에 상관 없이 모듈러 연산 결과가 같다

성질 2: 결합법칙 (Associative Property)

모듈러 연산은 결합법칙도 성립한다 식으로 확인하면

a mod (b mod c) = (a mod b)mod c

로 연산을 어떤 순서로 수행하더라도 결과가 동일하다는 걸 알 수 있다

성질 3: 분배법칙 (Distributive Property)

모듈러 연산은 분배법칙을 따른다 그렇기에

a mod (b+c) = (a mod b+a mod c)mod a

덧셈 혹은 뺄셈을 모듈러 연산한 결과는 개별적으로 모듈러 연산한 후에 다시 합친 결과와 동일하다

성질 4: 곱셈의 모듈러 연산 (Modular Multiplication)

모듈러 연산은 곱셈에 대해서도 성질을 갖는데

a × b mod n =(a mod n)×(b mod n)mod n

으로 이것은 두 수를 곱한 후 모듈러 연산한 결과는 각각의 수를 모듈러 연산한 후 곱한 결과와 같다는 것을 의미한다

성질 5: 항등원 (Identity Element)

마지막으로 항등원이 있는데 모듈러 연산에서 항등원은 모듈러 값을 그대로 돌려주는 수를 의미한다

모듈러 연산 예제

다음으로 간단한 모듈러 연산 예제로 모듈러 연산에 대해 이해해보자 예를 들어

17 mod 5

이것에 연산 결과는 2이다

모듈러 연산이 필요한 곳

그렇다면 모듈러 연산이 필요한 곳은 어디가 있을까?

암호학: RSA 알고리즘 등에서 소수의 성질을 이용하여 모듈러 연산이 활용된다
컴퓨터 과학: RSA 알고리즘, 해시 알고리즘, 자료 구조에서의 순환 및 반복 처리에 활용된다
그래픽스: 주기적인 패턴을 만들거나 좌표를 다룰 때 모듈러 연산을 사용한다

이렇게 정리할 수 있다

주의할 점

마지막으로 모듈러 연산에서 주의할 점에 대해 설명하고 마치려고 한다

0으로 나누기: 0으로 모듈러 연산을 수행할 수 없다
음수에 대한 모듈러 연산: 양수에 대한 연산과는 다르게 정의되는 경우가 있으므로 주의해야 한다
정확성 유지: 부동 소수점 연산 시 정확도를 유지하기 위해 조심해야 한다

모듈러 연산이란 무엇일까?