Shor Algoritması

Peter Shor 1994 yılında kuantum bilgisayarlarla çift asal sayıların çarpanlarının hesaplanmasına imkân veren bir algoritma geliştirdi. Bu algoritma özetle şu şekilde işler:

1. Asal çarpanlarını bulmak istediğiniz n sayısından küçük bir x tam sayısı alın
2. M bir tam sayı olmak üzere x^p=mn+1 (ya da x^p=1 mod n) eşitliğini sağlayan p sayısını bir kuantum bilgisayarı yardımıyla bulun
3. Bu eşitlik çözüldüğünde (x^p/2-1)(x^p/2+1)=mn olduğu görülür. Dolayısıyla x^p/2-1 ve x^p/2+1 sayıları n sayısıyla ortak çarpanlara sahip olabilir.

Bu algoritma her durumda n sayısının çarpanlarından birini vermez. Çünkü hesaplanan x^p/2-1 ve x^p/2+1 sayıları tamsayı olmayabilir ya da bu sayılardan biri aradığımız n sayısının tam katı olabilir. Böyle bir durumla karşılaşıldığında farklı bir x sayısı seçilerek hesap yeniden yapılır. Ta ki n sayısının çarpanlarından biri bulununcaya kadar.

Bu algoritmayı klasik bilgisayarlarla da uygulamak mümkündür. Örneğin 15 sayısının çarpanlarını bulmaya çalıştığımızı ve seçtiğimiz rastgele x sayısının 2 olduğunu düşünelim. P sayısını bulmak için x=2’nin tam kuvvetlerini birinci kuvvetinden başlayarak sırayla hesaplar ve x^p=mn+k biçiminde yazarız.

15 Sayısının çarpanlarını 2^4/2-1=3 ve 2^4/2+1=5 olarak hesaplandığında, her iki sayı da doğrudur. Bu algoritmayı klasik bilgisayarla uygulamaktaki ana sorun p sayısını bulmanın çok uzun zaman almasıdır.

Kuantum bilgisayarlarının sağladığı avantaj, süperpozisyon durumları üzerinde yapılan işlemlerle tek bir seferde olmasa bile sadece birkaç denemede p sayısını bulmaya imkân vermleri. Bunu nasıl gerçekleştiğini anlamak için önce modüler aritmetikle ilgili bir bilgiye daha ihtiyacımız var: Eğer x^p=1 mod n ve x^q=k mod n ise x^p+q=k mod n dir. Dolayısıyla p sayısını bulmanın bir başka yolu x sayısının kuvvetlerinin mod n’deki değerlerinde herhangi bir k sayısının hangi sıklıkla ortaya çıktığını tespit etmektir. Bir kuantum bilgisayarıyla aynı sonuçları hangi sıklıkla tekrar ettiğini bulmak için önce kübitlerin durumu muhtemel tüm kuvvet değerlerinin (q) bir süperpozisyonuna getirilir. Daha sonra x^q=k mod n hesabı yapılır. İşlemden sora kübitler muhtemel tüm sonuçların (k) bir süper pozisyonunda olacaktır. Son olarak aynı sonuçların hangi sıklıkla ortaya çıktığını tespit etmek için kübtlere “Fourier dönüşümü” denilen bir işlem uygulanır ve üzerlerinde ölçüm yapılır. Eğer işlemlerde kullanılan x değeri arzu edilen sonucu vermezse, başka bir x değeri ile hesaplar tekrar edilir.

Kısacası kuantum bilgisayarların bu problemi kolayca çözebilmesinin nedeni, klasik bilgisayarların aksine, x sayısının kuvvetlerini tek tek sırayla değil hepsini birden tek seferde hesaplayabilmeleridir.

Shor Algoritması için Örnek Kod [Python]

Büyük tamsayıları çarpanlarına ayırmak için yazılmış bir program.

https://github.com/lialkaas/qiskit-shors

import random
import sys
from assets import FactorClass

# Global variables
order = 3
limit = 10 ** order  # upper limit of the integer to be factored
sample_size = 10  # num of integers in a sample for finding a period
recursion_limit = 1000  # sys default set to 1000
seed = 3


def main():
    n = random.randint(10 ** (order - 1), limit)
    randint_set = FactorClass.sample(n, sample_size)
    p = FactorClass.euclidean(n, randint_set)
    try:
        if p is not None:
            q = int(n / p)
        else:
            print("-> Euclidean algorithm failed")
            p = FactorClass.modexp(n, randint_set)
            if p is not None:
                q = int(n / p)
            else:
                p, q = 1, n
                print("-> Classical Modexp failed")
    except OverflowError as message:
        q = 'q'
        print('Unable to find second factor q = n / p, because', message)
        if p is None:
            p = 'p'

    print("{} x {} = {}".format(p, q, n))


if __name__ == '__main__':
    print()
    sys.setrecursionlimit(recursion_limit)
    for i in range(seed):
        main()

bkz:https://akademikbulten.com/2020/02/kuantum-bilgisayarlar-caginda-kriptografi/