26. الگوریتم شور (Shor)

26.1تجزیهٔ اعداد صحیح

با عدد مرکب فرد N، عامل نابدیهی پیدا کنید (بعد بازگشتی ادامه دهید). مسئلهٔ پشت RSA است: ضرب دو عدد اول بزرگ آنی است و تجزیهٔ حاصل، تا جایی که می‌دانیم، سخت؛ و هر تبادل کلید اینترنتی چهار دههٔ گذشته روی این عدم‌تقارن شرط بسته است. الگوریتم شور (Shor) در ۱۹۹۴ عدد N را در زمان چندجمله‌ای تجزیه می‌کند — از مرتبهٔ O(n³) گیت برای n بیت روی رایانهٔ کوانتومی — و همچنان تعیین‌کننده‌ترین نتیجهٔ حوزه است: محاسبات کوانتومی را از کنجکاوی به ضرب‌الاجل رمزنگارانه تبدیل کرد. توجه کنید که شور چه نمی‌کند: دنبال عامل نمی‌گردد؛ دوره پیدا می‌کند و عامل‌ها می‌افتند بیرون.

26.2سختی کلاسیک

بهترین الگوریتم کلاسیک، غربال میدان اعداد عمومی، در exp(((64/9)^{1/3} + o(1))·(ln N)^{1/3}·(ln ln N)^{2/3}) اجرا می‌شود — زیرنمایی، فراتر از چندجمله‌ای. RSA-2048 با فاصله‌ای عظیم فراتر از آن است (رکورد: RSA-250 در ۲۰۲۰ با ~۲۷۰۰ سال-هسته). الگوریتم تجزیهٔ چندجمله‌ایِ کلاسیک با وجود قرن‌ها کار شناخته نشده و برای همین مسئله فرض سختیِ قابل‌اعتمادی است — و الگوریتم کوانتومیِ چندجمله‌ایِ شور یک رویداد واقعی نظریهٔ پیچیدگی است، نه شتابی افزایشی. میان‌بُر نظریهٔ اعداد از طریق دوره‌ها است که کار می‌کند: تجزیه و یافتن دوره، معلوم می‌شود، یک مسئله‌اند با لباس‌های متفاوت.

26.3حساب پیمانه‌ای

یک a تصادفی با gcd(a, N) = 1 بردارید (اگر gcd بزرگ‌تر باشد، از قبل عامل پیدا کرده‌اید — شانس آوردید). در گروه ضربی Z*_N از باقیمانده‌های هم‌اول با N کار کنید که اندازه‌اش φ(N) است (تابع اویلر). بنا به قضیهٔ لاگرانژ، هر عنصر مرتبه متناهی دارد: کوچک‌ترین r با a^r ≡ 1 (mod N)، و r مقسوم‌علیهٔ φ(N) است. پس توان‌های a^0, a^1, a^2, … با دورهٔ r سیکل می‌زنند. برای N = pq با دو عدد اول فرد متمایز، a تصادفی با احتمال ≥ 1/2 مرتبه‌ای زوج دارد که a^{r/2} ≢ −1 (mod N) — شرطی که گام نهایی gcd را برای شکستن N به کار می‌اندازد.

26.4یافتن دوره

کاهش: اگر بتوانید مرتبهٔ r یک a تصادفی به پیمانهٔ N را پیدا کنید، می‌توانید تجزیه کنید. وقتی r زوج است و a^{r/2} ≢ −1 (mod N)، بنویسید x = a^{r/2}؛ آنگاه x² ≡ 1 (mod N) ولی x ≢ ±1، پس N شمارندهٔ x²−1 = (x−1)(x+1) است بدون اینکه شمارندهٔ هر عامل باشد — و gcd(x−1, N) و gcd(x+1, N) عوامل نابدیهی‌اند. کلاسیکاً، یافتن r یعنی محاسبهٔ توان‌ها تا برخورد با ۱: O(r) ≤ O(N) ضرب، یا O(√r) با گام‌کوچک-گام‌بزرگ. برای N در مقیاس RSA، r نجومی بزرگ است — یافتن دوره همان دیوار نمایی است و دقیقاً همان دیواری که QFT منفجر می‌کند.

26.5یافتن دورهٔ کوانتومی

هستهٔ کوانتومی. Q = 2^t را با N² ≤ Q < 2N² انتخاب کنید (t ≈ 2n+1). (1/√Q)·Σ_{x=0}^{Q−1}|x⟩|1⟩ را آماده کنید و یکانیِ توان‌رسانی پیمانه‌ای |x⟩|y⟩ ↦ |x⟩|y·a^x mod N⟩ را اعمال کنید — ساخته‌شده از مربع‌کردن مکرر روی ارقام دودویی x، هیولای O(n³) گیت:

