Shor'un algoritması

Shor Algoritması

Shor algoritması, Amerikalı matematikçi Peter W. Shor tarafından geliştirilen bir kuantum algoritmasıdır. 1994 yılında ortaya çıkan bu algoritma, güçlü potansiyel uygulamaları ve en iyi bilinen klasik (non-kuantum) algoritmalarla karşılaştırıldığında hızlandırma konusunda güçlü kanıtlar içeren az sayıdaki bilinen Kuantum Algoritmalarından biridir.

Arka Plan

Tam sayı çarpanlama problemi, bir bileşik sayıyı asal çarpanlarına ayırmayı içerir. Klasik bilgisayarlar büyük sayılarda zorluk yaşar, çünkü en iyi bilinen klasik algoritma olan genel sayı alanı eleme, süb-ünlem süresinde çalışır. Ancak Shor algoritması, tam sayıları etkili bir şekilde çarpanlarına ayırmanın bir kuantum bilgisayarında verimli bir şekilde çözülebileceğini gösterir ve bu nedenle karmaşıklık sınıfı BQP’de yer alır (sınırlı hata kuantum polinom zamanı).

Shor Algoritması Nasıl Çalışır

1. Kuantum Fourier Dönüşümü:
   • Shor algoritması, bir modüler fonksiyonun periyodunu bulmak için kuantum Fourier dönüşümünü kullanır.
   • Periyot bulma adımı büyük sayıları çarpanlarına ayırma için önemlidir.
2. Kuantum Periyot Bulma:
   • Shor algoritması, kuantum paralelliği kullanarak bir modüler fonksiyonun periyodunu verimli bir şekilde bulur.
   • Periyot, tam sayının çarpanları hakkında bilgi verir.
3. Kuantum Hızlandırma:
   • Bir kuantum bilgisayarında Shor algoritması polinom zamanında çalışır.
   • Özellikle hızlı çarpma kullanılarak sırasıyla O((log N)^2 (log log N) (log log log N)) büyüklüğünde kuantum kapıları gerektirir.
   • Bu, en iyi bilinen klasik çarpanlama algoritması olan genel sayı alanı eleminin süb-ünlem süresinde çalışanından önemli ölçüde daha hızlıdır: .

Uygulanabilirlik ve Etki

• Shor algoritması, genel anahtarlı şifreleme gibi kriptografi uygulamaları için etkiler:
  • RSA şifrelemesi, büyük sayıları çarpanlarına ayırmanın zor olduğu varsayımına dayanır.
  • Bilinen kadarıyla, bu varsayım klasik (non-kuantum) bilgisayarlar için geçerlidir; polinom zamanında tam sayıları çarpanlayabilen bilinen bir klasik algoritma yoktur.
  • Ancak Shor algoritması, tam sayıları ideal bir kuantum bilgisayarında etkili bir şekilde çarpanlarına ayırmanın mümkün olduğunu gösterir, bu nedenle büyük bir kuantum bilgisayarı inşa ederek RSA’yı kırmak mümkün olabilir.
  • Ayrıca, yeni kuantum bilgisayar algoritmalarının çalışması ve tasarlanması için güçlü bir motivasyon kaynağı olmuştur.
  • Ayrıca, kuantum bilgisayarlar tarafından çözülemeyen güvenli ’ler üzerine araştırmaları kolaylaştırmıştır, bu da toplu olarak post-kuantum kriptografisi olarak adlandırılır.

Kaynakça

Washington University - 336_16/2016

NC State University - CSC591/ECE592 – 2019

Cambridge University - Shor's factorization algorithm