노트북 14 — Shor가 RSA를 깬다

노트북 14 — Shor가 RSA를 깬다#

이 책이 향해 온 순간입니다. \(N=15, 21, 35\)에서 Shor 알고리즘을 돌려 보고, 성공과 실패, 재시도를 거쳐 마침내 인수분해가 이루어지는 모습을 봅니다.

import numpy as np
from pqc_edu.quantum.shor import factor

빠르게 한 번 성공해 보기: \(N=15\)#

처음 몇 번의 시도가 성공하도록 seed를 골랐습니다.

rng = np.random.default_rng(0)
result = factor(15, rng, max_attempts=10)
print('factors:', result.factors)
print('quantum runs:', result.total_quantum_runs)
print('attempts:')
for i, att in enumerate(result.attempts):
    print(f'  {i+1}. a={att.a}, measured={att.measured}, r={att.inferred_period}, status={att.status}')

factors: (3, 5)
quantum runs: 1
attempts:
  1. a=13, measured=64, r=4, status=success

참고: 시뮬레이션 지름길#

우리는 \(a^x \bmod N\) 단계를 다항식 크기의 가역 산술 회로로 구성하는 대신, 모든 basis state에 대해 한 번에 상태 벡터를 갱신하는 방식으로 구현합니다. 알고리즘적 동작 — 중첩 \(\sum_x |x\rangle|a^x \bmod N\rangle\)을 만드는 것 — 은 동일하며, 다만 우리 시뮬레이터가 수행하는 고전적 작업만이 지수적일 뿐입니다. 이는 시뮬레이션 지름길이지 알고리즘 지름길이 아닙니다 — 실제 양자 컴퓨터는 \(n\)에 대해 다항적으로 스케일링되는 모듈러 지수 gate를 사용합니다.

\(N=21\)과 \(N=35\)#

더 큰 회로이며, counting qubit이 많을수록 주기를 더 정확히 분해할 수 있습니다.

for N in (21, 35):
    rng = np.random.default_rng(1 + N)
    result = factor(N, rng, max_attempts=20)
    print(f'\nN={N}: factors = {result.factors}  (after {result.total_quantum_runs} quantum runs, {len(result.attempts)} total attempts)')
    for i, att in enumerate(result.attempts):
        print(f'  {i+1}. a={att.a}, measured={att.measured}, r={att.inferred_period}, status={att.status}')

N=21: factors = (7, 3)  (after 2 quantum runs, 3 total attempts)
  1. a=16, measured=0, r=None, status=period_not_found
  2. a=8, measured=0, r=None, status=period_not_found
  3. a=7, measured=-1, r=None, status=a_not_coprime

N=35: factors = (7, 5)  (after 0 quantum runs, 1 total attempts)
  1. a=14, measured=-1, r=None, status=a_not_coprime

여러 seed에 걸친 성공률#

Shor는 확률적 알고리즘입니다 — 매 실행마다 무작위로 \(a\)를 고릅니다. 어떤 선택은 실패합니다(홀수 주기, 자명한 제곱근 등). 서로 다른 100개의 seed로 실행해 보고, 한 번의 시도만으로 성공하는 비율이 얼마나 되는지 세어 봅니다.

first_try_success = 0
success_eventually = 0
total = 100
for seed in range(total):
    rng = np.random.default_rng(seed)
    result = factor(15, rng, max_attempts=10)
    if result.factors is not None:
        success_eventually += 1
        if len(result.attempts) == 1:
            first_try_success += 1
print(f'N=15 success rate (first try):   {first_try_success}/{total}')
print(f'N=15 success rate (within 10):  {success_eventually}/{total}')

N=15 success rate (first try):   66/100
N=15 success rate (within 10):  100/100

상태별 분류#

실패할 때는 어떤 일이 일어날까요?

from collections import Counter
all_statuses = Counter()
for seed in range(total):
    rng = np.random.default_rng(seed)
    result = factor(15, rng, max_attempts=10)
    for att in result.attempts:
        all_statuses[att.status] += 1
print('attempt outcomes across 100 seeds of N=15:')
for s, c in sorted(all_statuses.items(), key=lambda kv: -kv[1]):
    print(f'  {s:22s} {c}')

attempt outcomes across 100 seeds of N=15:
  a_not_coprime          67
  period_not_found       37
  success                33
  trivial_factor         13

RSA 스케일링 참고#

ML-KEM-512는 RSA-2048 이상을 대체합니다. RSA-2048을 Shor로 풀려면 약 4096개의 qubit이 필요합니다. 우리 시뮬레이터는 14 qubit 정도(\(N \le 35\))가 한계입니다. “시뮬레이터에서 35를 인수분해한다”와 “\(2^{2048}\)을 인수분해한다” 사이의 간극은 문제 크기로 약 10자릿수에 달합니다. Q-Day가 여전히 논쟁거리인 이유가 여기에 있습니다: 4000 qubit짜리 fault-tolerant 양자 컴퓨터를 만드는 일은 오늘날 만들어진 그 어떤 것보다도 훨씬 어렵습니다.

→ 마지막 장: 15_shor_vs_lattice.ipynb — 왜 이 trick이 ML-KEM은 깨지 못하는가.