Hlavní navigace

Obstojí výpočetní složitost před kvantovými počítači?

Pavel Houser 5. 9. 2005

V předešlém dílu našeho zamyšlení o matematických zajímavostech souvisejících s šifrováním jsme za zabývali především prvočísly a faktorizací. Nyní se dostaneme k oblíbené otázce týkající se vztahu NP úplných problémů k problémům s polynomiální složitostí a ke kvantovým počítačům. Ohrozí kvantové počítače metodu RSA či kryptografii?

Na úvod je vhodné sebekriticky zopakovat, že následující text není dílem profesionálního matematika ani kryptologa. Tento text navazuje na článek Jak dlouho nám vydrží dnešní šifrovací metody?.
Co je co

Faktorizace: Rozklad čísla na dvě prvočísla. Faktorizace čísla 15 znamená zjistit, že 15 = 3×5. Faktorizovat obrovská čísla je výpočetně náročné.

Výpočetní složitost: Závislost trvání výpočtu na velikosti vstupu. Ještě jinak – jak s růstem velikosti vstupu roste doba výpočtu. Problémy, jejichž výpočetní složitost roste se vstupem exponenciálně, se obecně pokládají za prakticky nezvládnutelné.

NP úplné problémy: Třída problémů, pro které není znám algoritmus řešící je v polynomiálně rostoucím čase (a všeobecně se předpokládá, že žádný takový algoritmus ani neexistuje). Pokud je ovšem nějaké řešení už známo, lze jeho platnost v polynomiálně rostoucím čase ověřit (do nedeterminismu a věštíren se nebudeme zaplétat). Do této třídy problémů spadá například obchodní cestující, splnitelnost či určení pravdivostní hodnoty logické formule. Jednotlivé NP úplné problémy jsou na sebe vzájemně převoditelné.

DNA počítač: Zařízení, v němž se výpočetní postupy realizují prostřednictvím toho, jak se jednotlivé molekuly DNA „hodí/párují“ k sobě.

Heuristika: Přibližný postup, jakási zkratka, nebo spíše intuitivní strategie, která s určitou pravděpodobností vede k řešení a má smysl tam, kde nelze použít rigoróznějších postupů (algoritmus není znám, byl by příliš pomalý apod.)

Začneme problémem NP úplných problémů versus P. Clayův matematický ústav zařadil tuto otázku mezi 7 největších matematických problémů současnosti – každá z těchto úloh je přitom oceněna milionem dolarů. „Tržní“ cena problému NP/P je ovšem nejspíš mnohem vyšší.

V dalším textu budeme opět vycházet především z knihy Keitha Devlina Problémy pro třetí tisíciletí, jejíž české vydání by se mělo objevit ještě během letošního podzimu. Důkaz, že NP úplné problémy jsou řešitelné v polynomiálním čase, by (přinejmenším potenciálně) otřásl metodou RSA, protože by zároveň přinášel důkaz, že v polynomiálním čase je řešitelná také faktorizace. Ale co víc – zatímco efektivní algoritmy speciálně pro faktorizaci by umožnily postavit nové šifrování třeba na asymetrii problému obchodního cestujícího (neexistuje důkaz, že faktorizace spadá mezi NP úplné problémy), důkaz, že NP úplné problémy jsou totožné s problémy složitosti P, by už podobnou možnost přestavby šifrovacích systémů neumožňoval.

Devlin se nicméně domnívá, že nakonec se podaří dokázat různost NP úplných problémů od třídy P. Dokonce tvrdí, že jde o jediný z velkých problémů současné matematiky, u kterého je alespoň teoreticky možné, že řešení objeví amatér (u ostatních na seznamu Clayova ústavu je pro amatéra už mnohdy nemožné vůbec v plné šíři porozumět zadání). Možná dokonce, že pro řešení NP/P postačí jen JEDINÁ nová myšlenka. Devlin přitom pokládá za nejnadějnější následující postup: Objevíte úlohu, k jejíž „vlastní podstatě“ patří nemožnost řešení v polynomiálním čase – a potom nějak dokážete její ekvivalenci s třídou NP úplných problémů. Devlin však přiznává, že sám tímto způsobem nepokročil vůbec nikam.

Podrobnosti o těchto Devlinových názorech lze dohledat v článku na Science Worldu, přičemž podstatně podnětnější než původní článek je následující diskuse.

Mimochodem – dvorní matematik Science Worldu vystupující v diskusích pod nickem Mefisto se naopak domnívá, že v případě problémů NP/P bude dokázána jeho nerozhodnutelnost. Stejný názor zastává matematik Ian Stewart ve svém příspěvku o budoucnosti matematiky, který vyšel ve sborníku Příštích padesát let (Stewartův text je online dostupný také zde). Na Science Worldu najdete k celému problému NP/P také anketu – hlasování je jistě adekvátní cestou k řešení matematických záhad :-).

