지난번 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 이라면 어떻게 되는거임.. -_-??


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

Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유..  (2) 2011.03.02
Linear Diophantine Equation  (0) 2011.01.25
점과 선분과의 거리  (2) 2011.01.22
Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
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
Sorting Algorithm O(n^2)  (0) 2009.08.31
Bell Number  (0) 2009.07.12

Leave a Comment


to Top