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

확장 유클리드 알고리즘(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\)를 하면 된다.