Finding Inverse a (mod n)
먼저, 합동에서의 역이란 무엇을 말하는 것인가? gcd(a, n) = 1이라 했을 때, s와 t를 as + nt = 1을 만족하는 정수라 하자. 유클리드 알고리즘을 이용하면 s, t를 구할 수 있다. as + nt =1은 as ≡ 1 (mod n)의 꼴로 다시 쓸 수 있으며, 이때 s를 a (mod n)에 대한 inverse라 한다. 즉, a (mod n)에 대한 inverse를 구하려면, 다음과 같은 과정을 거친다. 1. as + nt = 1을 만족하는 s, t를 유클리드 알고리즘을 이용하여 구한다. 2. inverse a ≡ s (mod n)의 결과를 얻을 수 있다. 간단히, a와 n이 간단한 수라면 유클리드 알고리즘을 사용하는 것보다 직관적으로 쉽게 알 수도 있다. 예를 들어, inverse 7 (..
더보기