ADVERTISEMENT

양자컴퓨터란 무엇인가? [2]

중앙일보

입력

업데이트

술만먹으면...
뭔가를 마구 소인수분해 해버리고 싶은 충동에 어찌할바를 모른다.... 심지어는 지금 앉아 있는 math 8의 8자를 소인수 분해하고는 기뻐하고 있다...쩝.. 오늘도 술마시고 걸어오면서, 차 번호를 소인수분해 했다...
물론, 나는, 아무에게도 그런 이야기를 하지 않았지... 얼마전에, 수학과 95모임에서, 술마시고 오는길에, 소인수 분해를 하는과정을 이야기했더니, 애들이 다 기겁을 하려고 했다....나는 보통, 그런것을 잘 이야기 하지 않는데, 수학과 애들이라면 이해할줄 알았다..내가 멍청했지... 쩝.....세상에는 나를 이해해주는 사람이 없다는 것은 아니다...다만, 내가 이상한 거겠지...
(KAIST의 ′과수원 BBS′에서 인용)
양자컴퓨터가 왜 그렇게 각광을 받고 있는지 알기 위해서는 먼저 소인수분해에 대해 생각해 볼 필요가 있다. 뜬금없이 중고등학교 수학시간으로 돌아가는 것이 아닌가하고 의아해하는 독자도 있겠지만 이는 매우 중요한 문제이므로 차분히 읽어주기 바라는 바이다.

소인수분해(素因數分解-factorization in prime factors)란 주어진 합성수를 소수(素數)의 곱의 꼴로 바꾸는 일을 말한다. 소수란 1과 그 자신만으로만 나눠지는 수로 2, 3, 5, 7, 11, ... 등이 있다. 여기까지는 매우 쉽다.

Euclid, B.C.300년 경 고대 그리스의 대 수학자 유클리드는 배리법이란 방법으로 소수는 무한히 존재한다는 것을 증명했으나 현재까지 소수의 규칙성을 발견한 사람은 없으며 소수가 규칙성을 갖는지 조차 증명이 안된 상태이다. 만일 소수가 등장하는 규칙을 발견하는 사람이 나온다면 필즈 메달(4년에 한 번씩 주어지는 수학의 노벨상과도 같은 상, 수학자에게는 가장 큰 영광이다)은 따놓은 당상이므로 수학에 자신있는 pcBee의 회원이라면 도전해보기 바란다.

임의의 합성수 a는 유한 개의 소수만의 곱으로 나타낼 수 있다. 이 때, a의 소수인 인수(因數)를 a의 소인수라 하고, a를 소인수의 곱의 꼴로 나타내는 일을 a를 소인수분해한다고 한다.
합성수는 곱으로 나타나는 소인수들의 순서를 무시한다면, 모두 단 한가지로 소인수분해된다. 이 사실을 소인수분해의 일의성(一意性)이라 한다. 이를테면, 51688은 51688=23×7×13×71의 1가지로 소인수분해된다.

수학 시간에 곱셈보다 나눗셈이 어렵다고 느낀 사람들이 많이 있을 것이다. 소수끼리 곱해서 합성수를 만드는 것은 소형 계산기로도 충분할만큼 매우 쉬운 일이지만 합성수를 소수의 곱으로 분해하는 일은 슈퍼 컴퓨터로도 긴 시간이 걸릴만큼 어려운 작업이다.

어떤 알고리즘이 얼마나 빨리 문제를 풀 수 있는가를 알기 위해서는 입력에 대해 알고리즘이 완료될 때까지의 스텝의 횟수를 계산하는 것이다. N이라는 숫자를 소인수분해 할 경우 입력값은 N이고 입력의 크기는 logN이다. 효과적인 알고리즘은 실행속도가 입력크기의 정도의 다항식으로 나타나야 한다.(약 2내지 3승 정도이다.)

기존의 컴퓨터에서 가장 잘 알려진 소인수분해 알고리즘은 O(exp[(64/9)1/3(ln lnN)2/3 }]) 의 단계로 실행된다. 그러므로 이 알고리즘은 입력크기인 logN의 크기에 따라 지수(exponential)함수에 비례하여 많은 시간이 걸린다는 것을 알 수 있다.

