양자컴퓨터와 쇼어 알고리즘

목차

1. 확률론적 증거로 소수의 속성을 증명하기

2. 높은 확률로 비밀암호 깨기

 

 

---

 

 

---

 

 

1. 확률론적 증거로 소수의 속성을 증명하기

 

지난 몇 십 년간 우연의 위상은 많이 향상되었습니다. 더 이상 예측불허의 방해 요소가 아니라 생산적인 역할을 하는 긍정적 요인으로 인식되고 있습니다.

우연은 진리를 찾는 데도 도움이 됩니다.

큰 수 n을 가정해 봅니다. 적어도 천만 자리 이상의 수여야 합니다. 암호 연구 분야에서는 n이 소수인지 알아내는 것이 아주 중요합니다. 그러나 n이 너무 큰 수이기 때문에 직접적인 방법으로 알아내기는 힘들어, 즉 다른 간접적인 방법을 생각해 내야 합니다.

 

 

 

수 이론에 의하면, n이 소수가 아닐 경우 1에서 n사이의 수 가운데 적어도 절반은 속성 E를 가집니다. 이 속성 E는 간단한 검사로 확인할 수 있지만, 반면 n이 소수일 경우에는 n보다 작은 수 중 속성 E를 가지는 수가 없습니다(여기서 속성 E의 내용은 중요하지 않다). 그렇다면 난수 생성기 n보다 작은 수 x를 뽑아 이 수가 속성 E를 가지는지 알아봄으로써 n이 소수인지 아닌지 판단할 수 있을 것입니다.

만약 그 결과가 부정적이라면 n은 정말 소수가 아니거나, 소수인데 하필이면 E의 속성을 가지지 않는 절반의 수 중 하나가 뽑힌 것이거나 둘 중 하나일 것입니다. 여러 번 시도했을 때 이런 재수 없는 경우가 반복될 확률은 매우 낮습니다. 20번 시도했을 때 n이 소수가 아닐 경우의 확률은 1: 220으로 약 1대 백만 정도 입니다.

 

 

 

이렇게 되면 '이 수가 소수일 확률은 매우 높다'는 명제를 쓸 수 있게 됩니다. 대부분의 분야에서는 이 정도의 높은 확률이면 참인 명제로 받아 들입니다. 어떤 분야에서는 심지어 운이 좋아 답을 맞히는 경우도 용인이 되기도 합니다.

만약 비밀금고의 암호가 50퍼센트의 확률로 깰 수 있는 것이라면 금고의 주인은 밤마다 잠을 설칠 것입니다. 마치 대문 앞에 열쇠가 잔뜩 든 양동이(양동이 속에 든 열쇠 중 절반은 맞는 열쇠라고 하자)를 두고 자는 것과 같습니다.

그러나 응용할 때 대부분 고전적인 방법을 택합니다. 고작 99.9퍼센트의 확률로 똑바로 서 있는 탑에 올라가고 싶은 사람은 없을 데니 말입니다.

 

---

 

 

2. 높은 확률로 비밀암호 깨기 

 

피터 쇼어의 알고리즘은 양자컴퓨터를 이용해 큰 수의 곱으로부터 인수를 알아내는 방법입니다. 여기서 소인수분해의 어려움이 암호화 체계의 안전성을 확보하는 데 엄청나게 중요하다는 사실을 상기할 필요가 있습니다. 그래서 쇼어 알고리즘이 나왔을 때 그런 난리가 났던 것이죠.

 

p와 q라는 큰 소수가 있고, 두 수의 곱을 n이라고 한다. 그리고 1과 n, 사이에 놓인 임의의 수 x를 만들어 냅니다.

랜덤 넘버 제너레이터를 사용 하면 컴퓨터가 순식간에 만들어낼 수 있습니다. x의 특정한 인지값, 즉 순환마디를 알고 있다면, 그리고 이 순환마디가 속성 E를 가진다면 x를 통해 p와 q를 구할 수 있습니다. 여기서 속성 E는 전체 경우의 50퍼센트를 충족합니다. 이때 충분히 높은 확률로 x의 순한마디를 토해 내도록 양자컴퓨터를 프로그래밍하면 되는 것이죠.

 

 

 

쇼어 알고리즘은 다음과 같은 과정을 거칩니다.

1. 1과 n사이에 놓인 임의의 수 x를 만든다(이 과정은 순식간에 완료 된다).

2. 양자컴퓨터로 x의 순환마디가 될 만한 수를 계산한다(만약 언젠가 양자컴퓨터가 만들어진다면 이 과정도 눈 깜짝할 사이에 해결될 것이다).

3. 진짜 x의 순환마디를 구할 때까지 2의 과정을 반복한다(보통 컴퓨터로도 빠른 시간 내에 검사할 수 있다).

4. 순환마디가 속성 E를 가지는지 알아본다(이것도 역시 보통 컴퓨터로 할 수 있는 일이다). 결과가 부정적이면(E의 속성을 가지지 않으면) 새로운 x로 1부터 다시 시작한다.

5. x를 이용해 p와 q를 구한다. 이제 비밀암호를 깰 수 있다.

 

 

 

여기서 우연은 두 번 중요한 역할을 하게 됩니다.

첫 번째, 순환마디는 특정한 확률로만 찾아지며,

두 번째, x중 적어도 50퍼센트만이 인수를 찾는 데 쓸모가 있습니다.

암호해독이라는 목적에 있어서는 그리 나쁜 조건도 아 니죠. 조금 늦게 해독한다고 해서 큰일이 나는 것도 아니고, 양자컴퓨터 에게 100퍼센트의 정확한 답을 기대하는 것은 원칙적으로 불가능하기 때문입니다. 그리고 가만히 들여다보면 세상은 원래 확률에 지배받는 구조를 가지고 있기 때문에 더 정확한 진술은 불가능합니다.

 

---