Právem bychom mohli označit prvočísla za opravdu magická. Fascinují matematiky už od nepaměti. Již Euklides dokázal o prvočíslech několik pozoruhodných tvrzeních. Například že prvočísel je nekonečně mnoho nebo že každé přirozené číslo je buď prvočíslem nebo může být vyjádřeno jako součin jednoznačně určených prvočísel, přičemž nezáleží na pořadí, v jakém jsou čísla zapsána. To druhé tvrzení je vám určitě dobře známé, ale možná jste si to neuvědomili – jedná se o klasický rozklad čísla na prvočinitele (např. 1430 = 2 x 5 x 11 x 13). Dnes si můžete doplnit informaci, že toto tvrzení je známé pod názvem Základní věta algebry.
Pokud jste se někdy z dlouhé chvíle snažili zabavit hledáním prvočísel, pak tvrzení, že jich je nekonečně mnoho, by vás mohlo překvapit. Přestože se v první stovce nalézá poměrně dost prvočísel, s rostoucí velikostí čísel začíná jejich rozložení řídnout. Na první pohled není vůbec jasné, jestli nakonec prvočísla úplně nevymizí.
Např. mezi čísly 2 a 20 nalezneme prvočísel osm, ale mezi čísly 102 a 120 už jen čtyři. Ve stovce čísel mezi čísly 2101 a 2200 je deset prvočísel, ale ve stovce mezi 10 000 001 a 10 000 100 jsou jen prvočísla dvě. Toto postupné řídnutí prvočísel můžeme vyjádřit pomocí funkce. Její funkční hodnoty jsou zapsány v následující tabulce:
N f(N) f(N)/N
1 000 168 0.168
10 000 1 229 0.123
100 000 9 592 0.095
1 000 000 78 498 0.078
10 000 000 664 579 0.066
100 000 000 5 761 455 0.058
Přestože poměr f(N)/N s rostoucím N neustále klesá, prvočísla nikdy úplně nevymizí. Důkaz
Jak testovat prvočísla?
Nejjednodušší algoritmus k určení, zda dané číslo N je či není prvočíslem, je založen na metodě prvočíselného rozkladu. Dané číslo N se postupně pokusíme dělit všemi prvočísly, která jsou menší nebo rovna odmocnině z N (dále pak ozn. sqrt(N)). (Pozn. Dělitele větší než sqrt(N) nemusíme ani zkoušet, protože pokud má N prvočíselné dělitele, musí alespoň jeden z nich být menší nebo roven sqrt(N).) Pokud žádné z těchto prvočísel nedělí bezezbytku číslo N, pak číslo N označíme za prvočíslo. Tento algoritmus lze ale použít pouze pro malá čísla. Pokud budeme chtít rozložit nějaké dané desetimístné číslo, pak průměrný počítač je nám schopen najít jeho prvočíselný rozklad téměř okamžitě. Ale i tomu nejrychlejšímu počítači by trvalo asi dvě hodiny pokud by měl najít prvočíselný rozklad čísla 20místného, a na rozkladu čísla 50místného by musel pracovat deset miliard let. Někdy stačí pouze štěstí a rozklad daného čísla nalezneme poměrně rychle, ale pokud je číslo prvočíslem, pak abychom si byli svou odpovědí jistí, musíme vyzkoušet všechna prvočísla menší nebo rovna sqrt(N). Pokud by některého čtenáře zajímalo, jak se vypořádat s tímto problémem, může se zkusit podívat na jiný algoritmus tzv. ARCLP-test, který je schopen určit prvočíselnost 20místného čísla zhruba za 10 sekund a 50místného za asi 15 sekund. Algoritmus objevili v roce 1986 matematici: L. M. Adleman, R.S. Rumely, H. Cohen, H.W. Lenstra a C. Pomerance, kteří vyšli z malé Fermatovy věty a poté navrhli jednu z nejlepších obecných metod pro testování prvočíselnosti.
Jak utajit komunikaci?
Celou dobu se tu bavíme o prvočíslech, avšak stále nám uniká podstata, k čemu nám to tedy je. Odpověď je velmi snadná – šifrování. Každý běžně používá internet, posílá emaily, fotky a aniž by o tom věděl, využívá při tom prvočísla.
Pokud máme k dispozici rychlý počítač a využijeme některého testu prvočíselnosti např. ARCLP, pak velmi snadno nalezneme dejme tomu dvě 75místná prvočísla. Jejich vynásobením získáme složené číslo, které bude 149-150místné. Teď si vyberte nějakého vašeho „oblíbeného“ kamaráda a dejte mu za úkol nalézt prvočíselný rozklad tohoto čísla (tzv. faktorizace). I kdyby jste mu prozradili, že má hledat součin dvou velkých prvočísel, nebude schopen tento problém vyřešit. Zatímco zjistit, zda dané číslo je prvočíslem může trvat řádově sekundy, i nejlepší faktorizační programy na nejrychlejších počítačích můžou hledat prvočíselný rozklad opravdu velmi dlouho – roky, desetiletí, staletí.
Tohoto poznatku se využívá v šifrovacích metodách. V roce 1975 W. Diffie a M. Hellman vytvořili systém veřejného klíče (PKS – public key systém), ve kterém potencionální příjemce využívá hned dvou klíčů – šifrovacího a dešifrovacího. Šifrovací klíč je volně dostupný (mnoho uživatelů ho zveřejňuje na svých webových stránkách) a kdokoliv, kdo chce poslat zprávu osobě A, vyhledá jeho šifrovací klíč, kterým zašifruje svou zprávu a odešle ji. Zprávu osoba A dešifruje pomocí svého dešifrovacího klíče, který zná jen ona sama.
Ačkoliv to vypadá jednoduše, realizace je poněkud složitější. Tento navržený systém nedosahoval požadované bezpečnostní úrovně. Až metoda vyvinuta Ronaldem Rivestem, Adi Shamirem a Leonardem Adlemanem byla dostatečně robustní. Jejich systém RSA se dnes běžně používá v bankovnictví.
Šifrovací proces by měl umět zašifrovat zprávu natolik, aby ji bez použití dešifrovacího klíče nebylo možné rozluštit. Avšak z podstaty každého systému vyplývá, že příjemce musí být schopen šifru rozluštit, a proto musí existovat matematický vztah mezi šifrovacím a dešifrovacím klíčem. Takže teoreticky by mělo být možné získat ze šifrovacího klíče klíč dešifrovací. Přesto lze zprávu zašifrovat tak, aby to prakticky možné nebylo. V případě RSA systému se utajený dešifrovací klíč skládá ze dvou např. 75místních prvočísel a veřejný šifrovací klíč je jejich součinem. Zašifrování tak odpovídá zhruba násobení dvou velkých 75místních prvočísel, zatímco dešifrování odpovídá faktorizaci daleko většího 150místného čísla, což je i při současných znalostech a technologii neproveditelný úkol.
Jakou informaci si z listingu odnést?
Je třeba si uvědomit, že určení prvočíselnosti (zda číslo je prvočíslem) a rozklad daného čísla na jeho prvočinitele (faktorizace) jsou dva různé problémy. Můžeme velmi rychle určit jestli číslo N je prvočíslem, ale nemusíme už tak snadno nalézt jeho rozklad na prvočísla. Tohoto faktu využíváme při šifrování komunikace.
Finální souřadnice?
Abyste získali souřadnice schránky, je před vámi úkol provést jednoduchou faktorizaci, a to čísla 82711.
N 49° 46.A E 018° 26.(B-2)
(Pozn. A<B)
Lovu zdar :)
Zajímavé články:
Literatura:
-
DEVLIN, Keith J. Jazyk matematiky: jak zviditelnit neviditelné. 1. vydání v českém jazyce. Překlad Jan Švábenický. Praha: Argo, 2002, 343 s., 
s. barev. obr. příl. Aliter (Argo: Dokořán). ISBN 80-865-6909-8.
-
SINGH, Simon. Kniha kódů a šifer: tajná komunikace od starého Egypta po kvantovou kryptografii. Praha: Dokořán, 2003, 382 s. ISBN 80-865-6918-7.