Šoro algoritmas

**Šoro algoritmas** () yra kvantinis algoritmas faktorizavimui pirminiais skaičiais skaičiaus *N* (bitais) per laiką O((\log_2 N)^2) ir užima O(\log_2 N) vietos (kubitų n=\log_2 N), pavadintas pagal Piterį Šorą. Klasikinis algoritmas užtruktų 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)*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^{(\frac{64}{9})^{1/3}\cdot n^{1/3}\cdot (\log_2 n)^{2/3}} laiko, kur n=\log N, e natūrinis logoritmas (e\approx 2,7). Kvantiniam faktorizavimo algoritmui tereikia O(n^2\log_2 n \log_2\log_2 n) laiko. Kur n=\log_2 N yra kubitų skaičius.
:Pavyzdžiui, su klasikiniu kompiuteriu faktorizuoti 512 bitų (154 skaitmenų) skaičių reikia
: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 vartų, bei susideda is 10^4 procesorių, tai jis užtruks apie 10^{11} sekundžių arba apie 10000 metų (gali būti, kad kai kuriais atvejais vietoje constantos c=(\frac{64}{9})^{1/3}\approx 1.923 būna konstanta (\frac{32}{9})^{1/3}\approx 1.526, o vietoje e=2.7 gali būti vis tik 2 ir tada tampa aišku, kodėl buvo faktorizuotas net >600 bitų skaičius).
: 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 „skaičiavimo vartų“ ir 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\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\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\cdot 12\cdot 3.58=720749199\approx 7\cdot 10^8 laiko.
: 1 MHz kvantinis kompiuteris tam užtruktų apie valandą.

## Nuorodos
* http://www.senko-corp.co.jp/qcs/shor.html 
* http://xxx.lanl.gov/pdf/quant-ph/9508027 
* http://feynman.mit.edu/ike/homepage/papers/NATURE-chuang-group-shor-factoring-experiment-v414-p883-20dec01.pdf 
* http://alumni.imsa.edu/~matth/quant/299/paper/node20.html