Periyot bulma: Shor algoritmasının kalbi

Bir sayıyı çarpanlarına ayırmak neden bir dizinin kendini tekrar etme süresini bulmaya indirgenir? Shor algoritmasının klasik iskeletini 15 sayısıyla adım adım gör.

Çarpanlara ayırma ve şifreleme

15 = 3 × 5 gibi küçük sayıları kafadan ayırırız. Ama yüzlerce basamaklı bir sayıyı iki asal çarpanına ayırmak bugünkü en güçlü bilgisayarlar için bile pratikte imkânsızdır. İnternette yaygın kullanılan RSA şifrelemesinin güvenliği tam olarak bu zorluğa dayanır.

Peter Shor 1994’te bir kuantum bilgisayarın bu işi çok daha hızlı yapabileceğini gösterdi: klasik yöntemlerin süresi sayının basamak sayısıyla neredeyse üstel büyürken Shor algoritmasınınki yalnızca polinom büyür. İşin sırrı, çarpanlara ayırmayı bir periyot bulma problemine çevirmektir.

Kendini tekrar eden dizi

N = 15 ve rastgele bir a = 7 seçelim. 7’nin kuvvetlerini 15’e bölüp kalanlarına bakalım: 1, 7, 4, 13, 1, 7, 4, 13… Dizi her 4 adımda bir kendini tekrar ediyor. Bu 4 sayısına periyot denir ve r ile gösterilir.

Periyot bulununca çarpanlar basit bir hesapla çıkar: a^(r/2) − 1 ve a^(r/2) + 1 sayılarının N ile en büyük ortak böleni (EBOB) alınır. Örneğimizde 7² = 49; EBOB(48, 15) = 3 ve EBOB(50, 15) = 5. İşte 15 = 3 × 5.

from math import gcd

N, a = 15, 7
print([pow(a, x, N) for x in range(8)])   # [1, 7, 4, 13, 1, 7, 4, 13]

r = next(x for x in range(1, N) if pow(a, x, N) == 1)
print(r)                                   # 4
print(gcd(a**(r // 2) - 1, N), gcd(a**(r // 2) + 1, N))   # 3 5

Zor kısım periyodu bulmak

Yukarıdaki kod periyodu kuvvetleri tek tek deneyerek buldu. Küçük sayılar için bu kolay, ama büyük N için periyot astronomik büyüklükte olabilir ve tek tek denemek evrenin ömrünü aşar. Shor algoritmasında yalnızca bu adım kuantumdur; EBOB hesabı gibi geri kalan her şey sıradan bir bilgisayarda yapılır.

Bazen şanssız bir a seçilir: periyot tek sayı çıkar ya da a^(r/2), N’e bölününce −1 kalanını verir. Örneğin a = 14 için r = 2’dir ama 14 ≡ −1 (mod 15) olduğu için çarpan çıkmaz. O zaman başka bir a denenir; rastgele seçilen a’ların çoğu işe yarar.

Periyot ve Fourier dönüşümü

Periyot bulmak, orta seviye kursta gördüğün kuantum Fourier dönüşümünün tam olarak yaptığı iştir. Periyodik bir durumu Fourier dönüşümünden geçirince ölçüm sonuçları periyodu ele veren tepelerde toplanır. Bir sonraki derste bu iki parçayı birleştirip Shor algoritmasının bütününü göreceğiz.

Kendin dene

İlk H kapısı periyodu 2 olan bir durum hazırlar. Fourier dönüşümünden sonra yalnızca 00 ve 10 çıkar: tepeler periyodu ele verir. İlk H’yi kaldır: periyodik desen kaybolur ve dört sonucun her biri %25 olur.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

RSA şifrelemesinin güvenliği büyük sayıları çarpanlarına ayırmanın zorluğuna dayanır.
Shor algoritması çarpanlara ayırmayı aˣ mod N dizisinin periyodunu bulmaya indirger.
Periyot r bulununca çarpanlar EBOB(a^(r/2) ± 1, N) ile çıkar: 15 için 3 ve 5.
Yalnızca periyot bulma adımı kuantumdur; geri kalanı klasik hesaptır.

Kendini sına

N = 15 ve a = 7 için 7ˣ mod 15 dizisinin periyodu kaçtır?

Cevabı göster

4. Kalanlar 1, 7, 4, 13 ve yeniden 1 olur; dizi her 4 adımda bir tekrar eder.

Shor algoritması: faz tahminiyle çarpanlara ayırma →