|
'''
이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' |
|||||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
<colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
쇼어 알고리즘(Shor's algorithm)은 다항 시간안에 소인수 분해를 할 수 있는 양자 알고리즘이다. 피터 쇼어(Peter Shor)가 1994년의 논문[1]에서 제안한 알고리즘이다. 현재 다항 시간안에 소인수분해를 하는 알고리즘중 가장 빠른 알고리즘이라고 알려져 있다.[2]쇼어 알고리즘이 중요한 이유는 RSA 암호화와 관련이 있다. RSA 암호화는 큰 소수의 합성수를 소인수로 분해하는 문제는 고전 컴퓨터로 다항 시간에 풀 수 없는 문제로 알려져 있다. 따라서 RSA 암호화 체계는 소인수 분해의 어려움에 기반하여 설계되어 있다고 할 수 있다. 그래서 쇼어의 양자 알고리즘으로 정수의 소인수 분해 문제를 다항 시간 안에 풀 수 있게 되면, RSA 암호화를 사용하는 모든 서비스가 큰 보안 위협에 처하게 된다.
2. 쇼어 알고리즘의 고전적 구현
쇼어 알고리즘은 합동 관계의 주기성을 이용하여 소인수 분해를 한다. 자세한 원리는 이 영상 참고. 따라서 쇼어 알고리즘 자체는 고전 컴퓨터로도 구현할 수 있다. 다만, 고전 컴퓨터로 구현한 쇼어 알고리즘은 여전히 지수적인 시간 복잡도를 가지기 때문에, 다항 시간에 소인수 분해를 하려면 양자 컴퓨터를 이용해야 한다.쇼어 소인수분해 방법:
입력: 두 개의 소수 p, q의 곱으로 만들어진 합성수 N=p*q
출력: N의 소인수 p, q
절차:
1. 1보다 크고 N보다 작은 임의[arbitrary]의 정수 a를 선택한다.
2. 만일 N과 a의 최대공약수 gcd가 1이 아니면, 운이 좋게 소인수 p를 발견한 것이다. 따라서 p=gcd, q=N//gcd를 반환하고 종료한다.
3. 함수 f(x)=a^x (mod N)의 주기 r을 찾는다. 여기서 찾은 주기 r이 짝수가 아니라면, 1번 단계부터 다시 시작한다.
4. 주기 r로부터 두 개의 최대공약수 gcd1=gcd(N, a^(r//2)) + 1), gcd2=gcd(N, a^(r//2)) - 1)를 찾는다.
5. 여기서 찾은 두 개의 수 gcd1, gcd2 중 하나라도 1이거나 N이라면 1번 단계부터 다시 시작한다. 아니라면, 마침내 소인수들을 찾았으므로 gcd1, gcd2를 반환하고 종료한다.
입력: 두 개의 소수 p, q의 곱으로 만들어진 합성수 N=p*q
출력: N의 소인수 p, q
절차:
1. 1보다 크고 N보다 작은 임의[arbitrary]의 정수 a를 선택한다.
2. 만일 N과 a의 최대공약수 gcd가 1이 아니면, 운이 좋게 소인수 p를 발견한 것이다. 따라서 p=gcd, q=N//gcd를 반환하고 종료한다.
3. 함수 f(x)=a^x (mod N)의 주기 r을 찾는다. 여기서 찾은 주기 r이 짝수가 아니라면, 1번 단계부터 다시 시작한다.
4. 주기 r로부터 두 개의 최대공약수 gcd1=gcd(N, a^(r//2)) + 1), gcd2=gcd(N, a^(r//2)) - 1)를 찾는다.
5. 여기서 찾은 두 개의 수 gcd1, gcd2 중 하나라도 1이거나 N이라면 1번 단계부터 다시 시작한다. 아니라면, 마침내 소인수들을 찾았으므로 gcd1, gcd2를 반환하고 종료한다.
3. 쇼어 방법의 양자회로 구현
이 사진은 쇼어 알고리즘 양자 회로 구현도이다.
위 사진에서 봤겠지만 쇼어 알고리즘의 주기 찾기 부분에서 양자 회로 부분을 구현하기 위해서는 양자 푸리에변환(QFT: Quantum Fourier Transform)[4]과 역양자푸리에변환(I-QFT: Inverse-QFT) 회로를 구현해야 한다.
3.1. 양자 회로 구현 방법
먼저, 주기성을 가지는 이산 지수 함수의 형태인 이산 로그 문제 [math(f(x) = a^x \operatorname{mod}N )][5]을 살펴보자. 이 함수에서 [math(\frac{Q}{r} \ge N)]일때 [math(2N^2 \le Q \le 4N^2 )]를 만족하는 q의 비트값을 찾아야한다. 여기서 입력과 출력 큐비트 레지스터는 [math(Q-1)]과 0사이의 중첩값을 구축해야하기 때문이다. 여기서 x는 주기(r)이다.양자 중첩을 구축하기 위해 레지스터를 다음과 같이 초기화 시켜야 한다. 레지스터는 이산 푸리에 변환(DFT) 형식의 식이다.
|
[math(\displaystyle \begin{aligned} \dfrac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x\rangle=\left(\displaystyle\dfrac{1}{\sqrt{2}}\sum_{x_\text{1}=0}^{1}|x_\text{1}\rangle\right) \otimes …. \otimes \left(\displaystyle\dfrac{1}{\sqrt{2}}\sum_{x_\text{q}=0}^{1}|x_\text{q}\rangle\right) \end{aligned})]
|
이제 위의 이산 지수 함수 [math(f(x))]를 양자 함수로 가정하고 양자 상태 함수로 다음과 같이 표현해보자.
[math(U_\text{f}|x,0^q\rangle=|x,f(x)\rangle)]
위의 단계를 양자함수에 넣어보자, 큐비트가 중첩 상태로 초기화함으로써 다음과 같은 식을 얻을수 있다.
[math(\displaystyle\dfrac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x,0^q\rangle=\dfrac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x,f(x)\rangle)]
이 식을 보면 알겠지만 Q의 상태는 아직 중첩이다. 하지만 이 식은 [math(q+n)]개의 큐비트들이 서로 얽혀 별개의 큐비트 상태 텐서곱으로 쓰일수없다. 따라서, 주기를 비롯한 여러 값의 큐비트를 한꺼번에 이용해야하므로, 입력 값을 제어하는 융합 게이트가 제어 큐비트를 변환해, 입력 큐비트인 x의 위상에 제어 큐비트가 저장된다.
이제 [math(Q=2^q)]라는 상태의 중첩을 제어해야한다. 양자 중첩을 제어하려면 확률적인 [math(|y\rangle)]상태에서 [math(|x\rangle)]의 진폭을 분리해야하는데, 주기성을 가진 임의의 양에서 진폭을 가진 주기 함수로 변환시키는 푸리에 변환을 입력 레지스터에 대입하면 된다. 단 중첩을 제어하는 상태의 범위가 이산적이므로, 연속적 푸리에 변환대신 DFT를 입력 레지스터에 적용하는 방식으로 원소가 각각 다른 x에 대한 다른 연산 방법을 산출하게 한다.
[math(\displaystyle U_\text{IQFT}(|x\rangle)=\dfrac{1}{\sqrt{Q}}\sum_{y=0}^{Q-1}ω^{xy}|y\rangle)]
이 식은 종결 상태로 유도한다. 중첩을 유도하기 위해 식을 다음으로 확장한다.
[math(\displaystyle\dfrac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1}ω^{xy}|y,f(x)\rangle)]
[math(\displaystyle\dfrac{1}{Q}\sum_{z=0}^{N-1}\sum_{y=0}^{Q-1}\left(\displaystyle\sum_{x\in\mathbb {0,..,Q-1};f(x)=z}ω^{xy}\right)|y,z\rangle)]
이제 각 변수를 다음과 같이 가정해보자
- Q번째 드무아브르 수를 [math(ω=e^{\frac{2\pi i}{Q}})].
- [math(f)]의 주기를 [math(r)].
- [math(x_\text{0})]는 양자함수 [math(z)]에 적용되는 [math(x\in\mathbb {0,..,Q-1})]에서 가장 작은 상태.
- m-1은 [math(\left\lfloor \dfrac{Q-x_\text{0}-1}{r}\right\rfloor)]
- 0부터 m-1까지 x의 인덱스를 b.
이 가정을 적용하면 복소 평면에서 [math(ω^{ry})]는 단위 벡터이므로 종결 상태에서[math(\frac{1}{Q}|y,z\rangle)]의 계수는 다음과 같이 나타내진다.
|
[math(\displaystyle \begin{aligned} \sum_{y=0}^{Q-1}\left(\displaystyle\sum_{x\in\mathbb {0,..,Q-1};f(x)=z}\right)ω^{xy}=\sum_{b=0}^{m-1}ω^{(x_\text{0}+rb)y}=ω^{x_\text{0}y}\sum_{b=0}^{m-1}ω^{rby} \end{aligned})]
|
그러므로, 복소평면에서 같은 방향에 가까운 단위 벡터 [math(ω^{rby})] 지점[6]에서 양자 간섭이 발생한다. 입력 레지스터에서 y에 대한 결과들과 출력 레지스터에서 z에 대한 결과를 얻기 위해 [math(|y,z\rangle)]의 확률을 상기하면,
|
[math(\begin{aligned} P(|y,z\rangle)=\displaystyle|\dfrac{1}{Q}\sum_{x\in\mathbb {0,..,Q-1};f(x)=z}ω^{xy}|^2 \end{aligned})]
|
조건에 따라, 확률로 표현된 [math(|y,z\rangle)]의 계수를 정리하면
|
[math(\displaystyle \begin{aligned} \dfrac{1}{Q^2}|\sum_{b=0}^{m-1}ω^{x_\text{0}y+rby}|^2 = \dfrac{1}{Q^2}|ω^{x_\text{0}y}|^2|\sum_{b=0}^{m-1}ω^{rby}|^2
=\dfrac{1}{Q^2}|\sum_{b=0}^{m-1}ω^{rby}|^2 \end{aligned})] |
[math(\displaystyle \dfrac{1}{Q^2}|\dfrac{ω^{mry}-1}{ω^{ry} - 1}|^2=\dfrac{1}{Q^2}\dfrac{\operatorname{sin}^2(\frac{\pi mry}{Q})}{\operatorname{sin}^2(\frac{\pi ry}{Q})})]
이제 분석을 하면 이 확률이 높아지고 단위 벡터가 양수 실수축에 더 가까워지거나 혹은 [math(\frac{yr}{Q})]가 정수에 가까워짐을 보여준다. r^2가 아닌이상 이 확률은 Q의 원소가 되지 않는다.
[math(\frac{yr}{Q})]이 어떤 정수 c에 가까워질수록, [math(\frac{y}{Q})]도 알려지지 않은 [math(\frac{c}{r})]에 가까워진다. 그러므로 [math(\frac{y}{Q})]에 고전적인 CFE을 사용해서 두가지 조건을 만족하는 [math(\frac{d}{s})]의 예상값을 찾아야 한다. 이 조건들이 주어졌을때 s는 적합한 주기 r이 될 가능성이 높거나 최소한 Q의 원소가 될수 있다.
이제 고전적 구현을 이용하여 [math(f(x)=f(x+s) ⇔ a^s = 1\,mod\,N)]을 확인한다. 위의 과정이 맞으면 종료한다.
그렇지 않으면 s와의 곱을 이용하여 r의 예상값을 찾거나[math(\frac{d}{s})]로 [math(\frac{y}{Q})]의 주변에 있는 다른 s값을 찾아본다. 다음 방법도 맞지 않을 경우 입력 레지스터를 초기화했는지부터 다시 한번 확인해본다.
여기에 대한 또다른 설명은 이 문서를 참고할 수 있다. [7]
4. 인터프리팅
아래의 코드는 단순 계산 방법을 나타낸 것으로, 아래의 코드를 양자컴퓨터로 구현하려면 Qiskit[8]을 이용해 양자 회로의 작동에 관한 코드를 새로 짜야한다. 양자 알고리즘 구현의 간략한 방법은 레지스터 초기화(양자 중첩 발생) > 양자 푸리에 변환[9](양자 중첩 제어) > 확률 분석(제어된 값들의 분석) 순이다.4.1. python
쇼어 알고리즘의 계산 방법을 파이썬으로 구현하면 다음과 같다.#!syntax python
import random
import math
def mod_pow(a, x, N):
y = 1
while (x > 0):
if ((x & 1) == 1):
y = (y * a) % N
x = x >> 1
a = (a * a) % N
return y
def findPeriodByModPow(N, a):
for x in range(1, N):
if (mod_pow(a, x, N) == 1):
return x
return -1
def factorizeByShor(N):
while(True):
a = random.randint(2, N - 1)
gcd = math.gcd(N, a)
if (gcd != 1):
return gcd, N // gcd
r = findPeriodByModPow(N, a)
if (r % 2 != 0):
continue
gcd1 = math.gcd(N, a**(r//2) + 1)
gcd2 = math.gcd(N, a**(r//2) - 1)
if (gcd1 == 1 or N or gcd2 == 1 or N):
continue
return gcd1, gcd2
쇼어 알고리즘의 계산 방법에 대한 상세한 설명과 구현에 대한 해설은 이 영상과 이 영상을 참고할 수 있다. [10] [11]
[1]
P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124-134.
[2]
GEECM이 종종 더 빠르다는 주장이 있다.
[arbitrary]
[4]
DFT이다.
[5]
참고로
RSA 암호화는 위 식을 기반으로 정보를 암호화한다.
[6]
[math(ω^{ry})] 지점이 양수 실수축을 범위로 정하는
[7]
Shor's Algorithm in Qiskit Textbook
[8]
IBM에서 고안한 python기반의 양자컴퓨팅 언어 체계이다.
[9]
DFT 기반의 연산 범위가 Q인 선형 변환.
[10]
소인수 분해를 위한 쇼어의 양자 알고리즘
[11]
쇼어의 소인수 분해 알고리즘 구현