Algorithm/etc
-
Modular 연산에서 나눗셈Algorithm/etc 2020. 3. 23. 22:14
(a/b) % M 은 (a%M) / (b%M) 으로 바꾸어 표현할 수 없습니다. 대신 a/b를 a*a^-1 로 바꾸게 되면 (a*a^-1) % M = (a%M) * (a^-1 % M) 으로는 표현이 가능합니다.(곱셈에 대해서는 가능하기 때문입니다.) 위의 식을 이용하기 위해선 modular 연산에 대한 곱셈의 역원을 구해야 합니다. 1. M이 소수일때 M이 소수라면 저희는 페르마 소정리를 이용할 수 있습니다. 페르마 소정리 : a^p = p (mod p) a^(p-1) = 1 (mod p) 이고, a^(p-1) 를 a*a^(p-2) 로 나누게 되면 a의 p모듈러 영역에 대한 곱셈의 역원은 a^(p-2) 가 됩니다. 2. M이 소수가 아닐때 그리고 a와 M이 서로소 일때 ★a와 M이 서로소가 아니면 곱셈에..