Kozan Demircan | Kuantum Bilgisayarlar
**
Shor algoritması nedir ?
Shor algoritması 1994’te Amerikalı matematikçi Peter W. Shor tarafından geliştirilmiş bir algoritmadır. Bu algoritma kuantum bilgisayarlarında çok büyük sayıları kolaylıkla asal çarpanlarına ayırabilmektedir. Shor algoritması bu özelliğiyle kriptoloji tarihinin dönüm noktalarından biri olarak kabul edilmektedir. bir kuantum bilgisayarı,N tam sayısını çarpanlara, Shor’un algoritması ile polinom zamanda ayırır (alınan zaman log N içindeki polinomdur, bu girişin büyüklüğüdür). özel olarak alınan zaman O((log N)3), bu tam sayıyı çarpanlaştırma problemini göstermenin etkin çözümü bir kuantum bilgisayar olabilir ve böylece karmaşıklık sınıfı BQP içindedir.Bu en etkin bilinen klasik çarpanlama algoritmasından daha hızlıdır, elek Genel sayı alanı, bu alt-üstel zamaniçinde çalışır — yukarda O(e1.9 (log N)1/3 (log log N)2/3). Shor’un etkin algoritmasının etkisi kuantum Fourier dönüşümünün ve kareleştirme tarafından modüler üstelidir.
Eğer bir kuantum bilgisayar kubitlerin bir sayısı yeterli ise gürültüye yenik düşmeden işletilebilir ve diğer kuantum girişim fenomeneni, Shor’un algoritması kullanılarak açık-anahtarlı şifreleme şeması kırılabilir örneğin geniş ölçüde RSA şeması kullanıldığı gibi. RSA çok sayıda çarpanlara ayırmanın hesaplama açısından olanaksız olduğu varsayımına dayanmaktadır.
Şu ana kadar bilindiği gibi, Bu varsayım klasik (non-kuantum) bilgisayarlar için geçerlidir; hiçbir klasik algoritma polinom zamanda faktör olduğu bilinmektedir. Ancak, Shor’un algoritma büyük bir kuantum bilgisayarı oluşturarak RSA yenmek mümkün olabilir bu yüzden çarpanlama, ideal bir kuantum bilgisayar üzerinde etkili olduğunu göstermektedir.
Ayrıca kuantum bilgisayarların tasarımı ve inşası için ve yeni kuantum bilgisayar algoritmaları çalışma için güçlü bir motivasyon oldu. Ayrıca post-kuantum kriptografi topluca, kuantum bilgisayarların güvenli yeni kriptosistemlerde araştırmayı kolaylaştırdı.
2001’de, Shor’un algoritması IBM’de bir grup tarafından gösterilmişti, 15’in çarpanları içinde 3 × 5,bir kuantum bilgisayar ile 7 kubit bir uygulama kullanılır. Ancak, bazı şüpheler IBM’in deneyi kuantum hesaplamanın gerçek bir gösteri olup olmadığı gibi gündeme getirilmesinden beri gözlenen hiçbir dolaşıklık yoktur.
IBM’in uygulanmasından bu yana, çeşitli gruplar fotonik qubits kullanarak Shor’un algoritmasını hayata geçirdik, bu dolanma vurgulanması gözlenmiştir. In 2012,15’in çarpanları tekrarlandı. Ayrıca 2012’de, bir kuantum bilgisayar ile büyük sayı çarpanlı için 21’in çarpanları kaydı elde edildi.
Bizim problemin çözümünü deniyoruz:verilen bir tek bileşik sayı {\displaystyle N}N, bir tam sayı {\displaystyle d}{\displaystyle d},buluyoruz kesinlikle {\displaystyle 1}{\displaystyle 1} ve {\displaystyle N}N arasındadır, bu {\displaystyle N}N’e bölünür. Biz {\displaystyle N}N’in tek değerleri ile ilgileniyoruz çünkü {\displaystyle N}N’in herhangi çift değeri önemsiz {\displaystyle 2}{\displaystyle 2} sayısı olarak bir asal çarpan vardır. Biz emin olmak için asallık testi algoritması kullanabiliriz bu {\displaystyle N}N aslında bileşiktir.
Ayrıca,algoritmanın çalışması için, {\displaystyle N}N bir asalın gücü olmaması gerekir. Bu kare alma ile test edilebilir, kübik, …,{\displaystyle k\leq \log _{2}(N)}{\displaystyle k\leq \log _{2}(N)} için {\displaystyle k}{\displaystyle k}-{\displaystyle N}N’in kökü , ve hiçbiri kontrol edilmemiş bir tam sayıdır. (aslında bu {\displaystyle N=M^{k}}{\displaystyle N=M^{k}} hariç {\displaystyle M}{\displaystyle M} tam sayısı için ve {\displaystyle k>1}{\displaystyle k>1}.)
Dolayısıyla {\displaystyle N}N bir asalın bir kuvveti değildir, o iki eşasal’ın çarpımı {\displaystyle 1}{\displaystyle 1}’den büyük sayıdır.Bu bir Çinli kalan teoreminin sonucudur, {\displaystyle 1}{\displaystyle 1} sayısının modül {\displaystyle N}N’de en az dört ayrı kökü var,ikisi {\displaystyle 1}{\displaystyle 1} ve {\displaystyle -1}{\displaystyle -1}.Algoritmanın amacı birin bir {\displaystyle b}b kare kökünü bulmadır , {\displaystyle 1}{\displaystyle 1} sonra diğeri ve {\displaystyle -1}{\displaystyle -1}; böylece bir {\displaystyle b}b {\displaystyle N}N’in çarpanlarına ayırmasına yol açacak,kuadratik elek içinde diğer çarpanlama algoritmaları gibi sırayla, bir {\displaystyle b}b bulunuyor bir öğeyi bulmak için azaltılmıştır.çift periyodun {\displaystyle a}a ile belirli bir ek özellik(Aşağıda açıklandığı gibi, bu klasik parçanın Aşama 6’daki durum tutmaz olması gereklidir). kuantum algoritma rastgele seçilen elementlerin periyodu için {\displaystyle a}a kullanılır, sıralı-bulgu bir klasik bilgisayarın zor bir problemidir.
Shor’un algoritması iki bölümden oluşur:
sıralı bulgunun sorununa çarpım sorununu klasik bir bilgisayarda indirgeme yapılabilir .
sıralı bulma sorununu çözmek için bir kuantum algoritma.
Klasik parçası Düzenle
Rastgele bir sayı a< N seçin.
Compute gcd(a, N).Bu Öklid algoritması kullanılarak yapılabilir .
Eğer gcd(a, N) ≠ 1 ,ise burada Nin bir önemsiz-olmayan çarpanı ise,bu yüzden yapılır .
Yoksa r bulmak için period-bulma yordamı(aşağıda)kullanın,aşağıdaki fonksiyonun periyodu :
{\displaystyle f(x)=a^{x}{\bmod {N}},}{\displaystyle f(x)=a^{x}{\bmod {N}},}
yani {\displaystyle a}a’nın {\displaystyle r}{\displaystyle r} sıralı {\displaystyle (\mathbb {Z} _{N})^{\times }}{\displaystyle (\mathbb {Z} _{N})^{\times }} içinde, bu {\displaystyle f(x+r)=f(x)}{\displaystyle f(x+r)=f(x)} için r küçük pozitif tam sayıdır , veya {\displaystyle f(x+r)=a^{x+r}{\bmod {N}}=a^{x}{\bmod {N}}.}{\displaystyle f(x+r)=a^{x+r}{\bmod {N}}=a^{x}{\bmod {N}}.}
Eğer r tek ise,1 adım geri gidin .
Eğer a r /2 ≡ −1 (mod N) , 1 adım geri gidin .
gcd(ar/2 ± 1, N) bir önemsiz olmayan çarpandır.
Örneğin: {\displaystyle N=15,a=2,r=4}{\displaystyle N=15,a=2,r=4}, gcd(4 ± 1, N).
(Kaynak: Vikipedi)
Konu devam ediyor… Aşağıdaki linkten takip edin.
