티스토리 뷰

알고리즘 이론

Modular Arithmetic

museop 2017. 3. 18. 21:25

Modular Arithmetic



정수 \(a, b, m\)에 대하여, \(m \ | \ (a-b)\) 일때, \(a\)는 법 \(m\)에 대하여 \(b\)와 합동이다(\(a\) is congruent to \(b\) modulo \(m\)). 이때, 기호로 \(a\equiv b\pmod m\)이라고 쓴다. 여기서 \(m\)을 합동의 법(modular)이라고 한다. 수학적인 정의는 이렇고, 간단하게 말하면 '\(a\)와 \(b\)를 \(m\)으로 나누었을 때, 그 둘의 나머지가 같다'라고 생각하면 된다.


모듈라 연산에서의 덧셈, 뺄셈, 곱셈은 다음과 같은 성질들이 성립한다.


\((a+b) \pmod m \equiv ((a \pmod m) + (b \pmod m)) \pmod m\)

\((a-b) \pmod m \equiv ((a \pmod m) - (b \pmod m)) \pmod m\)

\((a \times b) \pmod m \equiv ((a \pmod m) \times (b \pmod m)) \pmod m\)


그러나 위의 덧셈, 뺄셈, 곱셈과는 다르게 나눗셈에서는 이와 같은 식으로 계산할 수 없다. 모듈라 나눗셈에서는 \(b\)로 나누는 대신 \(b\)의 곱셈 역원(multiplicative inverse)을 곱한다. 여기서 모듈라 곱셈 역원이란 \(b \times b^{-1} \equiv 1 \pmod m\)을 만족하는 \(b^{-1}\)을 말한다. \(b\)의 곱셈 역원은 항상 존재하는 것이 아니라, \(b\)와 \(m\)이 서로소인 경우에만 존재한다. 만약 이러한 \(b\)의 역원이 존재한다면 \((a/b) \pmod m\)을 다음과 같이 구할 수 있다.

\((a/b) \pmod m \equiv ((a \pmod m) \times (b^{-1} \pmod m)) \pmod m\)

곱셈 역원 구하기

단순한 방법

\(Z_m\)에서 어떤 수 \(b\)의 역원을 구하는 가장 단순한 방법은 1부터 \(m-1\)까지의 수를 모두 조사해보는 것이다. (시간복잡도: \(O(m)\))



페르마의 소정리

만약 \(m\)이 소수인 경우에는 페르마의 소정리(Fermat's Little Theorem)을 이용하여 역원을 빠르게 구할 수 있다. \(m\)이 소수이고, \(a\)와 \(m\)이 서로소일 때, \(a^{m-1} \equiv 1 \pmod m\)이 성립한다. 따라서 \(a\)의 역원은 \(a^{m-2}\)가 된다.


확장 유클리드 알고리즘

만약 \(m\)이 소수가 아닌 경우에 \(b\)의 역원을 빠르게 찾고 싶다면 확장 유클리드 알고리즘(Extended Euclidean algorithm)을 이용하여 다음과 같은 식을 만족하는 \(x\)를 빠르게 찾으면 된다.


\(x \cdot b + y \cdot m \equiv 1 \pmod m\)


확장 유클리드 알고리즘은 두 정수 \(a\)와 \(b\)가 주어졌을 때, 다음식을 만족하는 두 정수 \(x, y\) 그리고 gcd(\(a\), \(b\)) 까지 동시에 계산한다. 보통 모듈로 안에서 곱셈에 대한 역원을 구할 때나, 중국인의 나머지 정리에서 해를 구할 때 사용될 수 있다.



중국인의 나머지 정리

중국의 오래된 수학책 '손자산경(孫子算經)'에는 다음과 같은 문제가 있다고 한다.

 3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?


이러한 형태의 문제는 중국인의 나머지 정리(Chinese Remainder Theorem)와 확장 유클리드 알고리즘을 이용하여 해결할 수 있다. 먼저 중국인의 나머지 정리는 다음과 같다.


각각 서로소인 자연수 \(m_1, m_2, ..., m_n\)과 임의의 정수 \(a_1, a_2, ..., a_n\)에 대하여, 다음 연립합동식은 법 \(m_1, m_2, ..., m_n\)에 대하여 유일한 해를 갖는다. 


위 정리의 증명이자 연립합동식의 해 \(x\)를 구하는 과정은 다음과 같다.


  1. \(M=m_1m_2...m_n\)이라 하고, \(u_k=M/m_k\)라 놓는다.
  2. \(m_1, m_2, ..., m_n\)들은 각각 서로소이기 때문에 \(u_k\)와 \(m_k\) 역시 서로소, 즉 \(gcd(u_k, m_k)=1\) 이다.
  3. 2에 의해 \(s_ku_k+t_km_k=1\)을 만족하는 정수 \(s_k, t_k\)가 존재한다. 이를 합동식 형태로 고치면 \(s_ku_k \equiv 1 \pmod {m_k}\)가 되고, 양변에 임의의 정수 \(a_k\)를 곱하면 \(a_ks_ku_k \equiv a_k \pmod {m_k}\)가 성립한다.
  4. 이제 \(x=a_1u_1s_1+a_xu_2s_2+...+a_nu_ns_n \equiv a_k \cdot 1 \equiv a_k \pmod {m_k}\)가 성립하게 된다. 따라서 \(x\)가 주어진 연립합동식의 해가 된다.
위 과정에서 손으로 계산하기 까다로운 것이 \(s_ku_k+t_km_k=1\)을 만족하는 \(s_k\)인데 이는 앞서 설명한 확장 유클리드 알고리즘을 이용하여 구하면 된다.


예제


참고 자료


'알고리즘 이론' 카테고리의 다른 글

탐색 (Searching)  (0) 2017.03.06
Counting Sort, Radix Sort  (0) 2017.02.23
Suffix Array, LCP Array  (0) 2017.02.22
트리의 지름 (Diameter of Tree)  (0) 2017.02.20
KMP Pattern Searching  (0) 2017.02.20
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함