확장 유클리드 알고리즘으로 나머지 연산의 곱셈 역원 구하기

확장 유클리드 알고리즘(Extended Euclidian Algorithm)은 유클리드 호제법을 확장한 것이다.

$as + bt = gcd(a,b)$을 만족하는 정수 $s$, $t$ 짝을 찾아낼 수 있다.

증명은 생략하고 어떻게 사용하는가를 적어볼까 한다.

초기 조건

$s_0 = 1, s_1 = 0, ~~t_0 = 0, t_1 = 1, ~~r_0 = a, r_1 = b$

진행

$$\begin{align} q_i \leftarrow & \lfloor~r_{i-1}~/~r_i~\rfloor & (i \ge 1)\\ r_i \leftarrow & ~r_{i-2} - r_{i-1} \cdot q_{i-1} & (i \ge 2)\\ s_i \leftarrow & ~s_{i-2} - s_{i-1} \cdot q_{i-1} & \\ t_i \leftarrow & ~t_{i-2} - t_{i-1} \cdot q_{i-1} & \\ \end{align}$$

가만보면 $r, s, t$가 전부 똑같은 방식으로 처리되는 걸 알 수 있다. 이걸 표를 그려서 전개해보면 외우기도 쉽고 과정도 잘 보여서 좋다.

$r_i \leftarrow ~r_{i-2} - r_{i-1} \cdot q_{i-1}$ 라고 되어있는데, 그냥 $r_{i-2}~mod~r_{i-1}$ 즉, 나눈 나머지로 계산하면 편하다. (이때는 $a \geq b$이여야함)

아래 표를 작성하고 숫자만 채울 준비를 하자.

	$s_i$	$t_i$	$r_i$	$q_i$
$i=0$	1	0	$a$
$i=1$	0	1	$b$	$\lfloor~a~/~b~\rfloor$
			$a~mod~b$

 

적당한 예시로 $15s+6t=3$ 를 만족시키는 $s, t$를 찾아보자.

이전에 구한 값을 노란색으로 색칠하고, 노란색을 통해 계산한 값을 파란색으로 칠했다.

 

 

 

 

	$s_i$	$t_i$	$r_i$	$q_i$
$i=0$	$1$	$0$	$a = 15$
$i=1$	$0$	$1$	$b = 6$	$\lfloor~15~/~6\rfloor = 2$
$i=2$	$1 - 0*2 = 1$	$0 - 1*2 = -2$	$15~mod~6 = 3$
$i=3$

 

위 표에서 우린 다음 $q_2$와 $r_3$을 얻을 수 있다. 이걸로 다시 또 $s_3, t_3$을 찾을 수 있고 계속 반복한다.

 

	$s_i$	$t_i$	$r_i$	$q_i$
$i=0$	$1$	$0$	$a = 15$
$i=1$	$0$	$1$	$b = 6$	$2$
$i=2$	$1$	$-2$	$3$	$\lfloor~6~/~3~\rfloor = 2$
$i=3$			$6~mod~3 = 0$

 

 

 

 

$r$이 0이 되는 순간 우린 나머지가 0이 되는, 즉 식이 나누어 떨어지는 $s, t$를 찾았다는 의미이다. 그래서 노란색으로 색칠된 값들이 우리가 구하고자 했던 답이다.

언제나 검산은 옳다. 검산해보면 $15s+6t~=~15 \cdot 1 + 6 \cdot (-2)~=~15-12~=3$ 인 것을 확인할 수 있다.

나머지 연산의 곱셈 역원

확장 유클리드 알고리즘으로 모듈러에서 곱셈의 역원도 구할 수 있다!
우선 곱셈의 역원이 존재한다는 것은 두 수가 서로소라는 건데, $a \cdot s \equiv 1~(mod~p)$ 를 만족시키는 $s$를 찾을 수 있다는 의미이다.

그럼 다음 식이 가능하다는 의미이다.

$$\begin{align} \text{if}~\text{gcd}(a,p)=1,~~& a \cdot s \equiv 1~(mod~p) \\ \therefore~& a \cdot s + p \cdot t = 1 \end{align}$$

우린 $a$와 $p$를 알고 있으니 확장 유클리드 알고리즘으로 원하던 $s$를 구할 수 있다. 한 가지 주의할 점(?)이라면 $s$ 는 음수가 될 수도 있다는 것이다. 양수인 곱셈의 역원만 구하고 싶다면, $s_{result} \leftarrow (s_{result} + p)~mod~p$를 하면 된다.