Modular Multiplicative Inverse
Problem Solving/Algorithm notes 2010. 6. 13. 22:29
지난번 Extended Euclid 포스팅에 이어서..
이번에는 Modular Multiplicative Inverse 에 대해서 공부해보자..
modulo 연산의 성질에서..
(a * b) mod c = ((a mod c) * (b mod c)) mod c 는 성립하지만
(a / b) mod c = ((a mod c) / (b mod c)) mod c 는 성립하지 않는다..
대신 (a / b) mod c 를 구하고자 한다면..
((a mod c) * modular_multiplicative_inverse(b, c)) mod c
이렇게 하면 되겠다..
modular multiplicative inverse 는 extended euclid 를 이용하여 구할 수 있는데..
a^(-1) = x (mod m) <-- 여기서 x 가 a 의 modular multiplicative inverse 임..
=> ax = 1 (mod m)
=> ax - 1 = qm
=> ax - mq = 1
자 이제 여기서 extended euclid 를 이용하여 x 를 구하자..~
근데 여기서 만약 gcd(a, m) <> 1 이라면 어떻게 되는거임.. -_-??
이번에는 Modular Multiplicative Inverse 에 대해서 공부해보자..
modulo 연산의 성질에서..
(a * b) mod c = ((a mod c) * (b mod c)) mod c 는 성립하지만
(a / b) mod c = ((a mod c) / (b mod c)) mod c 는 성립하지 않는다..
대신 (a / b) mod c 를 구하고자 한다면..
((a mod c) * modular_multiplicative_inverse(b, c)) mod c
이렇게 하면 되겠다..
modular multiplicative inverse 는 extended euclid 를 이용하여 구할 수 있는데..
a^(-1) = x (mod m) <-- 여기서 x 가 a 의 modular multiplicative inverse 임..
=> ax = 1 (mod m)
=> ax - 1 = qm
=> ax - mq = 1
자 이제 여기서 extended euclid 를 이용하여 x 를 구하자..~
근데 여기서 만약 gcd(a, m) <> 1 이라면 어떻게 되는거임.. -_-??
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| Inversion Count (0) | 2016.01.31 |
|---|---|
| The Tower of Hanoi (0) | 2011.08.28 |
| Gaussian Prime (0) | 2011.04.03 |
| 점과 선분과의 거리 (2) | 2011.01.22 |
| Konig's Theorem (0) | 2010.08.01 |
| Primality Testing (Miller-Rabin) (0) | 2010.03.23 |
| Modular Exponentiation (Big Mod) (2) | 2010.02.19 |
| 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 |