-
Před 2000 lety Eukleides dokázal,
-
že každé číslo má jedinečný
prvočíselný rozklad,
-
který si můžeme představit
jako tajný klíč.
-
Ukazuje se, že prvočíselný rozklad
je složitý problém.
-
Vyjasníme si, co myslíme pojmy
"snadný" a "složitý"
-
pomocí tzv. časové složitosti algoritmu.
-
Všichni umíme násobit čísla
-
a každý z nás pro urychlení
používá svůj vlastní postup.
-
Pokud naprogramujeme počítač,
aby násobil čísla,
-
tak to může provádět
mnohem rychleji než člověk.
-
Zde je graf, který ukazuje kolik času potřebuje
počítač, aby vypočetl násobek dvou čísel.
-
Potřebný čas pro získání výsledku
se zvyšuje s rostoucími čísly.
-
Všimněte si, že čas pro výpočet se drží
pod 1s i s poměrně vysokými čísly.
-
Proto je snadné provádět násobení.
-
Teď to porovnejte
s prvočíselným rozkladem.
-
Pokud by vám někdo řekl,
abyste našli prvočíselný rozklad čísla 589,
-
tak si hned všimnete,
že se příklad zdá být těžší.
-
Bez ohledu na vaši strategii to bude
vyžadovat použití metody pokus-omyl,
-
dokud nenajdete číslo,
kterým lze 589 dělit.
-
Až s tím dozápasíte, tak zjistíte,
že prvočíselný rozklad je (19 krát 31).
-
Pokud byste měli najít
prvočíselný rozklad čísla 437231,
-
tak byste to pravděpodobně
vzdali a vzali si na pomoc počítač.
-
Tohle funguje dobře pro malá čísla,
-
ale pokud zkusíme rozkládat větší čísla,
tak výsledek nebude spočítán "v rozumném čase".
-
Čas potřebný k výpočtu rapidně
roste s přírůstkem potřebných kroků.
-
A jak čísla rostou, tak počítač
potřebuje minuty a pak i hodiny.
-
Nakonec bude potřebovat stovky nebo tisíce let
pro prvočíselný rozklad obrovských čísel.
-
Proto říkáme, že je to těžký problém.
Kvůli nárůstu času potřebného k řešení.
-
Takže prvočíselný rozklad je to, co Cocks použil
pro vytvoření řešení se zadními vrátky.
-
Krok 1:
-
Alice náhodně vygeneruje prvočíslo
přes 150 číslic dlouhé. Nazveme ho P1.
-
Potom vygeneruje druhé náhodné prvočíslo
o zhruba stejné velikosti. Říkejme mu P2.
-
Pak vynásobí tyto dvě prvočísla,
-
aby dostala složené číslo N,
které má více než 300 číslic.
-
Tento krok s násobením
zabere méně než sekundu.
-
Zvládli byste to provést dokonce
i ve svém webovém prohlížeči.
-
Potom vezme prvočíselný rozklad N,
(P1 krát P2), a schová ho.
-
I kdyby se teď N dostalo
ke komukoliv jinému,
-
tak by mu trvalo roky, než by na počítači
nalezl prvočíslený rozklad N.
-
Krok 2:
-
Cocks potřeboval nalézt funkci, která závisí
na znalosti prvočíselného rozkladu N.
-
Kvůli tomu se podíval
do práce z roku 1760,
-
jejímž autorem byl švýcarský
matematik Leonhard Euler.
