Modular Exponentiation (Big Mod)
Problem Solving/Algorithm notes 2010. 2. 19. 00:18
만약에 a^b mod n 을 구한다고 해보자..
a, b 는 상당히 큰 integer 일 수 있다..
가장 무식한 방법은 a 를 b 번 곱하고 그 결과를 n 으로 modulo 하는 것이다..
대략 c 코드로 나타내면..
하지만 b 가 조금만 크더라도 계산 중간에 overflow 가 나서 막장이된다..
이를 해결하기 위하여 modulo 의 다음 성질을 이용해보자..
(a * b) mod c = ((a mod c) * (b mod c)) mod c
이를 이용하여 위 코드를 좀 고쳐보면..
이제 정확한 결과를 구할 수 있다.. 그러나 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
이런식으로 구하면 되겠다..
이정도면 상당히 효율적인 코드가 된다..
그러나 Indroduction to Algorithms (일명 CLR) 책 page 879 를 보면 좀더 괴상한 방법을 소개하고있다..
과연 이 코드의 원리는..?
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 }
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 }
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 }
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
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 |