만약에 a^b mod n 을 구한다고 해보자..
a, b 는 상당히 큰 integer 일 수 있다..

가장 무식한 방법은 a 를 b 번 곱하고 그 결과를 n 으로 modulo 하는 것이다..
대략 c 코드로 나타내면..

  1 int modular_exponentiation(int a, int b, int n)
  2 {
  3     int i, res;
  4     res = 1;
  5     for (i = 0; i < b; i++) {
  6         res *= a;
  7     }
  8     return res % n;
  9 }

하지만 b 가 조금만 크더라도 계산 중간에 overflow 가 나서 막장이된다..
이를 해결하기 위하여 modulo 의 다음 성질을 이용해보자..

(a * b) mod c = ((a mod c) * (b mod c)) mod c

이를 이용하여 위 코드를 좀 고쳐보면..

  1 int modular_exponentiation(int a, int b, int n)
  2 {
  3     int i, res;
  4     res = 1;
  5     for (i = 0; i < b; i++) {
  6         res = (res * (a % n)) % n;
  7     }
  8     return res;
  9 }

이제 정확한 결과를 구할 수 있다.. 그러나 b 가 매우 크다면 상당히 시간이 오래걸리는 코드이다..
여기서 exponentiation 을 좀 더 효과적으로 구할 수 있는데.. 다음의 성질을 이용할 수 있다..

a^n = a^(n/2) * a^(n/2) (n 은 짝수)

물론 n 이 홀수라면 저기에 a 를 한번만 더 곱해주면 된다..
즉, a^10 을 구한다고 하면 a 를 10 번 곱하는게 아니라..

a * a = a^2
a^2 * a^2 = a^4
a^4 * a = a^5
a^5 * a^5 = a^10

이런식으로 구하면 되겠다..

  1 int modular_exponentiation(int a, int b, int n)
  2 {
  3     int res;
  4     if (b == 0)
  5         return 1;
  6     if (b & 1)
  7         return ((a % n) * modular_exponentiation(a, b-1, n) % n) % n;
  8     res = modular_exponentiation(a, b / 2, n);
  9     return ((res % n) * (res % n)) % n;
 10 }

이정도면 상당히 효율적인 코드가 된다..
그러나 Indroduction to Algorithms (일명 CLR) 책 page 879 를 보면 좀더 괴상한 방법을 소개하고있다..

MODULAR-EXPONENTIATION(a, b, n)
 1 c ← 0
 2 d ← 1
 3 let (bk, bk-1, ..., b0) be the binary representation of b
 4 for i ← k downto 0
 5     do c ← 2c
 6         d ← (d · d) mod n
 7         if bi = 1
 8             then c ← c + 1
 9                    d ← (d · a) mod n
10 return d

과연 이 코드의 원리는..?


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Gaussian Prime  (0) 2011.04.03
점과 선분과의 거리  (2) 2011.01.22
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15

to Top