모듈러 역원 설명(Modular Inverse)

이 글은 확장 유클리드 알고리즘을 안다는 전제 하에 작성했습니다. 확장 유클리드 알고리즘은 여기에 설명했습니다.

나머지 연산

나머지 연산이란 정수끼리 연산을 할 때, 그 결과로 항상 어떤 수 $N$에 대하여 나머지를 취하는 연산을 말한다. 모듈러 연산이라고도 하며 나머지 연산 상에서 같다는 것을 표기할 때는 작대기 세개짜리 등호를 쓴다($\equiv$) .

어찌 됐든 이 모듈러 연산을 할 때, 덧셈과 곱셈, 뺄셈은 일반적인 정수의 사칙연산과 별 차이가 없다. 하지만 나눗셈의 경우 일단 원래 하던 방식으로 가능한지부터 의문이 든다. 모듈러 나눗셈을 하기 위해서는 역원이라는 개념을 알아야 한다. 어떤 수로 모듈러 나눗셈을 하고자 할 때, 그 수의 곱셈에 대한 역원을 찾고 그 역원을 곱해주는 것으로 나눗셈을 수행한다. 일반 나눗셈을 할 때, $a$로 나눠주는 것은 $\frac{1}{a}$를 곱해주는 것과 같은 것을 생각해보면 그림이 좀 그려질 것 같다.

이 뒤로 작성할 나머지 연산은 $\mod N$으로 한다고 생각하고 글을 작성합니다.

$a$의 $N$에 대한 모듈러 곱셈의 역원

역원을 구한다고 할 때, 어떤 수의 어떤 연산에 대한 역원을 구하는 것인지를 명시할 필요가 있다.

이제 $a$로 모듈러 나눗셈을 한다고 생각하자. 그러면 먼저 $a$의 $N$에 대한 모듈러 곱셉의 역원을 구해야 한다. 이 역원은 다음과 같이 정의할 수 있다.

$$
ax \equiv 1 \mod N
$$

위 식을 만족하는 $x$를 우리는 역원이라고 말하며, 일반적으로 $a^{-1}$이라고 표기한다.

그래서 $a$로 모듈러 나눗셈을 한다고 하면, $a^{-1}$을 구해서 곱셈을 하는 것을 말한다. 그러면 이런 $x$를 어떻게 구하는지 알아보자.

$ax \equiv 1 \mod N$이므로 $ax = kN + 1$이라고 할 수 있다. $kN$을 좌변으로 넘기자.

$$
\begin{aligned}
ax-kN=1 \\
ax+Ny=1
\end{aligned}
$$

좌변으로 넘긴 식이 베주 항등식과 같은 꼴이기 때문에 $a,N$이 계수인 베주 항등식으로 생각할 수 있다. 이 식이 정수해 $(x,y)$를 가질 조건은 우변이 두 계수의 최대공약수의 정수배여야 한다. 즉, $GCD(a,N) = 1$일 때만, 정수해를 갖는다. 이를 바꿔 말하면 $a$와 $N$이 서로소일 때만 $a$의 $N$에 대한 모듈러 곱셈의 역원이 존재한다는 것이다. 서로소 아니면 나눗셈도 못한다니 너무하다.

어찌됐든 $a$와 $N$이 서로소라면 위 식의 정수해 $(x,y)$를 구할 수 있고 우리가 원하는 역원 $a^{-1}$은 $x$가 된다.

이제 확장 유클리드 알고리즘을 사용하면 모듈러 곱셉의 역원을 구해서 나눗셈을 할 수 있다는 것을 알았다. 그리고, 나누려는 수와 모듈러 수가 서로소가 아니면 불가능한 것도 알았다. 아래는 $a$와 $N$이 주어졌을 때, 역원을 구해주는 코드이다.

pair<int,pair<int,int>> xGCD(int a, int b) {    // it returns {g, {x,y}}, ax+by=g
    if(b == 0) return {a,{1,0}};
    pair<int,pair<int,int>> ret = xGCD(b, a%b);
    int g, x, y;
    g = ret.first;
    tie(x,y) = ret.second;
    return {g,{y,x-(a/b)*y}};   
}

int mod_inverse(int a, int mod) {
    auto res = xGCD(a,mod);
    if(res.first > 1) return -1;
    return (res.second.first + mod) % mod;
}

마지막으로 $N$이 소수일 때 성립하는 아주 좋은 성질이 있다. 페르마의 소정리라고 부른다.

$$
a^{-1} \equiv a^{N-2} \mod N
$$