Šoro algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

   Informacija šiame straipsnyje nėra sutvarkyta - Straipsnis turi prasidėti aiškiu apibrėžimu
Jei galite, prašome sutvarkyti šį puslapį. Tik tada bus galima ištrinti šį pranešimą.
Priežastys, dėl kurių straipsnis laikomas nesutvarkytu, aiškinamos straipsnyje Nesutvarkyti straipsniai.

Šoro algoritmas (angl. Shor's algorithm) yra kvantinis algoritmas faktorizavimui skaičiaus N per laiką O((lg N)3) ir užima O(lg N) vietos, pavadintas pagal Piterį Šorą.

Algoritmas yra reikšmingas, kadangi numato, kad RSA, populiarus viešo-rakto kriptografijos metodas, gali būti lengvai nulaužtas su pakankamai dideliu (daug kubitų turinčiu) kvantiniu kompiuteriu. RSA naudoją viešą raktą N, kuris yra dviejų sudaugintų pirminių skaičių rezultatas. Vienas būdas nulaužti RSA yra skaičiaus N faktorizavimas, bet su klasikiniu algoritmu, faktorizavimas tampa vis daugiau ir daugiau laiko reikalaujantis, kai skaičius N didėja. Nėra žinomas klasikinis algoritmas kuris galėtų faktorizuoti N per laiką O((log N)k) su bet kuriuo k. Tuo tarpu Šoro algoritmas gali nulaužti RSA per poliminalų (per trumpą) laiką. Klasikinis kompiuteris užtruktų O(2N) laiko. Jei N labai didelis skaičius faktorizavimas su klasikiniu kompiuteriu užtruktų milijardus metų, tuo tarpu kvantinis kompiuteris tokį patį skaičių N faktorizuotų per keletą valandų.

Kaip ir daugelis kvantinių algoritmų, Šoro algoritmas yra tikimybinis: jis duoda su didele tikimybe teisingą atsakymą, ir neteisingo atsakymo tikimybė gali mažėti kartojant algoritmą.

Greičiausias klasikinis faktorizavimo algoritmas užtrunka e^[((64/9)^(1/3))*((ln n)^(1/3))*((ln ln n)^2/3)] laiko, kur n yra kiekis skaitmenų skaičiuje, kuris bus faktorizuojamas. Šoro faktorizavimo algortimui reikia tik (log n)^(2+ε) (kur ε labai mažas) laiko.

[taisyti] Nuorodos

http://www.senko-corp.co.jp/qcs/shor.html