A zcela na okraj – když už jsme se dostali k Ianu Stewartovi, v jeho knize Čísla přírody najdete i hezkou hříčku týkající se prvočísel, kterou jsem v minulém článku zapomněl zmínit. Jak jistě víte, prvočísla se vyskytují kolem násobků čísla 4 nebo násobků 6. Otázka zní – lemují je nějak přednostně shora, nebo zdola? (jinak řečeno, je v zadaném dostatečně velkém intervalu více prvočísel tvaru 4n-1 než 4n+1, respektive 6n-1 versus 6n+1?)

Nyní přejdeme k druhé části tohoto zamyšlení, tedy ke kvantovým počítačům. Faktorizace je na kvantovém počítači skutečně realizovatelná s polynomiální složitostí. Výklady o tom, že se tak děje kvůli tomu, že by kvantový výpočet probíhal v paralelních vesmírech, jsou ovšem poněkud přitažené za vlasy. V češtině existuje podle mých informací zřejmě pouze jediný srozumitelný text, který by vysvětloval, jak vlastně onen kvantový (Shorův) faktorizační algoritmus funguje. Pochází z knihy Zkratka napříč časem, přičemž úryvky vyšly opět na Science Worldu. Kromě vlastní faktorizace stojí snad za pozornost, že v textu najdete také vysvětlení, jak si vlastně představit kvantový Turingův stroj nebo kvantový celulární automat.

Kvantový počítač však prozatím teorií výpočetní složitosti neotřásl. I když pomineme potíže s faktickou realizací kvantových počítačů (nově zjištěné problémy se samovolnou ztrátou koherence jsou popsány např. v článku na serveru Osel), faktorizace na kvantovém počítači je tak efektivní díky drobnému fíglu při manipulaci s čísly v rámci hodinové aritmetiky pomocí Fourierovy transformace (asi nemá smysl si nic nalhávat – většina z nás už stejně beznadějně zapomněla, o co v této proceduře jde).

Shrnuto, Shorův algoritmus se opravdu hodí de facto pouze pro faktorizaci. Pro efektivní řešení NP úplných úloh na kvantovém počítači v tuto chvíli není známa žádná procedura efektivnější než klasické postupy. Z čehož, jak se zdá, vyplývá, že i eventuální masivní technologický pokrok při konstrukci kvantových počítačů by sice ohrozil metodu RSA, ne však asymetrickou kryptografii jako takovou.

Závěrečná poznámka ke vztahu kvantových efektů a šifrování. Před zhruba rokem se objevovalo velké množství článků o tom, že ta a ta banka nasazuje systém pro kvantovou kryptografii. Na spadnutí měly být systémy fungující nejen v optickém kabelu, ale i při přenosech vzduchem. Dokonce se objevily zprávy, že EU chystá s ohledem na americký systém Echelon v této oblasti vlastní gigantický projekt (PC World). Poté ale vše nějak usnulo a o kvantové kryptografii prakticky přestalo být slyšet. Máte také ten dojem?

Anketa

Proč přestalo být o kvantové kryptografii v posledním roce slyšet?

Našli jste v článku chybu?

5. 9. 2005 22:53

Martin 'Bilbo' Petricek (neregistrovaný)
No, kvantova kryptografie je tak nejak zalozena na tom, ze po nejake specialni ceste posilam fotony, a jelikoz mereni ovlivni vysledek tak v podstate nemam sanci ty fotony 'odposlechnout' aniz bych znicil jejichz stav (a i tak zmeri jen jednu velicinu a ja s jednim fotonem poslu dve - treba 2 smery polarizace)

Jenze nevim jestli soucasne masiny pracujici s kvantovou kryptografii posilaji prave jen jeden foton ... nekde jsem cet ze jich posilaji vice (protoze asi poslat jediny foiton nezvladno…

5. 9. 2005 13:45

jozka (neregistrovaný)
No me se behem clanku vybavila Nadace od Asimova.
(aneb jako zaostaly jedinec to vnimam jako nadprirozene jevy)
Měšec.cz: Platby do zahraničí: pozor na tučné poplatky

Platby do zahraničí: pozor na tučné poplatky

DigiZone.cz: Mňam TV splnila slib a odešla z DVB-T

Mňam TV splnila slib a odešla z DVB-T

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Vitalia.cz: Vláknina: Rozpustná, nebo nerozpustná?

Vláknina: Rozpustná, nebo nerozpustná?

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

120na80.cz: Bojíte se encefalitidy?

Bojíte se encefalitidy?

DigiZone.cz: Digi CZ výrazně zlevnila balíček HBO

Digi CZ výrazně zlevnila balíček HBO

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

120na80.cz: 5 poporodních problémů a jejich řešení

5 poporodních problémů a jejich řešení

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony