Shor Algoritması: RSA'yı Tehdit Eden Periyot Bulma Makinesi

RSA'nın güvenliği tek bir varsayıma dayanır: iki büyük asal sayının çarpımı verildiğinde, o asalları geri bulmak pratikte imkânsızdır. Bilinen en iyi klasik algoritma (genel sayı alanı eleği) alt-üstel zamanda çalışır; 2048-bit bir RSA modülü için bu, evrenin ömrünü aşan süreler demektir. Peter Shor'un 1994'te gösterdiği şey, bu problemin kuantum bilgisayarda polinom zamanda çözülebileceğiydi; bu, kriptografi tarihinin belki de en sarsıcı teorik sonucudur.

Ana fikir: çarpanlara ayırma aslında periyot bulmadır

Shor'un ilk hamlesi tamamen klasik bir indirgemedir. N'yi çarpanlarına ayırmak istiyorsak, N ile aralarında asal rastgele bir a seçer ve f(x) = aˣ mod N fonksiyonunun periyodunu (r) ararız: yani aʳ ≡ 1 (mod N) koşulunu sağlayan en küçük r'yi. r çiftse ve a^(r/2) ≢ -1 (mod N) ise, gcd(a^(r/2) ± 1, N) hesabı yüksek olasılıkla N'nin gerçek bir çarpanını verir. Uygun olmayan a seçimlerinde birkaç kez yeniden denemek yeterlidir.

from math import gcd
from random import randint

def shor_classical_part(N: int, r: int, a: int):
    """Periyot r bulunduktan sonraki tamamen klasik adım."""
    if r % 2 == 1 or pow(a, r // 2, N) == N - 1:
        return None                      # uygunsuz a, yeniden dene
    p = gcd(pow(a, r // 2) - 1, N)
    q = gcd(pow(a, r // 2) + 1, N)
    return (p, q) if p * q == N and p not in (1, N) else None

# Küçük bir örnek: N = 15, a = 7
# f(x) = 7^x mod 15 → 1, 7, 4, 13, 1, 7, ...  periyot r = 4
print(shor_classical_part(15, 4, 7))     # (3, 5) yüksek olasılıkla

Zor kısım periyodu bulmaktır: klasik olarak f'yi tek tek değerlendirip tekrarı yakalamaya çalışmak, üstel sayıda deneme gerektirebilir. Kuantum bilgisayarın devreye girdiği yer tam burasıdır.

Kuantum kısım: süperpozisyonda periyot yakalamak

• ▪İki register hazırlanır; ilki Hadamard kapılarıyla 0'dan 2ᵗ-1'e tüm x değerlerinin eşit süperpozisyonuna sokulur.
• ▪Modüler üs alma devresi, ikinci register'a f(x) = aˣ mod N değerini işler; hem de tek çalıştırmada 'tüm' x'ler için.
• ▪İkinci register ölçüldüğünde ilk register, aynı f değerini üreten x'lerin süperpozisyonuna çöker (x₀, x₀+r, x₀+2r, ...); periyot artık durumun içine kodlanmıştır.
• ▪Kuantum Fourier dönüşümü (QFT) bu periyodik yapıyı frekans uzayına taşır; ölçüm, k·2ᵗ/r civarında bir değer verir.
• ▪Sürekli kesirler açılımı ile ölçümden r geri çıkarılır.

“Shor'un dehası kuantum hızlandırmayı doğru probleme bağlamasında: süperpozisyon tek başına hız kazandırmaz; periyodiklik gibi küresel bir yapıyı girişimle okunabilir hâle getirdiğinizde kazandırır.”

Gerçekte ne kadar yakınız?

2048-bit RSA'yı kırmak için gereken kaynak tahminleri, hata düzeltme yükü dahil milyonlarca fiziksel qubit ve saatler-günler mertebesinde kesintisiz hesap öngörüyor; güncel çalışmalar bu tahminleri düşürmeye devam etse de bugünün yüzlerce-binlerce gürültülü qubit'lik cihazlarından hâlâ nitelik olarak uzaktayız. Bugüne kadar donanımda çarpanlarına ayrılan sayılar (15, 21 gibi) gösterim amaçlıdır. Yani tehdit acil değil ama yapısaldır: algoritma hazır, donanım yolda.

Bu asimetri, post-kuantum kriptografiye geçişin neden bugünden planlanması gerektiğinin de cevabıdır: 'şimdi topla, sonra çöz' saldırısında verinin bugün kaydedilmesi yeterli. Uzun gizlilik ömrü olan her veri, Shor'un gölgesi altındadır.