잡소리 파트 )

본의 아니게, 양자역학을 공부 하게 ㄷㅚㅆ는데요, 우선 시초를 마련해주신 썬 서울님께 감사를 드리며, 다짜고짜 휘발유 뿌리신 익명의 분들과 듀크님께 고마움을 표 합니다.
일단 퀀텀컴터에 ‘ㅋ’도 모르던 입장에서 새로운걸 알아 간다는 즐거움은 다른것에 비할게 없는것 같습니다. 역시 이래서, 젓갈은 삭히고 사람은 배워야 한다는 말이 있나 봅니다.

대략, 컴터 컴터의 개발에 천문학적인 돈을 들이게 만든 사람중 한명이 Peter shor란 사람인것 같습니다.

이분의 알고리듬을 보고 있노라면, 참 수학자들의 수의 비밀을 파 혜치는 작업역시 컴터 프로그램 짜는 노가다 버금간다란걸 다시 생각 하게 됩니다.

제가 듀크님께 물어 봤던건, 어떻게 RSA의 키값과 상관없이, 이 많은 연산을 쉽게 끝낼수 있는가에 대한 how였는데, 막상 설명이 없어시기에, 혼자 삽질좀 했는데요. (개인적으로 암호는 절대 하나만 쓰이지 않습니다. 즉 RSA는 풀더라도, 70조의 키 조합이 필요한 DES 3번 꼬아 버린 3중 DES역시 풀어야 하고, 또 푼다 하더라도, 안의 내용의 각 나라별로 다양한 암호방식으로 인코딩 됐다면 이건 또다른 이야기가 됩니다.)

부적절한 양자 컴터 이해)

일단 양자 컴터는 양자 의 기본 성질을 이용한다는데요.

기본적으로 양자를 bit으로 사용한다는데, 저는 아직도 이개념이 애매 모호 합니다.

우선 양자라고 말하는게 atom인데, 이 atom의 정체가 먼지 참 궁금하네요, 그냥 electron이 하나를 갖고 있는 아무 양자를쓰는건지 , 아니면 수소를 쓰는건지 애매 합니다.

또 큐빗이 물리적인 공간 즉 atom trap같은 걸 지칭하는건지, 아니면 atom하나 자체를 bit으로 쓰는 개념을 이용하는건지 애매 하네요.

여튼 무수한 원자를 한곳에 중첩을 시킬수 있다고 합니다.
또 중첩된 곳의 원자의 값은 0(up) 또는 1(down) 중간값(left or right)값을 갖고 똑같은 물리적 위치에 위의 값을 갖은 상태로 증첩되어 존재 합니다(관찰전입니다).

그후, 양자의 특성중 하나인, 관찰후 붕괴 때문에 중첩된 무수한 원자들은 하나의 값을 갖는것들만 빼고 나머지는 붕괴 됩니다.

이 점이 직렬연산을 병렬로바꾼 점입니다.

Shor’s 알고리듬 뇌가다)

이건 노가다보다 제 뇌쪽에 영향을 직접 끼치길래, 부적절한 단어의 결합을 선택합니다.

부디 거부 반응 없으시길 바랍니다.

즉 100자리 소수(N)든 뭐든 하나 잡아 냅니다.

임의의 수 x를 구한후 (X^a)mod N 값을 구합니다.

여기서 a의값은 다양하게 올라 갈수 있습니다.
Shor란 분께서 2*n^2 와 3*n^2 의 범위의 수 하나를 찍으라고 이야기 합니다.
이 숫자가 10 이면 a 값은 0부터 10까지 됩니다.

근데 보시다 시피, 2*(100자리수 ^2 ) 와 3*(100^3) 면 자릿수가 많이 짜증납니다.
또 부분이 이해하기 애매한것중,저 범위의 값이 아닌 훨씬 적은 수를 찍어도 답은 나올수 있습니다.

여튼 (X^a)mod N 대략 a를 10으로 잡고 계산을 하다 보면, 나머지를 갖는 값들이 일정 주기를 갖게 됩니다.

즉 1,5,7,8,1,5,7,8,1,5,7,8.. 이렇게 되면 주기 r=4가 되고, shor의 알고리듬에 있는 식중 r을 통해서, (x^(r/2) +1)(x (r/2)^-1)=0 mod N 이 성립이 됩니다.

즉 GCD((x (r/2)^-1) , N)=0 또는 GCD((x (r/2)^+1) , N)=0이 성립됩니다.

이 알고리듬의 애매 한것중 하나는 확률을 통해서 값을 구 하는 것이기에 단번에 100%의 값을 주지 않습니다. 그러나 빠른 속도가 장점을 이용 몇자례를 시도 하게 되면 답을 얻을수 있는 확률이 올라갑니다.

간단한 소인수 분해를 예시를 들면,

3*5=15 p=3, q=5 N값은 15이고 무작위값 x는 8로 잡고 a승의 값은 0-10까지 하면요.

여기서 6개의 큐빗을 만들어 놓고 앞의 3자리 비트는 a의 값, 뒤의 3자리 비트는 (X^a)mod N의 값을 놓습니다.

즉 이론대로 라면, 6비트의 규빗들이 한곳에 모여 있게 되고요,그곳에 존재 하는 값들은 앞 3비트의 경우 0-6 값, 그 옆3자리 비트(뒤의 3비트)에는 나머지값이 저장되어 있고, 그 값들은 1,8,4,2,1,8,4,2 이러 합니다.

뒤의 3비트를 측정하게 될경우 ‘1,8,4,2,1,8,4,2’ 중 하나의 값을 갖는것을 빼고 나머지는 다 붕괴됩니다.

총 6비트가 측정된 하나의 값을 갖고 나머지 (앞의 3비트포함)이 붕괴가 된다고 합니다.

만약 측정된 뒤의 3비트 값이 4 라면 붕괴된 앞의 3비트값을 측정 하기 위해서 Foruier transform 이란게 쓰이는데, 이개념이 애매 하네요.

제 돌머리의 이해로는 앞의 3비트 값은 붕괴가 되었지만, 앞의 3비트가 붕괴가 되지 않았다면 2,6,10,14 이렇게 4 주기로 커지는값을 갖고 있었을겁니다.

Foruier transform를 통해서 붕괴된 앞의 3비트 값을 sample을 뽑아 내게 됩니다,

결국 이 sample들이 set이루게 되면 그 값들의 주기를 찾아 낼수 있습니다.

이런과정을 통해서 주기 값만 찾아 내면 큰 소수의 소인수 분해는 바로 분해가 되는데요.

그 다음 과정 역시 제 컴터로는 큰 문제가 되는데 슈퍼 컴터를 이용하면 큰 문제가 아닌가 봅니다.(제가 찾아낸 한수의 주기는 대략 70000개 이상부터 시작된게 있는데 말이지요.)

여튼 물리 고수님들 도움좀 부탁드리겠습니다.

링크 첨부 합니다.

http://en.wikipedia.org/wiki/Shor’s_algorithm 알고리듬 설명해주고 있습니다.

http://en.wikipedia.org/wiki/RSA RSA에 관한 간략한 질문입니다.

http://primes.utm.edu/largest.html#largest 대략 덤빌려고 작정했던 수중 일부 입니다.