Bitcoin mining (faktorizace)

[Marek Peca]

> No zatim udajne byl vyvinut pokus, ktery snad dokazuje, ze lze 
> faktorizovat cislo 15, ale myslim, ze jeste neni uplne jiste, ze se 
> skutecne dospelo k realnemu vysledku a neni to jen nahoda (zkratka ma to 
> zatim maly sigma koeficient). Takze v tuto chvili je SHA-256 zrejme 
> jeste pomerne velke sousto :-)
>
> Ale kazdopadne klasicka faktorizace bezi v polynomialni komplexite v N, 
> kdezto kvantova sice taky v polynomialni komplexite, ale jen v log(N). 
> Jinymi slovy klasicka roste polynomialne s poctem moznych stavu, kdezto 
> kvantova pouze s poctem bitu, do kterych se ty stavy vejdou. A to je 
> zatraceny rozdil.
> (..)

Zcela odbihate od otazky. Jedna vec je, zda umi kvantovy pocitac (QC) 
faktorizovat rychleji, nez klasicky pocitac (P). Pokud je mi znamo, zatim 
je pro QC znam asympt. rychlejsi alg. nez pro P. Neni zatim dokazano, ze 
pro P stejne asympt. rychly alg. byt nemuze. Ale je to rozhodne mozne, ze 
v tomto QC nad P zvitezi. Ovsem pozor, tento faktorizacni alg. neni 
NP-tezky, takze jine NP problemy nan nejsou v O(poly) prevoditelne.

Tudiz, zpatky k tomu, co me zajimalo. Je inverzni uloha k SHA-256 
prevoditelna na faktorizacni ulohu?

ZdraviM.P.