Algoritmus pro prvočísla

Loni v srpnu byl vyřešen problém, který – řečeno s trochou nadsázky – zajímal už slavného J. C. F. Gausse a jehož kořeny sahají ještě hlouběji do historie. Indičtí matematici Manindra Agrawal, Neeraj Kayal a Nitin Saxena nalezli polynomiální algoritmus pro určení, zda je dané přirozené číslo prvočíslem. Agrawal je profesorem teoretické informatiky na Indické technice v Kanpuru. Kayal a Saxena jsou jeho studenti, kteří teprve loni začali postgraduální doktorandské studium. Způsob, jímž problém vyřešili, odpovídá dnešní době. Agrawal měl jistou domněnku, pomocí níž chtěl algoritmus sestrojit. Jeho domněnku Kayal a Saxena v letech 2000 až 2001 testovali na počítači, a protože se ukázalo, že ji experimenty potvrzují, začali loni v dubnu na problému intenzivně pracovat. Studenti informatiky jistě nemají tak hluboké znalosti z teorie čísel jako matematici, kteří se na tento obor specializují, je však možné, že právě díky tomu se pokusili o něco skutečně originálního. Coby zkušení účastníci matematických olympiád měli dobré předpoklady a nechybělo jim ani odhodlání. Místo toho, aby v létě odjeli na prázdniny, pokračovali spolu se svým profesorem v práci. V červenci se konečně dostavil úspěch, chyběla pouze jedna věc. K tomu, aby prokázali, že jejich algoritmus funguje, bylo potřeba dokázat, že se určitý typ prvočísel vyskytuje dost často. Teorém, který potřebovali, nejen vypadal pravděpodobně, ale také se zdálo, že je to něco, co už někdo zkoumal. Díky internetu brzy zjistili, že takový výsledek publikoval E. Fouvry r. 1985. Tím byl jejich důkaz dokončen.

Proč jsou prvočísla důležitá

Prvočísla jsou 2, 3, 5, 7, 11, …, tj. čísla větší než 1, která kromě sebe a jedničky nemají jiné dělitele. Jsou to jakési základní prvky, z nichž se ostatní čísla sestavují násobením. Prvočísla jsou důležitá skoro ve všech oborech matematiky a praktické uplatnění mají i v informatice, zejména v kryptografii (viz Vesmír 71, 615, 1992/11). Ověřit pro malé číslo n, zda jde o prvočíslo, je snadné. Musíme n zkusit postupně vydělit všemi čísly od dvojky do n – 1. Stačí se trochu zamyslet, abychom si uvědomili, že ve skutečnosti nemusíme testovat čísla větší než √n, což je pro větší čísla n značná úspora. Například pro čísla, která jsou menší než milion, nám stačí méně než tisíc dělení. Čísla kolem milionu jsou poměrně malá. V roce 1914 publikoval D. N. Lehmer seznam všech prvočísel do deseti milionů, a přitom jej sestavil bez použití mechanických zařízení. V době výkonných počítačů začíná být úloha zajímavá, až když je počet cifer řádově ve stovkách, tedy pro čísla 10¹⁰⁰ a výše. To jsou čísla, pro která už nemůžeme použít naivní postup, ale stále s nimi lze ještě dobře provádět elementární aritmetické operace (můžeme je sčítat, násobit, dělit atd.).

Z praktického hlediska je nejzajímavější vědět, pro jak velká čísla dokážeme pomocí počítačů rozhodnout, zda jde o prvočísla. To ovšem Agrawal s Kayalem a Saxenem nevyřešili. Problém, který vyřešili, byl teoretický, přesněji řečeno matematický. Našli odpověď na otázku, zda existuje algoritmus určitého, matematicky přesně definovaného typu. Tato definice říká, že algoritmus smí použít jen takový počet elementárních kroků, který je omezen nějakým polynomem v závislosti na počtu cifer testovaného čísla. Má-li číslo k cifer, potom je řádově velké 10^k. Budeme-li ho zkoušet vydělit všemi čísly menšími, použijeme přibližně 10^k dělení. V tomto případě počet kroků závisí exponenciálně na k. I když budeme zkoušet jenom potenciální dělitele menší než odmocnina, bude počet kroků √10^k ≈ 3,16^k. Tato funkce roste pomaleji, ale stále je to exponenciální funkce (navíc dělení není zcela elementární operace). Naproti tomu Agrawalův, Kayalův a Saxenův algoritmus potřebuje nanejvýš c . k¹² elementárních kroků, kde c je nějaká konstanta. Čili počet kroků tohoto algoritmu je omezen polynomem c . x¹² v závislosti na počtu cifer čísla.