reg 1 (t ≈ 2n qubits):  |0> ──H^⊗t────────[QFT over Q]──measure y
                                  │
reg 2 (n qubits):       |1> ──────U_pow──          U_pow: |y> ↦ |y·a^x mod N>

حالا ثبات ۲ a^x mod N را نگه می‌دارد — دوره‌ای با دورهٔ r — درهم‌تنیده با ثبات ۱. درهم‌تنیدگی نکته است: ثبات ۱ برهم‌نهی همدوس همهٔ xهاست، برچسب‌خورده با ساختار دوره‌ای تصاویرشان.

26.6پیوند با QFT

QFT روی Q را به ثبات ۱ اعمال کنید. قطار دوره‌ایِ درون حالت درهم‌تنیده پراش می‌کند: دامنه روی اعداد صحیح y با |y/Q − k/r| ≤ 1/(2Q) برای k متناسبی متمرکز می‌شود — مضارب Q/r، تا گردکردن. اندازه بگیرید: y/Q کسری است در فاصلهٔ 1/(2Q) از k/r. حالا گام کلاسیک — بسط کسر مسلسل (continued fraction) y/Q با مخرج‌های محدود به N، هر وقت gcd(k, r) = 1 باشد k/r را بازیابی می‌کند؛ و این برای کسری ثابت از shotها رخ می‌دهد (قله‌ها در مجموع احتمال ≥ 4/π²·φ(r)/r حمل می‌کنند). a^r ≡ 1 (mod N) را راستی‌آزمایی کنید؛ اگر راستی‌آزمایی شکست خورد (r/gcd(k,r) را گرفته‌اید یا r فرد بود)، دوباره نمونه‌برداری کنید — تعداد ثابتی دور به‌طور مورد انتظار. این اسکلت سایمون است با (Z, +) به‌جای (Z₂)ⁿ.

26.7الگوریتم کامل

همه‌چیز سرهم — بخش کوانتومی یک خط جعبه‌شده است:

import math, random

