잡소리 파트 )

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

대략, 컴터 컴터의 개발에 천문학적인 돈을 들이게 만든 사람중 한명이 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 대략 덤빌려고 작정했던 수중 일부 입니다.

검색공부를 하시다 보면, 실제로 무엇이 문제인가 코딩해 보고 싶은 욕망이 들기도 합니다. 저도 천재도 못하는 것을 번득이는 영감이 떠오른다고 착각하고 코딩하기도 했습니다.

제가 조금 먼저 프로그램세계를 산것 같아서, 시간을 내어 연습을 많이해 보시라고 권하고 싶었던 것이. 표현이 까칠했었나 봅니다.

참~ 이상하지요? 글로만 적어서, 오해의 소지도 많은것이 리플일텐데. 그런 것이 드러나는 가 봅니다.

천천히 하나씩 해 보세요. 일단 FFT연산부터~? 모든 ‘인식’시스템은 이것을 기초로 한다고 봐도 무리가 없습니다. 음성인식,패턴인식(지문,홍체…)

제가 좀 예의를 넘어서 표현이 나가는 듯 해서, 사과로 마무리 지었던 것이고요.
단순 RSA가 그렇게 쉽지 않으니, 실제로 RSA하나를 작은 단위부터 격파해 보시고요.

제쪽 업무에서는. MD5 해쉬값을 1024bit Modulus를 가진 RSA로 암호화 한것을 다룹니다.

궁금중이 많은 사람이, 많은 것을 접하게 되고, 많은 것을 얻습니다.
하지만! 꼭, 체험해 보세요.
– 둨-

질문하신 사안중 양자컴퓨터에 대해, 조금 차분히 정리해 놓았다고 느껴지는 링크 하나 올립니다.
quanta.khu.ac.kr/physics/98Undergraduate_Theses/kwk/index.htm

>>단순 RSA가 그렇게 쉽지 않으니, 실제로 RSA하나를 작은 단위부터 격파해 보시고요.

저랑은 다른 방향이시네요, 저는 DES를 많이 공략하는 쪽에 시간을 투자 했었습니다. 머리 쓰는것보다는 직접 뭔가를 집어 던지던가 무작위 대입법을 통해 최대한 빨리 키 대입 시도 하는게 더 흥미로웠던것 같습니다.

생각이 이렇게 돌아가니, 제가 파는 쪽은 분산 시스템을 통해 한곳을 공격 시키는 걸로 가게 됩니다.

또 분산시스템을 컨트롤 할려다 보면 자연히 OS와 더불어서 스케쥴링까지 먹어야 되고, Thread도 필수로 잡히게되는것 같습니다.

또 분산 시스템 구현 자체가 넷떡이라서 이부분도 소홀히 할수 없고, 같은 값을 전송시키지 않게끔 부위를 나눠서 공격 시키는 프로그래밍까지 겸해야 한다란 생각을 하게 되더군요.

방향이 다르니, 파는게 다른것 같음을 다시 느낍니다. 저는 알고리듬 보다는 컴터를 최대한 잔혹하게 부려 먹어서, 기존의 데이터 량으로는 상상도 못하는걸 건드릴려고 하는데, 좀 다른것 같습니다.