[Algorithm] 모듈러 산술(modular Arithmetic)

모듈로(Modulo) 연산

컴퓨팅에서 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.

즉 일반적으로 정수 범위의 내에서 대부분 a를 n으로 나눈 나머지 r과 몫 q는 다음을 충족한다. 

일반적으로 a와 n이 모두 정수인 상태에서 수행되지만 요즘은 많은 곳에서 정수 범위 이상의 피연산자를 사용할 수 있다.

하지만, mod 0은 Divide by Zero 에서 예외가 발생할 수 있기 때문에 주의해야한다.

 

이 모듈로 연산에 관련된 규칙이 모듈러 산술이다.

 

모듈러 산술(Modular Arithmetic)

모듈로 합동(Congruence Modulo)

두 정수 a, b와 정수 n (n > 1)이 주어질 때 n이 a, b의 차의 약수인 경우 (즉, a - b = kn을 만족하는 정수 k가 있는 경우) 모듈로 합동이라고 한다.

이는 a ≡ b (mod n), 즉 a mod n = b mod n 라는 뜻이다. (≡ 는 동치의 의미이다)

 

모듈로 합동은 다음 조건을 만족시킨다.

• 반사성: a ≡ a (mod n)
• 대칭성: a ≡ b (mod n) 이면, b ≡ a (mod n)
• 추이성: a ≡ b (mod n) 이고, b ≡ c (mod n) 이면, a ≡ c (mod n)

다음은 음수 값에도 적용되는 예시이다.

2 ≡ -3 (mod 5)

-8 ≡ 7 (mod 5)

-3 ≡ -8 (mod 5)

 

모듈러 연산(Modular Operation)

덧셈

 

뺄셈

 

곱셈

 

모듈러 역원(Modular Inverse)

모듈러 연산은 산술적으로 나눗셈 연산이 없지만 역원이 존재한다.

a (mod n)의 역원은 a^(-1) 이다. 이때, a * a^(-1) ≡ 1 (mod n) 이다.

 

이는 a의 역원 a^(-1)은 (a * a^(-1)) mod n = 1을 성립하는 a^(-1) 값을 뜻한다.

 

이때 이를 나머지 연산의 곱셈 역원이라고도 부르며, a^(-1)은 정수 a를 n으로 나눈 나머지 연산의 곱셈 역원이다.

이 역원은 a와 n이 서로소인 경우에만 존재한다.

 

역원?

집합 S와 이항연산자 *에 대해, 만약 항등원 e가 존재한다고 할 때, S의 원소 a에 대해 

를 만족하는 S의 원소 b가 유일하게 존재할 때, b를 a의 역원이라고 한다.

 

예를 들어,

실수 집합 R과 덧셈 연산자에 대해, 원소 x의 역원은 -x이다.

R에서 0을 제외한 집합과 곱셈 연산자에 대해, 원소 x의 역원은 1/x이다.

 

활용

a 값을 구하는 과정에서 a가 데이터 형식 범위를 넘어가 구할 수 없을 때 아래 성질을 활용할 수 있다.

즉 a값과 b^(-1)를 각각 모듈러 후 곱해서 다시 모듈러를 취하면 된다.

여기서 b^(-1)은 n이 소수라면 페르마의 소정리를, 소수가 아니라면 확장 유클리드 알고리즘을 통해 구할 수 있다.

 

이 외에 제일 간단한 방법을 설명하자면,

정수 a를 m으로 나눈 나머지 연산의 곱셈 역원은 다음 식을 만족하는 a^(-1)을 의미한다.

즉, a^(-1) ≡ x (mod m) 을 만족하는 x를 말한다.

역원은 a와 m이 서로소인 경우에만 존재하며, 이를 코드로 작성하면 다음과 같다.

for (int i = 1; i < m; i++) {
    if ((a * i) % m == 1) {
        x = i;
    }
}

하지만 이 방법은 O(m)의 시간복잡도를 가지고 있어, 보통 문제들의 m이 1000000007인 것을 고려하면 시간이 오래 걸린다.

 

때문에 위에서 언급한 두 방법으로 해결하는 것이 좋다.