Kuantum bilgisayarlar hatırladığım kadarı ile normal çalışma olarak klasik bilgisayarlardan daha yavaşlar. Sadece hesaplama olarak normal bilgisayarları tokatlarlar.
Kuantum bilgisayar bunları yapar;
Rastgele pozitif tam sayılar m<n seçilir ve gcd(m, n) Öklid Algoritması kullanılarak polinomal zamanda hesaplanır. Eğer gcd(m, n) ≠ 1 ise N'in asal çarpanı bulunmuştur ve problem çözülmüştür. Eğer gcd(m, n) = 1 iseikinci adıma geçilir. Kuantum bilgisayar dizinin periyordunu (P) bulmak için kullanılır. Eğer P bir tek tam sayı olarak bulunduysa birinci adım tekrar edilir, P çift ise 4. adıma geçilir. P çift ise periyot sinüsoidaldır.
(MP/2 - 1)(MP/2 -1) = MP - 1 = 0 mod n
Eğer MP/2 + 1 = 0 mod n ise 1. Adım tekrarlanır. MP/2 + 1 ≠ 0 ise 5. adıma geçilir.
►Son olarak, D = gcd(MP/2 - 1, n) is Öklid algoritması kullanılarak bulunur.
MP/2 + 1 ≠ 0 mod n 4. adımda sağlandığından, D n in bir asal çarpanıdır denilebilir.
Şimdi yukarıdaki adımlar göz önünde bulundurularak n = 91(=7*13) ün Shor Algoritmasıyla nasıl çarpanlarına ayrıldığını gösterelim.
1) m = 3 gibi rastgele bir pozitif tam sayı seçtik ve gcd(91, 3)=1 dedik.
2) Periyot P, F(a) = 3a mod 91 şeklinde bulunur.
Kuantum bilgisayar Shor Algoritmasını kullanarak periyordu P = 6 şeklinde bulur.
3) Periyot çift tam sayı olduğundan 4. adıma atlanır.
4) Eşitlik 0 mod 91 ‘ e eşit olmadığından 5. adıma geçilir.
3P/2 + 1 = 33 + 1 = 28 ≠ 0 mod 91
5) D = gcd(3P/2 - 1, 91) = gcd(33 - 1, 91) = gcd(26, 91) = 13
Kuantum bilgisayar kullanılarak yapılan bu hesaplama sonucunda n= 91'in asal çarpanı olan D = 13 olarak bulunur.