Thursday, January 23, 2014

법 M에 대한 곱셈의 역원(Inverse Element)

PS를 하다보면 P/Q (mod M) (단, P는 Q의 배수이며 M은 큰 소수)를 계산하게 되는 경우가 있다. 이 때, P와 Q가 엄청 큰 수라서 각각을 구한 후, 나누기가 힘드므로 법 M에 대한 곱셈의 역원을 구하여 계산을 쉽게할 수 있다.
법 M에 대한 양의 정수 a의 곱셈의 역원을 구하는 방법에는 크게 2가지가 있다.

1. Euler's Theorem
'오일러의 정리'란 양의 정수 M과 (a,M)=1인 정수 a에 대하여 aφ(M) ≡1(mod M)임을 말한다. 이 정리는 기약잉여계를 이용하여 간단하게 확인할 수 있으므로 증명은 생략한다. φ(M)은 M이 소수이므로 M-1이 된다.(역도 귀류법에 의해 성립한다.) 따라서 법 M에 대한 양의 정수 a의 곱셈의 역원을 x라고하면 ax≡1(mod M)이고 오일러 정리에 의해 x ≡ aM-2 (mod M)이 된다. 각각의 x를 구할 때마다 O(log M)의 시간복잡도를 가지므로 n개의 역원을 구한다면 전체 시간복잡도는 O(n log M)이 되겠다.

2. 확장 유클리드 알고리즘

이에 대해선 앞선 게시글에 언급한 바가 있어서 자세히 설명하진 않겠다.
두 양의 정수 a, b에 대하여 r0 = a, r1 = b라 하고 a0 , ... , an , r2 , ... , rn , rn+1 을 다음을 만족하는 정수라 하면,
r0 = a0 r1 + r2 (0<r2<r1)
r1 = a1 r2 + r3 (0<r3<r2)
r2 = a2 r3 + r4 (0<r4<r3)
...
rn-1 = an-1 rn + rn+1 (0<rn+1<rn)
rn = an rn+1, (a, b) = rn+1
그리고 
S= 1, S= 0, SSi-2 ai-2 Si-1 (2 ≤ i ≤ n+1)
T= 0, T= 1, TTi-2 ai-2 Ti-1 (2 ≤ i ≤ n+1)
이라 두면 ri = a ST(0 ≤ i ≤ n+1)이 성립하고, 특히 (a, b) = rn+1 = Sn+1 Tn+1 이 성립한다. 이를 이용하여 ax≡1(mod M)를 (a, M) = 1이므로 일차부정방정식의 형태로 고쳐서 풀 수 있다. 시간복잡도는 오일러 정리를 이용한 것과 큰 차이가 없다.
추가적으로 예를 들어 설명하자면, 3x≡1(mod 5)는 (3, 5)=1이므로 3×2+5×(-1)=1 임을 통해 x≡2(mod 5)의 해를 얻게 된다.

No comments:

Post a Comment