Hlavní navigace

Prvočísla ano, faktorizace ne

Pavel Houser 13. 2. 2003

Senzace se podle všeho nekoná: Nové objevy týkající se prvočísel nepředstavují bezprostřední ohrožení pro kryptografii.

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?

Našli jste v článku chybu?

17. 8. 2005 8:21

Jan Šimek (neregistrovaný)
Zajímavé, bylo by možné získat i zbytek příspěvku? (simek.jan@gmail.com)

18. 2. 2003 9:41

PaJaSoft (neregistrovaný)

Prikladam jeste jedno URL: http://www.mersenne.org/prime.htm , neni sice primo o prvocislech, ale o specifickych prvocislech, nicmene informace zde zminene jsou znamy odhadem 6 mesicu (aspon od zhruba rijna jsou na uvedem Webu i s komentarem)

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Měšec.cz: Nenechte se ošidit, když vám staví dům

Nenechte se ošidit, když vám staví dům

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

Recenze Westworld: zavraždit a...

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č?

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

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

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

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

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

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

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

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Vitalia.cz: Co pomáhá dítěti při zácpě?

Co pomáhá dítěti při zácpě?

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí