Joonas' Note

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

알고리즘

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

joonas 2017.11.01 16:05

확장 유클리드 알고리즘(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 \\
r_i \leftarrow & ~r_{i-2} - r_{i-1} \cdot q_i \\
s_i \leftarrow & ~s_{i-2} - s_{i-1} \cdot q_i \\
t_i \leftarrow & ~t_{i-2} - t_{i-1} \cdot q_i \\
\end{align} $$

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

\( r_i \leftarrow ~r_{i-2} - r_{i-1} \cdot q_i \) 라고 되어있는데, 그냥 \(r_{i-1}~mod~r_{i-2}\) 즉, 나눈 나머지로 계산하면 편하다. (이때는 \(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\)를 하면 된다.

2 Comments
댓글쓰기 폼