Polynomiální algoritmy

Je dobře známo, že exponenciální funkce rostou velice rychle. Algoritmy, které vyžadují exponenciální počet kroků, se dají použít jen pro malá čísla, a proto se také snažíme hledat polynomiální algoritmy, ve kterých je počet kroků omezen polynomem. Klasifikovat algoritmy na polynomiální, exponenciální apod. podle typu funkce omezující počet kroků algoritmu je samozřejmě jen konvence a v praxi se může stát, že některý exponenciální algoritmus je lepší než polynomiální. Např. x¹² je větší než 2^x pro x = 64, a tudíž pro 64ciferná čísla je lepší použít exponenciální algoritmus s omezením 2^x než polynomiální algoritmus s omezením x¹². Nicméně je to užitečná konvence, která se osvědčila jak v teorii, tak v praxi. Ukáže-li se totiž, že pro nějakou úlohu existuje polynomiální algoritmus, potom se skoro vždy, dříve nebo později, najde i skutečně prakticky aplikovatelný algoritmus. Pojem polynomiální algoritmus vznikl v 60. letech 20. století v době, kdy se formoval nový obor – teorie složitosti. Předtím matematici hledali rychlé algoritmy pro různé úlohy a prvočíselnost je velice zajímala, ale co přesně „rychlý algoritmus“ znamená, nebylo definováno. Samotný algoritmus byl přesně definován nedlouho předtím, ve 30. letech 20. století.

Úloha najít vlastního dělitele

Nakonec bych chtěl upozornit na rozdíl mezi úlohou určit, zda číslo je prvočíslo, a úlohou najít vlastního dělitele v případě, že dané číslo prvočíslem není. Ač spolu tyto problémy velice souvisejí a první z nich má polynomiální algoritmus, stále se domníváme, že druhý problém takový algoritmus nemá. Všechny rychlé algoritmy na prvočíselnost jsou založeny na testování pouze určitých příznaků toho, že číslo je prvočíslem, aniž bychom se snažili vlastního dělitele skutečně najít. Problém, jenž se podařilo Agrawalovi, Kayalovi a Saxenovi vyřešit, spočíval v nalezení malého množství snadno testovatelných příznaků, které s jistotou zaručují, že je číslo prvočíslem. Nalézt vlastního dělitele se zdá být mnohem těžší. Pokud by se našel polynomiální algoritmus i pro tuto úlohu, znamenalo by to převrat nejen v teorii, ale vážně by byly ohroženy téměř všechny šifrovací metody. V nejpoužívanějších šifrovacích klíčích se volí dvě prvočísla, která jsou součástí tajného klíče a jejichž součin je složkou klíče veřejného. Pokud se někomu podaří z daného čísla najít činitele, získá tím tajný klíč. I když zatím vše nasvědčuje tomu, že hledání dělitele je těžká úloha, nemáme pro to důkaz, stejně jako nemáme důkazy pro řadu dalších hypotéz z teorie složitosti. Pozoruhodná je také následující souvislost. Kdyby se podařilo dokázat, že úloha nalézt dělitele vyžaduje exponenciálně mnoho kroků, ¹⁾ dal by se každý pravděpodobnostní polynomiální algoritmus upravit na obyčejný polynomiální algoritmus. Speciálně bychom dostali polynomiální algoritmy pro prvočíselnost ze známých pravděpodobnostních algoritmů (viz rámeček 1 ). Stručně řečeno, z obtížnosti nalezení dělitele bychom mohli odvodit jednoduchost určení prvočíselnosti jiným způsobem, než to udělali Agrawal, Kayal a Saxena.

Dosavadní zkušenosti však nasvědčují tomu, že najít důkaz neexistence polynomiálního algoritmu pro nějakou úlohu je mnohem složitější než takový algoritmus najít. V podstatě zatím nemáme žádnou metodu, jíž bychom mohli neexistenci polynomiálních algoritmů dokázat. ²⁾ Na to, kdy se povede tuto bariéru prolomit, se uzavírají sázky a jsou vypsány i finanční odměny. Dříve jsem tipoval, že se to podaří mladému ruskému matematikovi. Dnes bych se spíše vsadil, že to bude Ind nebo Číňan. Mimo jiné i proto, že mnohé rozvojové země podporují vědu více než země postkomunistické.