Shor 알고리즘 — 소인수분해의 양자 우위

개념 소개

큰 합성수 $N$을 두 소수의 곱으로 분해하는 것은 고전적으로 매우 어렵다. 현재 가장 효율적인 고전 알고리즘인 일반 수체 체(General Number Field Sieve, GNFS)는 $\exp!\bigl(O((\log N)^{1/3}(\log\log N)^{2/3})\bigr)$의 준지수 시간을 요구한다. RSA 암호는 바로 이 어려움에 안전성의 근거를 둔다.

1994년 Peter Shor가 제안한 양자 알고리즘은 이 문제를 $O((\log N)^3)$ 게이트 복잡도로, 즉 다항 시간에 해결한다. 이는 단순한 상수 배 개선이 아니라 복잡도 클래스 자체를 뛰어넘는 지수적 가속이다.

---

핵심 원리

1. 소인수분해 → 주기 탐색 환원

소인수분해를 직접 공격하는 대신, 다음 동치를 이용한다.

$N$의 소인수를 구하려면, 임의의 $a$ ($\gcd(a,N)=1$)에 대해 함수 $f(x) = a^x \bmod N$의 주기 $r$을 찾으면 된다.

주기 $r$이 짝수이고 $a^{r/2} \not\equiv -1 \pmod{N}$이면,

$$\gcd(a^{r/2} \pm 1,; N)$$

이 $N$의 비자명 인수를 확률적으로 제공한다. 이 환원 자체는 순수 정수론이며 고전적으로 처리된다.

2. 양자 주기 탐색

주기 $r$의 탐색이 고전적으로 지수 시간을 요하는 반면, 양자 컴퓨터는 이를 다항 시간에 수행한다.

알고리즘 회로 구조:

1. 초기화: 두 레지스터 $|0\rangle^{\otimes n}|0\rangle^{\otimes m}$ 준비
2. 중첩 생성: 첫 번째 레지스터에 하다마르 변환 적용 $$H^{\otimes n}|0\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle$$
3. 모듈러 지수화: 제어 유니터리 $U_f$ 적용 $$\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|0\rangle ;\longrightarrow; \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|a^x \bmod N\rangle$$
4. 두 번째 레지스터 측정: 특정 값 $f_0 = a^{x_0} \bmod N$으로 붕괴 → 첫 레지스터는 ${x_0, x_0+r, x_0+2r, \ldots}$의 중첩 상태
5. 양자 푸리에 변환(QFT): 주기 정보를 주파수 도메인으로 변환 $$\text{QFT}N|j\rangle = \frac{1}{\sqrt{N}}\sum{k=0}^{N-1} e^{2\pi i jk/N}|k\rangle$$
6. 측정: 측정값은 $2^n/r$의 정수 배에 집중 → 연분수 전개로 $r$ 추출

3. 양자 푸리에 변환의 효율성

고전 FFT가 $O(N \log N)$인 반면, QFT는 $O((\log N)^2)$ 게이트로 구현된다. 이것이 전체 알고리즘의 다항 복잡도를 가능하게 하는 핵심이다.

$$\text{QFT}|j\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{l=1}^{n} \left(|0\rangle + e^{2\pi i j/2^l}|1\rangle\right)$$

이 곱 형태의 분해 덕분에 $n$비트 QFT를 $n(n+1)/2$개의 회전 게이트로 구현할 수 있다.

---

예시·응용

소규모 예시: $N = 15$ 분해

# Qiskit을 이용한 개념적 구현 (시뮬레이터 기준)
from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
import numpy as np

# N=15, a=7 선택 (gcd(7,15)=1)
# f(x) = 7^x mod 15 의 주기는 r=4
# 7^(4/2) - 1 = 48 = 3*16 → gcd(48, 15) = 3
# 7^(4/2) + 1 = 50 = 2*25 → gcd(50, 15) = 5
# 결과: 15 = 3 × 5

N = 15
a = 7
r = 4  # 양자 주기 탐색으로 얻은 값

factor1 = np.gcd(a**(r//2) - 1, N)
factor2 = np.gcd(a**(r//2) + 1, N)
print(f"{N} = {factor1} × {factor2}")  # 15 = 3 × 5

RSA에 대한 함의

RSA-2048은 2048비트 합성수의 소인수분해에 안전성을 둔다. GNFS로는 현재 슈퍼컴퓨터로도 우주 나이를 초과하는 시간이 필요하다. 반면 충분한 물리 큐비트를 갖춘 내결함성 양자 컴퓨터는 이를 시간 내에 해결할 수 있다. 이에 대응하여 NIST는 격자 기반 암호(CRYSTALS-Kyber 등) 표준화를 완료하였다.

현실적 구현 요건

• $N$이 $n$비트 수이면 약 $2n$ 큐비트의 논리 큐비트가 필요
• 모듈러 지수화 회로의 게이트 수: $O(n^3)$
• 실제로는 오류 정정을 포함한 수천~수만 개의 물리 큐비트 요구
• 현재 공개된 하드웨어로는 수십 비트 규모의 $N$만 시연 가능

---

정리

Shor 알고리즘은 소인수분해라는 정수론 문제를 주기 탐색으로 환원하고, 양자 중첩·얽힘·QFT를 결합해 고전적 한계를 지수적으로 돌파한다. 알고리즘의 고전부(환원, 연분수 전개)와 양자부(QFT, 모듈러 지수화)의 분리된 역할을 이해하는 것이 전체 구조를 파악하는 핵심이다. 내결함성 양자 컴퓨터의 실현과 함께 이 알고리즘의 실용적 위협이 현실화될 경우, 현재의 공개키 암호 인프라 전반에 대한 전환이 불가피하다.