Šoro algoritmas
Šoro algoritmas (angl. Shor's algorithm) yra kvantinis algoritmas faktorizavimui pirminiais skaičiais skaičiaus N (bitais) per laiką O( ( log 2 ⁡ N ) 2 {\displaystyle (\log _{2}N)^{2}} ) ir užima O( log 2 ⁡ N {\displaystyle \log _{2}N} ) vietos (kubitų n = log 2 ⁡ N {\displaystyle n=\log _{2}N} ), pavadintas pagal Piterį Šorą. Klasikinis algoritmas užtruktų O ( 2 ( log 2 ⁡ N ) 1 / 3 ) {\displaystyle O(2^{(\log _{2}N)^{1/3}})} laiko. 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 naudoja 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 2 ⁡ N {\displaystyle \log _{2}N} )k) su bet kuriuo k. Tuo tarpu Šoro algoritmas gali nulaužti RSA per polinominį (per trumpą) laiką. 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 ⋅ n 1 / 3 ⋅ ( log 2 ⁡ n ) 2 / 3 {\displaystyle e^{({\frac {64}{9}})^{1/3}\cdot n^{1/3}\cdot (\log _{2}n)^{2/3}}} laiko, kur n = log ⁡ N {\displaystyle n=\log N} , e natūrinis logoritmas ( e ≈ 2 , 7 {\displaystyle e\approx 2,7} ). Kvantiniam faktorizavimo algoritmui tereikia O ( n 2 log 2 ⁡ n log 2 ⁡ log 2 ⁡ n ) {\displaystyle O(n^{2}\log _{2}n\log _{2}\log _{2}n)} laiko. Kur n = log 2 ⁡ N {\displaystyle n=\log _{2}N} yra kubitų skaičius. Pavyzdžiui, su klasikiniu kompiuteriu faktorizuoti 512 bitų (154 skaitmenų) skaičių reikia e ( 64 9 ) 1 / 3 ⋅ 512 1 / 3 ⋅ ( log 2 ⁡ 512 ) 2 / 3 = e 1.923 ⋅ 8 ⋅ 4.327 = e 66.6 = 8 ⋅ 10 28 {\displaystyle e^{({\frac {64}{9}})^{1/3}\cdot 512^{1/3}\cdot (\log _{2}512)^{2/3}}=e^{1.923\cdot 8\cdot 4.327}=e^{66.6}=8\cdot 10^{28}} laiko. Jei kompiuteris dirba 1GHz dažniu ir išnaudoja apie 10 4 {\displaystyle 10^{4}} vartų, bei susideda is 10 4 {\displaystyle 10^{4}} procesorių, tai jis užtruks apie 10 11 {\displaystyle 10^{11}} sekundžių arba apie 10000 metų (gali būti, kad kai kuriais atvejais vietoje constantos c = ( 64 9 ) 1 / 3 ≈ 1.923 {\displaystyle c=({\frac {64}{9}})^{1/3}\approx 1.923} būna konstanta ( 32 9 ) 1 / 3 ≈ 1.526 {\displaystyle ({\frac {32}{9}})^{1/3}\approx 1.526} , o vietoje e = 2.7 {\displaystyle e=2.7} gali būti vis tik 2 ir tada tampa aišku, kodėl buvo faktorizuotas net >600 bitų skaičius). e ( 32 9 ) 1 / 3 ⋅ n 1 / 3 ⋅ ( log 2 ⁡ n ) 2 / 3 = e ( 32 9 ) 1 / 3 ⋅ 512 1 / 3 ⋅ ( log 2 ⁡ 512 ) 2 / 3 = e 1.526 ⋅ 8 ⋅ 4.327 = e 52.8 = 8.7 ⋅ 10 22 ≈ 10 23 {\displaystyle e^{({\frac {32}{9}})^{1/3}\cdot n^{1/3}\cdot (\log _{2}n)^{2/3}}=e^{({\frac {32}{9}})^{1/3}\cdot 512^{1/3}\cdot (\log _{2}512)^{2/3}}=e^{1.526\cdot 8\cdot 4.327}=e^{52.8}=8.7\cdot 10^{22}\approx 10^{23}} laiko. Su 1 GHz, 10 4 {\displaystyle 10^{4}} „skaičiavimo vartų“ ir 10 4 {\displaystyle 10^{4}} procesorių, tai užtruks 870000 s arba 10 dienų. Kvantiniui kompiuteriui reikia n 2 log 2 ⁡ n log 2 ⁡ log 2 ⁡ n = 512 2 log 2 ⁡ 512 log 2 ⁡ log 2 ⁡ 512 = 262144 ⋅ 9 ⋅ 3.17 = 7478968 ≈ 10 7 {\displaystyle n^{2}\log _{2}n\log _{2}\log _{2}n=512^{2}\log _{2}512\log _{2}\log _{2}512=262144\cdot 9\cdot 3.17=7478968\approx 10^{7}} laiko. Akivaizdu, jog užtenka 1 MHz kvantinio kompiuterio, norint suspėti per 10 sekundžių. Norint faktorizuoti pirminiais skaičiais 1024 bitų skaičių, kvantiniam kompiuteriui reikia: n 2 log 2 ⁡ n log 2 ⁡ log 2 ⁡ n = 1024 2 log 2 ⁡ 1024 log 2 ⁡ log 2 ⁡ 1024 = 1048576 ⋅ 10 ⋅ 3.32 = 34812723 ≈ 3 ⋅ 10 7 {\displaystyle n^{2}\log _{2}n\log _{2}\log _{2}n=1024^{2}\log _{2}1024\log _{2}\log _{2}1024=1048576\cdot 10\cdot 3.32=34812723\approx 3\cdot 10^{7}} laiko. Norint faktorizuoti 4096 bitų skaičių pirminiais skaičiais (4096 yra didžiausias naudojamas skaičiaus ilgis RSA saugume), kvantiniam kompiuteriui reikia: n 2 log 2 ⁡ n log 2 ⁡ log 2 ⁡ n = 4096 2 log 2 ⁡ 4096 log 2 ⁡ log 2 ⁡ 4096 = 16777216 ⋅ 12 ⋅ 3.58 = 720749199 ≈ 7 ⋅ 10 8 {\displaystyle n^{2}\log _{2}n\log _{2}\log _{2}n=4096^{2}\log _{2}4096\log _{2}\log _{2}4096=16777216\cdot 12\cdot 3.58=720749199\approx 7\cdot 10^{8}} laiko. 1 MHz kvantinis kompiuteris tam užtruktų apie valandą.