1. Introduction 여러분은 합동식 (Congruence)에 대해 알고 있는가? 아마 이과라도 정규 교육과정만 배웠다면 합동식에 대해 들어본 적 없을 수 있다. 컴공정도는 되어야 익숙하게 설명할 수 있을 듯한 이 합동식은 사실 정수론의 핵심적인 이론이다. 합동식의 정의는 다음과 같다. "정수 $a,b,m$에 대하여, $m∣(a−b)$일 때, $a$는 법 $m$에 대하여 $b$와 합동이다." 이때, 기호로는 $$a\equiv b\left(\text{mod}\,m\right)$$라고 쓴다. $m$를 합동의 법(modular)이라고 한다. 이해하기 어려운가? 간단하게 말해서, "$a$를 $m$으로 나눈 나머지와 $b$를 $m$으로 나눈 나머지는 같다." 라는 것과 같은 말이다. 컴공에서는 합동식이 결..

1. Introduction 호제법은 유클리드의 저서 원론에 적혀있는, 인류 최초의 알고리즘이다. 두 수의 최대공약수를 구하는 방법으로, 정의는 다음과 같다. 두 양의 정수 $a, b (a > b)$에 대하여 $gcd(a, b) = gcd(b, (a\bmod b))$이다. 2. Proof $gcd(a, b)=G$라 하자. 그럼 적당한 서로소인 정수 $A, B$에 대해 $a=GA, b=GB$가 성립한다. 이를 $a=bq+r$에 대입하면, $GA=GBq+r$이고, $r=G(A−Bq)$이다. 여기서 $G$는 $b$와 $r$의 공약수임을 알 수 있다 ($b=GB, r=G(A−Bq)$). 만약 $B$와 $A−Bq$ ($b$와 $r$에서 $G$를 제외한 남은 부분)가 서로소이기만 하면, 즉 $gcd(B, A−Bq)..

1. Introduction 정수론과 암호학을 공부하다보면, 매우 큰 수에 대해 나머지를 알아야 하는 경우가 생긴다. 그 수가 소인수분해가 된다면 나머지를 얻어내는데 큰 어려움이 없겠지만, 그렇지 않다면 그 수를 $N = a^b + R$의 형태로 나누어 계산해야한다. $a^b$의 나머지를 알 수 있으면 $R$은 상대적으로 작은 수이기 때문에 나머지를 얻어내는데 큰 어려움을 갖지 않는다. 따라서 이번 포스팅에서는 $a^b$의 나머지를 찾아내는 방법을 알아보도록 한다. 2. Approach 기본적인 아이디어는 $ab \bmod m = (a \bmod m)(b \bmod m) \bmod m$에서 착안한다. 지수를 2의 거듭제곱의 합 형태로 나타내어 표현하는 것이다. $5^{117} \bmod 19$를 예로 들..