Prvočísla ano, faktorizace ne

Následující kauza má dlouhou (a pohnutou :-)) historii:

Loni před Vánoci mi Tomáš Krause přeposlal e-mail obsahující oskenovanou stránku z vědecké rubriky Koktejlu, kde se s odvoláním na New Scientist oznamoval významný objev na poli prvočísel. Kde se hýbou prvočísla, tam lze větřit také ohrožení šifer. Tištěný New Scientist k dispozici však nemám, verze webová v tomto ohledu mlčela. Ještě v prosinci mě redaktor vědecké rubriky Koktejlu Pavel Hošek odkázal na příští vydání časopisu Vesmír; v diskusi se čtenáři Science Worldu zastávala většina (např. Jan Poslušný alias Pajout) názor, že se nic neděje a že objev týkající se prvočísel s kryptografií nutně souviset nemusí, jenom novinářům to vždycky takhle „sepne“.

Pátrání je u konce. V lednovém Vesmíru konečně vyšel článek Pavla Pudláka, z něhož budeme nadále čerpat.

Jaká je tedy skutečnost? Tři indičtí matematici, Agrawal, Kayal a Saxena nalezli způsob, jak otázku, zda číslo X je prvočíslem, řešit v polynomiálním čase. Až dosud se úloha pokládala za NP problém, tedy takový, jehož složitost roste exponenciálně (i proto se v této souvislosti dumá o nasazení DNA nebo kvantových počítačů, viz níže). Nový objev umožňuje test v čase polynomiálním.

Velikost polynomu je ovšem stále hodně vysoká – 10 exp 12. Pavel Pudlák ve Vesmíru uvádí, že díky tomu bude polynomiální algoritmus rychlejší až u prvočísel v řádu 64 cifer. Fakticky lze také těžko i při polynomu stupně 12 realizovat luštění stále složitějších úloh (můžete si to představit následujícím způsobem: když složitost úlohy roste s X exp 3, po zdvojnásobení X řeším úlohu tak, že zdvojnásobím objem počítače – rychlost řešení mi díky třem rozměrům také poroste se třetí mocninou; samozřejmě se omlouvám znalcům, jde o hodně velké zjednodušení, počítač ve 12 rozměrech ale každopádně k dispozici nemáme).

Ale hlavně: Šifrovací klíče se generují násobením dvojice prvočísel (činitelé jsou tajným klíčem, součin klíčem veřejným). Opačný postup (tzv. faktorizace) je stále pokládána za úlohu se složitostí exponenciální. Náš algoritmus v polynomálním čase pouze zjistí, zda je určité číslo prvočíslem, nebo číslem složeným. Když víme, že jde o číslo složené, stále to ještě neznamená, že známe i rozklad.

Co s tím mají společného kvantové počítače? Definice NP problémů (tedy těch nepolynomiálních, respektive takových, u kterých zatím neznáme algoritmus s polynomiálním růstem složitosti) závisí na fyzikálních vlastnostech použitého počítače. I faktorizace by se stala polynomiální na počítači kvantovém – při použití tzv. Shorova algoritmu (to se v miniměřítku podařilo na kvantovém počítači IBM).

Autor tohoto článku se ovšem necítí kompetentní se podrobněji vyjadřovat k teoriím výpočetní složitosti; předpokládám, že řada čtenářů vidí do problému hlouběji.

Jinak: ohledně zkoumání provočíselnosti existuje samozřejmě celá řada elegantních matematických postupů: Malá Fermatova věta, ARCLP test apod. Vesměs ale mají svá omezení. Například Malá Fermatova věta umožňuje rychle identifikovat čísla složená; zbytek jsou pravděpodobně prvočísla, ale ne nutně.

A ještě jednou: Určení prvočíselnosti ještě neznamená, že nalezneme také rozklad na dvě prvočísla u čísla složeného (faktorizaci). Přitom právě faktorizací bychom se dostali k tajnému klíči. Ba právě naopak: rychlé testy na prvočíselnost spíše urychlují šifrování, tedy generování co nejdelších tajných klíčů.

A když už jsme u těch prvočísel, neodpustím si jednu perličku: Víte, jaká je role prvočísel v biologické evoluci?