Complexity Theory 세계로... Complexity Theory(계산복잡도 이론)은 암호학에 필요한 이론이라고 한다. 우리가 알고리즘때 사용하는 Big-O표기법도 Complexity Theory에서 나왔다. (알고리즘도 여기에 포함된다고 한다.) 즉 Complexity Theory란 튜링머신(컴퓨터)이 어떤 연산을 하는데 얼마나 걸리는지를 분석하는 컴퓨터 과학 분야이다. 미리 알아둬야할 컨셉이 있다. 어떤 문제가 어렵다는 것은 해당 문제를 해결하는 시간이 오래 걸린다는 뜻이다. 사실 "오래 걸린다"도 추상적이긴 하지만 "어렵다"도 마찬가지이니 의미만 이해하고 넘어가자. Halting Problem 어떤 프로그램과 인풋이 주어졌을 때 해당 프로그램이 정지하는 지(끝나는 지) 판정하시오. Hal..