Modular Inverse

모듈러 역원(Modular Inverse)은 어떤 수와 모듈러 관계에 있는 다른 수를 의미한다. 구체적으로 모듈러 곱셈 역원(Modular Multiplicative Inverse)인지, 모듈러 덧셈 역원(Modular Additive Inverse)인지에 따라 정의가 달라지며, 일반적으로 모듈러 역원이라고 하면 곱셈 역원을 지칭해 사용한다.

덧셈 역원

\[n + x \equiv 0 \pmod{m}\]

수 $n$ 의 모듈러 $m$ 에 대한 덧셈 역원은 $x$ 이다.

모듈러 덧셈 역원은 어떤 정수 $n$ 에 대해, 합이 $m$ 의 배수가 되도록 하는 다른 수 $x$ 를 찾는 것이다. 즉, $n + x$ 가 $m$ 으로 나누어 떨어지도록 하는 $x$ 를 의미한다.

이 값은 찾는 방법이 매우 쉽고 모듈러를 도입하지 않아도 충분히 논의 가능하기 때문에, 모듈러를 적용하면서 계산하지는 않는다.

곱셈 역원

\[n \cdot x \equiv 1 \pmod{m}\]

수 $n$ 의 모듈러 $m$ 에 대한 곱셈 역원은 $x$ 이다.

모듈러 곱셈 역원은 어떤 정수 $n$ 에 대해, 곱이 모듈러 $m$ 에서 1과 합동이 되도록 하는 다른 수 $x$ 를 찾는 것이다. 즉, $n \cdot x$ 가 $m$ 으로 나누었을 때 나머지가 1이 되도록 하는 $x$ 를 의미한다.

곱셈 역원은 덧셈 역원과 달리, 낯선 사람에게는 다소 비직관적일 수 있다. 또한 덧셈 역원과는 상반되게 모듈러를 적용하지 않으면 논의가 불가능하고, 더욱 다양하게 활용 가능하므로, 모듈러 역원이라고 하면 곱셈 역원을 지칭해 사용한다.

모듈러 역원은 페르마의 소정리나 확장 유클리드 호제법을 사용해 구할 수 있다.

페르마의 소정리

\[a^{p-1} \equiv 1 \pmod{p}\]

모듈러 $m$ 이 소수일 때, 위 식의 양 변에 $a^{-1}$ 을 곱하면, 모듈러 곱셈 역원을 구할 수 있다.

이 때 $a^{-1}$ 은 $1/a$ 는 아니고, 모듈러 곱셈 역원으로 $a$ 와 곱했을 때 모듈러 $p$ 에서 1과 합동이 되는 수를 의미한다.

\[a^{p-2} \equiv a^{-1} \pmod{p}\]

모듈러 곱셈 역원 $a^{-1}$ 을 $a^{p-1}$ 에 곱한 결과를 일반 곱셈, 나눗셈처럼 $a^{-2}$ 로 표현하더라도 모듈러를 사용하고 있는 이상 문제가 발생하지 않는다.

$a^{p-1}$ 은 $a^p$ 에서 정수 $a^{-1}$ 을 1회 곱한 것으로, $a^{p-1}$ 에서 $a^{p}$ 로는 $a$ 를 1회 곱하고 모듈러하여 되돌릴 수 있다.

\[\begin{aligned} &2^{5-1} (= 2^4) \equiv 1 \pmod{5} \\ \Rightarrow &2^{5-2} (= 2^3) \equiv 2^{-1} (=3) \pmod{5} \end{aligned}\]

계속해서,

\[a^{-1} \equiv a^{p-2} \pmod{p}\] \[x = a^{-1} \equiv a^{p-2} \pmod{p}\] \[x \equiv n^{m-2} \pmod{m}\]

확장 유클리드 호제법

\[ax + my = 1\]

확장 유클리드 호제법에서는 위 식을 만족하는 정수 $x$, $y$ 를 찾는 것이 목표이다.

def gcd(a, b):
  if b == 0: return a
  return gcd(b, a % b)

유클리드 호제법에서 $a$ 를 $b$ 로 나눈 몫을 $q$, 나머지를 $r$ 이라고 하면, 다음과 같이 표현할 수 있다.

\[a = qb + r \Longrightarrow r = a - qb\]

제수 $b$ 와 나머지 $r$ 에 대해서 다음의 관계를 만족하는 정수 $x’$, $y’$ 가 존재한다고 가정한다.

\[b x' + r y' = \gcd(b, r)\]

유클리드 호제법에 의해 $\gcd(a, b) = \gcd(b, r)$ 이다.

\[\gcd(a, b) = \gcd(b, r)\] \[r = a - qb\] \[\begin{aligned} b x' + r y' &= \gcd(b, r) \\ b x' + (a - qb) y' &= \gcd(a, b) \end{aligned}\] \[a (y') + b (x' - qy') = \gcd(a, b)\]

외형적으로 처음의 식과 비슷하게 구성되었다. 따라서 $x = y’$, $y = x’ - qy’$ 로 치환하여, 역원을 구할 수 있다.

\[x = y' \quad \text{and} \quad y = x' - qy'\]