양자알고리즘의 꽃이라 할 수 있는 쇼어의 알고리즘에 대해 알아보자. 쇼어에 앞서 Simon은 2대1 함수의 주기를 구하는 알고리즘을 고안했다. 이 알고리즘은 주기를 구하기 위해 n-bit Hadamard transform을 이용한다. 쇼어는 QFT(Quantum Fourier Transform)을 이용하여 함수의 주기를 구하는 일반적인 알고리즘을 고안했고 이를 이용하면 정수를 다항식 시간 안에 소인수 분해할 수 있다. 일반적으로 큰 정수의 소인수분해는 대단히 어렵고 이를 이용한 RSA라 불리는 암호체계가 현재로서는 가장 안전한 암호체계의 기초가 되고 있다. 그런데 양자컴퓨터가 구현되면 큰 수의 소인수분해가 가능해지고 RSA는 더 이상 쓰일 수 없다. 바로 이점 이 양자컴퓨터를 뜨게 한 것이다.
< Finding the period >
먼저 함수의 주기를 찾는 과정을 살펴보자. 이 과정은 조금 복잡한데 크게 세 부분으로 나누어 서술하겠다. 첫째로 쇼어의 알고리즘에서 수행하는 연산을 차례로 기술하겠다. 둘째로 연산결과 측정된 값에서 얻는 주기에 대한 정보가 무엇인지 서술하겠다. 마지막으로 주기를 구하는 방법을 서술하겠다.
먼저 쇼어의 알고리즘이 수행하는 연산을 살펴보자. 우리가 주기를 찾아야 하는 함수는 n-bit 입력과 m-bit 출력을 갖는 함수이고 주기 r을 갖는다. 이때 다음의 조건을 만족한다고 가정된다.
 |
[1] |
알고리즘에서 핵심적인 역할을 수행하는 것이 QFT인데 이는 다음과 같이 정의되는 변환이다.
 |
[2] |
이제 알고리즘을 살펴보자. 먼저 주어진 상태|x>를 다음과 같이 변환해준다.
 |
[3] |
여기서 출력레지스터를 측정하면 주어진 상태가 하나의 함수 값을 갖는 상태만의 중첩이 되어 다음과 같이 바뀐다.
 |
[4] |
여기서 A는 같은 함수값을 갖는 |x>의 개수이고 N, A사이에 다음의 관계가 성립한다.
 |
[5] |
[4]의 상태에 QFT를 가하면 다음의 상태로 변환된다.
 |
[6] |
[6]의 상태를 측정하여 |y>를 얻는 것에서 이 알고리즘이 수행해야 하는 양자연산은 끝이 난다.
이제 위의 연산결과가 어떤 의미를 갖는지 알아보자. 먼저 [6]의 상태를 측정하여 y를 얻을 확률은 다음과 같다.
 |
[7] |
[7]을 보면 yr/N이 정수에 가까운 경우 sum내의 각항이 보강적으로 더해져서 y값이 측정될 확률이 높다는 것을 알 수 있다. 이를 테면 N/r이 정수가 될 경우 확률은 다음과 같다.
 |
[8] |
한편 [7]식의 sum은 등비수열의 합의 형태이므로 다음의 형태로 간략하게 나타낼 수 있다.
 |
[9] |
한편 함수의 주기 r에 대해 y가 가질 수 있는 값 {0, 1, 2, ..., N-1}중 정확히 r개의 값이 다음의 조건을 만족한다.
 |
[10] |
쎄타의 정의와 [10]에 의해 정확히 r개의 y값에 대해 다음이 성립한다.
 |
[11] |
[11]식을 만족하는 y값은 sum의 계산에서 등비수열의 각 항들이 모두 복소평면 상에서 허수부가 양의 값을 갖기 때문에 sum을 한 결과가 보강간섭을 일으킨다. 그 결과 [11]식을 만족하는 y가 측정될 확률도 다른 값에 비해 매우 높아지는데 이를 자세히 살펴보자. 먼저 다음의 두 부등식이 성립함을 기하학적으로 간단히 증명할 수 있다.
 |
[12] |
삼각부등식과 [12]식에 의해 다음의 부등식이 성립한다.
 |
[13] |
2/A 정도의 오차를 무시하면 결국 [10]식을 만족하는 y값이 측정돨 확률은 다음과 같이 된다.
 |
[14] |
[14]식을 만족하는 y값이 정확히 r개 있으므로 측정된 y값이 [10]식을 만족할 확률은 다음과 같다.
 |
[15] |
이제 [10]식을 만족하는 y값을 구하는 것의 의미를 알아보자. 먼저 [10]식을 다음과 같이 다시 쓸 수 있다.
 |
[16] |
여기서 k는 y가 조건을 만족하게 하는 정수이다. 일단 y값이 정해지면 [16]식을 만족하는 유리수 k/r은 유일하게 결정된다.(왜 그런지 여기서는 쓰지 않는데 그 이유는 물리가 아닌 단순한 수학이기 때문이다.) 뿐만 아니라 [16]에서 결정되는 k/r은 연속분수를 이용하여 효율적으로 계산되어 구해진다. [16]식을 만족하는 k와 r이 서로 소라면 계산에서 구한 k/r의 분모가 r이 된다. 그러나 서로 소가 아닌 경우는 계산에서 구한 k/r의 분모는 r의 약수일 뿐이다.
요약하면 [10]식을 만족하는 y가 측정될 확률은 [15]식으로 주어지는데 이 경우 주기 또는 주기의 약수를 계산을 통해 구할 수 있는 것이다.
이제 함수의 주기 r을 찾는 방법을 보자. 먼저 쇼어의 연산을 수행하여 y를 측정한다. 그 결과 [10]을 만족하지 않는 y가 측정될 수도 있는데 이 경우 측정된 y는 함수의 주기를 찾는데 도움을 주지 못하므로 다시 연산을 수행하여 y를 측정해야 한다. 반대로 [10]을 만족하는 y가 측정되면 이 값을 이용해 함수의 주기 r을 구하는데 사용할 수 있다. 결국 [10]식을 만족하는 y가 측정될 때까지 연산을 반복해야 한다. 원하는 y를 얻을 확률은 [15]식과 같다.
일단 원하는 y를 측정하면 [10]식과 동치인 [15]식을 만족하는 k/r을 연속분수를 이용하여 계산한다. 계산결과의 분모는 원하는 주기 r일 수도 있고 r의 약수일 수도 있다. 이것을 확인하는 것은 고전컴퓨터로도 쉽다. 확인 결과 구한 값이 주기가 되면 우리는 주기를 구한 것이 된다. 그러나 주기가 아닌 약수일 수도 있다. 이 경우 원하는 주기를 찾는 세 가지 방법이 있다.
첫째로 측정된 y값을 약간 바꾸어 준 후 k/r을 다시 계산하고 그 결과가 주기인지 확인하는 것이다. 둘째는 계산된 k/r의 분모의 배수가 주기가 되는 것은 분명하므로 분모의 배수가 주기인지를 검사하는 것이다. 이 두 가지 방법은 이미 측정된 y값을 바탕으로 하여 고전컴퓨터로 주기를 찾는 방법이다. 마지막 방법은 쇼어의 연산을 다시 수행하여 새로운 y를 측정하는 것이다. 그래서 다시 k'/r을 계산하여 분모가 주기인지 검사한다. 이렇게 해도 분모가 주기가 아니라면 처음 구한 분모와 둘째로 구한 분모의 최소공배수가 주기인지 검사한다. 그래도 주기가 아니면 쇼어의 연산을 다시 수행한다. 확률적으로 쇼어의 연산을 계속 수행해야 되는 경우는 매우 드물다. k와 k'이 서로 소이면 두 경우에서 구한 분모의 최소공배수가 정확히 r이 되기 때문이다. 합리적인 추론 결과 k와 k'이 서로 소일 확률은 0.607 정도로 운이 아주 나쁘지 않은 경우 외에는 몇 번의 연산으로 함수의 주기를 알 수 있는 것이다.
< Factoring >
다음 기회에 쓰겠습니다.
< RSA >
RSA방법은 public key를 이용한 암호 체계이다. secret key만을 이용한 암호체계는 암호의 작성을 위해 반드시 secret key의 교환을 필요로 한다. 때문에 암호를 공유하려면 전송자와 수신자가 secret key를 교환해야 하고 교환 시에 암호가 누출될 수 있다. (이를테면 도청, 강탈, 납치, 고문 등의 방법이 있다.) 이런 문제로 많은 사람이 암호를 사용해서 정보를 전송하는 방법으로는 부적합하다. RSA는public key를 이용해 암호를 작성하고 secret key를 이용해 암호를 푸는 방법으로 많은 사람이 암호를 작성할 수 있는 장점이 있다.
RSA는 두개의 public key n, e와 두개의 secret key m, d로 구성된다. public key는 암호를 작성하고자 하는 모든 이에게 공개되어 암호의 작성에 사용된다. secret key는 암호를 해독하는 측에만 공개되어 암호의 해독에 쓰인다. n은 소인수분해가 매우 어려운 큰 정수로 정하는데 보통 소인수분해가 가장 어려운 두 개의 매우 큰 소수의 곱으로 한다. d는 적당히 큰 정수이면 된다. m은 n과 서로 소이면서 n보다 작은 자연수의 개수로 n에 관계하는 함수이다. 수학적으로 m은 n의 오일러 함수값이다. n을 소인수분해 했을 때 m은 다음과 같다.
 |
[1] |
n을 소인수 분해할 수 있을 때에만 m값은 위식에서 쉽게 구해진다. 한편 d는 다음을 만족하는 정수이면 된다.
 |
[2] |
secret key를 모르는 상태에서 public key로부터 secret key를 구하려면 먼저 m을 구해야 d를 구할 수 있다.
이제 암호의 작동원리를 알아보자. 어떤 정보 a를 암호화한다고 하자. 전송자는 다음의 규칙으로 a를 b로 변환하여 전송한다.
 |
[3] |
수신자는 다음의 규칙으로 b를 a로 역변환한다.
 |
[4] |
위 식에서 마지막 단계에서는 다음과 같은 오일러 정리가 이용되었다.
 |
[5] |
이상의 과정에서 암호는 public key를 이용하여 쉽게 작성되고 secret key를 이용하여 쉽게 해독된다. 그러나 secret key를 모르는 상태에서는 해독이 어렵다.
secret key를 모르는 상태에서 public key로부터 secret key를 구하려면 먼저 m을 알아야 d를 구할 수 있으므로 이 암호법의 성공여부는 m값의 보안에 있다. 그런데 공개된 n값에서 m을 구하려면 먼저 n을 소인수분해 해야 한다. 그런데 소인수분해를 위한 기존의 알고리즘은 인수분해 하려는 정수의 자리수가 늘수록 연산횟수가 지수적으로 증가한다. 참고로 두 소수의 곱으로 이루어진 129자리 정수를 소인수 분해하는 문제를 RSA의 제안자들이 제시하였는데 1994년에야 1600여대의 컴퓨터를 돌려서 인수분해가 되었다. 현재 RSA에서 쓰이는 정수는 150자리를 갖는 것으로 이를 소인수 분해하는 것은 (알고리듬이 자리수에 지수적으로 의존하지 않게 되는 이상) 고전컴퓨터로는 전혀 불가능하다고 할 수 있다. (우연히 찍은 것이 맞는 소위 째수라는 가능성도 있기는 하다.) 그런데 위에서 밝힌 바와 같이 쇼어의 알고리즘을 이용하면 자리수에 다항식 의존성을 갖는 연산 회수로 소인수분해가 가능하고 secret key가 공개되어 RSA는 깨지는 것이다.