def shor(N):                                   # رانندهٔ کلاسیک
    if N % 2 == 0:
        return 2
    while True:
        a = random.randrange(2, N - 1)
        g = math.gcd(a, N)
        if g > 1:
            return g                           # شانس آوردید: عامل مجانی
        r = quantum_order(a, N)                # یافتن دوره با QFT (26.5-26.6)
        if r % 2 != 0:
            continue                           # مرتبهٔ فرد: با a تازه تکرار کنید
        x = pow(a, r // 2, N)
        if x == N - 1:
            continue                           # a^(r/2) = -1: تکرار کنید
        f1, f2 = math.gcd(x - 1, N), math.gcd(x + 1, N)
        if 1 < f1 < N:
            return f1                          # بازگشتی روی f1 و N // f1

quantum_order(a, N) مدار ۲۶.۵–۲۶.۶ را تعداد ثابتی بار اجرا می‌کند. هزینهٔ کل: O(n³) گیت به‌طور ساده (O(n²·polylog n) با حساب سریع)، تعداد ثابتی تکرار مورد انتظار — هر تکرار با احتمال ≥ 1/2 عدد N را تجزیه می‌کند.

26.8پیاده‌سازی اسباب‌بازی

N = 15 و a = 7 — مثال استاندارد سرتاسری. توان‌ها با دورهٔ ۴ سیکل می‌زنند؛ نسخهٔ اسباب‌بازی از Q = 16 استفاده می‌کند (کوچک‌تر از Q ≥ N² لازم، اما این‌جا دقیق چون r = 4 مقسوم‌علیهٔ ۱۶ است):

x          : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
7^x mod 15 : 1  7  4 13  1  7  4 13  1  7  4 13  1  7  4 13
                                             └── period r = 4 ──┘

QFT over Q = 16 → peaks at y ∈ {0, 4, 8, 12}   (each with probability 1/4)
y/Q = 4/16, 8/16, 12/16 = 1/4, 1/2, 3/4  →  continued fractions → r = 4
7^(r/2) = 7^2 = 49 ≡ 4 (mod 15), 4 ≢ −1 ≡ 14  →  condition satisfied
gcd(4 − 1, 15) = 3   and   gcd(4 + 1, 15) = 5   →   15 = 3 × 5

و شبیه‌سازی کامل — اورکل، QFT، اندازه‌گیری، کسر مسلسل، gcd:

import numpy as np
from fractions import Fraction
rng = np.random.default_rng(3)
N, a, Q = 15, 7, 16
f = np.array([pow(a, x, N) for x in range(Q)])        # 7^x mod 15
psi = np.zeros(Q * N, dtype=complex)
for x in range(Q):
    psi[x * N + f[x]] = 1                             # |x>|a^x mod N>
H = np.exp(2j * np.pi * np.outer(np.arange(Q), np.arange(Q)) / Q) / np.sqrt(Q)
psi = np.kron(H, np.eye(N)) @ psi                     # QFT روی Q برای ثبات ۱
p = (np.abs(psi.reshape(Q, N)) ** 2).sum(axis=1)
y = rng.choice(Q, p=p)                                # اندازه‌گیری ثبات ۱
r = Fraction(y, Q).limit_denominator(N).denominator   # کسر مسلسل
print("y =", y, " r candidate =", r)
if r % 2 == 0 and pow(a, r, N) == 1:
    print("factors:", np.gcd(pow(a, r // 2, N) - 1, N), np.gcd(pow(a, r // 2, N) + 1, N))
else:
    print("unusable shot (y=0 or k shares a factor with r) — rerun")

شاخهٔ else تزئین نیست: y = 0 (با احتمال ¼) و y = 8 (که 1/2 می‌دهد؛ یعنی r/gcd(k,r) = 2) هر دو به همان‌جا می‌افتند — دقیقاً همان‌طور که ۲۶.۶ وعده داده بود.

from fractions import Fraction
for y in (4, 8, 12):                     # قله‌های اندازه‌گیری‌شده، Q = 16، r واقعی = 4
    fr = Fraction(y, 16).limit_denominator(15)
    print(f"{y}/16 -> {fr}   r-candidate = {fr.denominator}")

26.9منابع لازم

مدار منطقی: t ≈ 2n+1 کیوبیت شمارش، ثبات‌های حساب n-بیتی، QFT با O(n²) گیت، و توان‌رسانی پیمانه‌ای غالب با O(n³) گیت ساده — O(n²·polylog n) با مدارهای ضرب پیشرفته. تخمین‌های سرتاسری برای RSA-2048: گیدنی–اکرا (Gidney–Ekerå، ۲۰۱۹) — حدود ۲۰ میلیون کیوبیت فیزیکی نویزی در ۸ ساعت؛ گیدنی (۲۰۲۵) — کمتر از ۱ میلیون کیوبیت نویزی در کمتر از یک هفته، به لطف حساب بهتر و چیدمان‌های تصحیح خطا. هر دو تحمل خطای surface code با نرخ خطای فیزیکی نزدیک 10⁻³ را فرض می‌کنند. در برابر ماشین‌های امروز — صدها تا چند هزار کیوبیت فیزیکی — شکاف حدود سه مرتبه بزرگی در شمار کیوبیت است. این افق برنامه‌ریزی صادقانه است: دست‌یافتنی اما نه قریب‌الوقوع؛ این مهندسی است، نه خیال.

26.10پیامدها برای رمزنگاری

شور، RSA و Diffie–Hellman میدان متناهی و رمزنگاری منحنی بیضوی را می‌شکند، به شرط موجودبودن ماشین‌های تحمل‌پذیر خطا در مقیاس ۲۶.۹. Primitiveهای متقارن جان می‌دهند: گروور فقط ضریب ۲ در طول کلید مؤثر هزینه دارد، پس AES-256 سالم می‌ماند. تهدید عملیاتی، اکنون برداشت کن، بعداً رمزگشایی کن (harvest now, decrypt later) است — حریفانی که امروز ترافیک رمزشده را ضبط می‌کنند تا پس از موجودشدن رایانهٔ کوانتومی رمزشکن، رمزگشایی کنند — و همین مهاجرت را برای رازهای طولانی‌عمر فوری می‌کند. NIST در ۲۰۲۴ جایگزین‌ها را استاندارد کرد: ML-KEM (FIPS 203، شبکه‌ها)، ML-DSA (FIPS 204)، SLH-DSA (FIPS 205، مبتنی بر هش). مهاجرت برنامه‌ای ده‌ساله است که هر پروتکلی را که روزی منتشر کرده‌اید لمس می‌کند — و نزدیک‌تر به خانه، نقطهٔ تلاقی مشاغل تحلیل رمز و محاسبات کوانتومی است (۵۱.۹). الگوریتم ۳۰ سال دارد؛ پیامدهایش هنوز در حال ساخته‌شدن‌اند.