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 \bmod m$형태를 계산하는 방법은 여기에 포스팅했다. 이번 포스팅에서는 이것을 돌리기 위한 코드를 최적화하는 방법을 소개한다. 2. Approach $a^b$의 형태의 자연수에 대한 나머지 계산에 대한 방법들을 소개한다. 2.1 일반적인 방법 def powMod1(base, index, mod): r = 1 for i in range(index): r *= base r %= mod return r 시간복잡도가 $O(b)$이다. r이 $a^b$까지 커지기 때문에 overflow일어나기 매우 쉽다. 2.2 개선된 방법 def powMod2(base, index, mod): if index == 1: return base if index % 2 == 0: r = pow..

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$를 예로 들..