모듈러 나눗셈

Modular

사칙연산만큼 친숙한 모듈러지만 연산은 사칙연산만큼 심플하지는 않다. 정의 자체가 나눗셈을 한 후에 나머지를 가리키는 뜻이니 나눗셈 이상의 매력이 있다.

 

그럼 한번 사칙연산과 모듈러의 관계를 정리해보자.

$$ \begin{align} (a + b)\ \%\ M & = ((a\ \%\ M) + (b\ \%\ M))\ \%\ M \\
(a - b)\ \%\ M & = ((a\ \%\ M) - (b\ \%\ M) + M)\ \%\ M \\
(a \times b)\ \%\ M & = ((a\ \%\ M) \times (b\ \%\ M))\ \%\ M \\
(a\ /\ b)\ \%\ M & = ((a\ \%\ M)\ /\ (b\ \%\ M)\ \%\ M \cdots ? \end{align} $$

 

덧셈, 뺄셈, 곱셈은 분배법칙이 잘 먹히지만 나눗셈에 대해서는 적용되지 않는다.
그럼 식을 조금씩 바꿔가면서 접근해보자.

$$ \begin{align}
(a\ /\ b)\ \%\ M &= (a \times b^{-1})\ \%\ M \\
&= ((a\ \%\ M) \times (b^{-1}\ \%\ M))\ \%\ M \end{align} $$

 

나눗셈을 곱셈으로 바꾸기 위해 $b$를 $b^{-1}$로 바꿨다. 

곱셈은 분배가 되니 이제 $ b^{-1} \%\ M $ 만 해결하면 될 것 같다.

 

여기서 곱셈에 대한 역원 개념을 가져와보자.

 

흔히 알고 있는 $x$의 곱셈에 대한 역원은 $x^{-1}$ 이다. $x^{-1}$를 곱하면 항상 곱셈 항등원인 1을 만들 수 있기 때문이다. 하지만 모듈러 영역에서 $x^{-1}$ 는 알맞은 값이 아니다. 모듈러 영역의 값 중에서 b와 곱하고 모듈러를 취했을 때 1이 되는 값을 찾아야 한다. 이 값을 찾는다면 $ b^{-1} $ 를 대체할 수 있고 결국 모듈러 연산에서 나눗셈을 없앨 수 있다.

 

그렇다면 $ Z_{M} = \{0, 1, 2, 3, ..., M-1\} $ 인 모듈러 집합 세계에서 곱셈에 대한 역원은 어떻게 구할 수 있을까?

 

곱셈에 대한 역원

모듈러 집합 세계에서 곱셈에 대한 역원을 구하는 방법은 여러 가지가 있다.
가장 무식하게는 모든 원소에 대해서 곱셈을 해본 후 모듈러를 취했을 때 1이 나오는 값을 찾으면 된다. 하지만 수학적으로 더 빠르게 구할 수 있는 방법을 알아보자.

페르마의 소정리

Fermat's Little Theorem 에 의해 다음과 같은 식이 존재한다.

$$ a^{p-1} \equiv 1\ (mod\ p), 단\ p는\ 소수이고\ a가\ p의\ 배수가\ 아닌\ 경우 $$

즉, $ a^{p-1} = a \times a^{p-2} \equiv1\ (mod\ p) $ 이다.

 

식을 자세히 보면 $a$에 $a^{p-2}$를 곱했더니 곱셈 항등원 1이 나왔다.

Fermat's Little Theorem 한방에 $ a^{p-2} $ 라는 $a$의 곱셈에 대한 역원을 구한 것이다.
(물론 Fermat's Little Theorem을 도입했기 때문에 p는 소수여야 하고 a는 p의 배수이면 안된다는 가정은 충족되어야 한다.)

 

그럼 다시 구하려던 식을 정리하면 아래처럼 $b^{-1}$을 $b^{M-2}$로 바꿀 수 있다.
$$ ((a\ \%\ M) \times (b^{M-2}\ \%\ M))\ \%\ M $$

곱셈은 모듈러 연산의 분배 법칙이 가능하기 때문에 매번 모듈러 연산을 해가면서 오버플로 나지 않도록 $b^{M-2}$를 계산하면 된다. 더 효율적으로 $ b^{M-2} $ 를 지수 성질을 이용해서 제곱하면 $ O(log_{2}M) $ 만에 구할 수 있다.

int fastPow(int base, int exp, int mod) {
    int result = 1;
    for (; exp; exp >>= 1, base = (base * base) % mod) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
    }

    return result;
}

 

확장 유클리드

페르마의 소정리로 곱셈에 대한 역원을 구했지만 이는 $M$이 소수라는 제약조건이 있다.
확장 유클리드 호제법은 $M$이 소수가 아니어도 $a$와 $M$이 서로소라는 조건만 만족하면 곱셈에 대한 역원을 구할 수 있다. 확장 유클리드 호제법은 $a$와 $b$에 대해서 아래 식을 만족하는 $x$, $y$, $gcd(a,b)$를 구하는 알고리즘이다.
$$ax + by = gcd(a,b)$$

 

그 원리를 조금 더 파보면 식 $ax + by = c$ 는 $c$가 $gcd(a,b)$의 배수인 경우에만 정수해 $x$, $y$를 가진다. 따라서 $x$, $y$가 정수일 때 구해지는 값 $c$ 중에 최솟값을 구하면 그것이 $gcd(a,b)$가 되고, $gcd(a,b)$를 구하는 유클리드 호제법을 역으로 추적해가는 확장 유클리드 호제법을 이용하면 이를 만족시키는 $x$, $y$, $gcd(a,b)$ 를 구할 수 있다.

// return: <gcd(a, b), n, m>
tuple<int, int, int> xGCD(int a, int b) {
      if (b == 0) {
          return make_tuple(a, 1, 0);
      }
      int g, x, y;
      tie(g, x, y) = xGCD(b, a%b);
      return make_tuple(g, y, x-(a/b)*y);
}

 

그러면 확장 유클리드 호제법과 곱셈에 대한 역원을 연결 지어보자.

 

$a$의 곱셈에 대한 역원을 $x$라고 하면 $ax \equiv 1\ (mod\ p)$ 일 것이다. 이 식을 다시 쓰면 확장 유클리드 호제법과 같은 식으로 변환할 수 있다.
$$ \begin{align}
ax & \equiv 1\ (mod\ p) \\
ax & = py + 1 \\
ax - py & = 1 \\
ax - py & = gcd(a,p) \end{align}$$

따라서 $a$와 $p$에 대해서 확장 유클리드 호제법을 이용해서 $x$와 $y$를 구하면 $a$의 곱셈에 대한 역원 $x$를 구할 수 있다.

이를 이용해서 처음에 구하려던 식을 정리해보자.

$$ ((a\ \%\ M) \times (b^{-1} \%\ M))\ \%\ M $$

확장 유클리드 호제법을 이용해서 $ bx - My = 1 $ 를 만족하는 $b$의 곱셈에 대한 역원 $x$를 구하면 아래와 같이 바꿀 수 있다.
$$ ((a\ \%\ M) \times (x\ \%\ M))\ \%\ M $$

 

정리

모듈러 연산에서 나눗셈이 있는 경우 분배 법칙이 적용되지 않기때문에 $ b^{-1} \%\ M $ 식으로 변경한 후 b의 곱셈에 대한 역원을 구해서 해결했다. 곱셈은 모듈러 연산에서 분배법칙이 적용되기 때문이다. 이때 곱셈에 대한 역원은 페르마의 소정리 또는 확장 유클리드 호제법을 이용해서 구한다.

 

문제를 풀다 보면 가끔 쿼리 자체가 많아서 이걸로도 부족한 경우가 있는데, 상황에 맞게 적절한 전처리를 해 놓으면 여러 케이스에 빠른 답을 구할 수 있다.