Šoro algoritmas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Š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 (skaičių N dalinti iš visų pirminių skaičių didėjimo tvarka, jei padalinus iš kažkurio pirminio skaičiaus atsakymas bus taip pat pirminis skaičius, reiškia surastas raktas), 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ą.
Kanados kompanijos 2007 m. sukurtas 16 kubitų Orion (ar bet koks kitas kvantinis kompiuteris), kaip teigia pati kompanija negali ir negalės pagreitintai faktorizuoti (negalės nulaužti RSA) net padidinus kubitų skaičių, nes kvantinis kompiuteris duoda tik apytikslų rezultatą[1].
[taisyti] Nuorodos
- ↑ "Kvantinio kompiuterio fiasko pagal D-wave." (tekstas) blogas. Geordie Rose D-wave worldpress: 2006.