예를 들어 1994년 RSA129로 알려진 129자리 숫자를 소인수분해 하는 데에는 이 알고리즘을 이용하여 세계에 있는 1,600여대의 워크스테이션을 병렬로 연결하여 8개월이 걸렸다.
이 알고리즘대로 250자리의 수라면 800,000년이 걸릴 것이며, 1,000자리라면 1025년이 걸릴 것이다. 이것은 우주의 나이보다 더 많은 시간이다. 그냥 더 많은 것이 아니라 우주가 만들어져서 지금까지 성장한 과정을 다시 수 십억번을 반복해도 턱없이 모자른 시간이다.

소인수분해는 꽁꽁 묶인 실타래를 푸는 과정을 연상시킬 만큼 복잡하고 지루하다. 알렉산더는 고르디우스의 매듭(Gordian Knot)이라 불리는 실타래를 푸는데 주저없이 단칼에 매듭을 잘라버렸다지만 소인수분해에는 이런 편법이 존재하지 않는다. 이렇게 현존하는 최고의 시스템들을 동시에 가동시켜도 숫자가 조금만 커지면 소인수분해가 불가능에 가까울만큼 오래 걸리는 것을 보면 컴퓨터라는 첨단기기에 무기력감을 느끼는 게 당연하다.

왜 소인수분해가 중요한가?
지금까지 지루한 이야기를 읽은 독자라면 한 번 쯤 의구심을 갖게 될 것이다. 그까짓 소인수분해 따위가 뭐그리 대단하길래 계산이 끝나는데 수 만년이 걸리는 것을 걱정하는가 하고 말이다.

미처 신경을 쓰지 않고 있겠지만 컴퓨터에서 소인수분해 문제는 매우 중요한 위치를 차지한다. 대부분의 공개키 암호 시스템(우리가 컴퓨터를 사용하면서 쓰는 CD키나 각종 패스워드들은 공개키 암호 시스템(public key cryptosystem)에 의존하고 있다.)은 합성수에 소수를 숨겨놓는 방법으로 암호를 만들기 때문이다.

따라서 대부분의 암호들은 소인수분해를 해서 소수들을 찾아내면 그 조합으로 새로운 암호를 생성할 수 있다. 소인수분해만 빨리 해낸다면 누구라도 비밀문서를 읽을 수 있고 서명을 위조할 수도 있다. 쉽게 얘기해 스타크래프트 CD키의 소수만 알면 버젓이 복제 CD로도 당당히 베틀넷에 들어갈 수 있는 것이다.

큰 숫자에 대한 소인수분해의 어려움은 공개키 방식의 암호화에 있어서 필수적인 것이었다.
은행에서 이용하는 암호코드는 약 250자리 숫자의 소인수분해에 의존하고 있다. 최근에 양자컴퓨터에서 사용할 수 있는 소인수분해 알고리즘이 개발되었는데(Shor 알고리즘으로 알려져 있다.) O((logN)2+x))로 실행된다. (x는 작다).

이것은 대략 입력크기의 4승 정도가 된다. 따라서 1,000자리 합성수를 소인수분해하는데 단지 수만 단계만 필요하다. 이것은 소인수분해에 근거를 둔 공개키 암호시스템이 더 이상 통하지 않음을 의미한다!

지금까지는 하드웨어의 발전 속도에 맞게 적당히 암호의 자리수만 늘리면 시스템을 보호할 수 있었다. 무어의 법칙이 그대로 통한다 하더라도 한 자리만 암호의 단위를 늘려도 이를 따라잡기 위해서 CPU 제작자들은 몇 년동안 연산속도를 높이기 위해 피땀을 흘려야 하는 것이다.

소인수분해를 잘하면 상금도 탄다!

이런 창과 방패의 싸움에서 소인소분해 문제는 난공불락의 방패인 셈이지만 양자컴퓨터가 실용화되면 소인수분해 알고리즘으로 작성된 암호체계는 모두 폐기되어야 할 정도로 양자컴퓨터는 강력한 계산능력을 갖고 있는 것이다.

소인수분해보다 조금 더 풀기 어렵다고 하는 이산대수 문제 역시 양자컴퓨터로 쉽게 답을 구할 수 있으므로 양자컴퓨터의 등장은 더욱더 복잡한 실타래의 등장을 요구하면서 우리들의 실생활에도 큰 변화를 몰고 올 것을 예견시키는 것이다.

정구정
자료제공:pcBee(http://www.pcbee.co.kr)

 

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT