WEBVTT

00:00:00.050 --> 00:00:02.790
Před 2000 lety Eukleides dokázal,

00:00:02.790 --> 00:00:06.290
že každé číslo má jedinečný
prvočíselný rozklad,

00:00:06.290 --> 00:00:08.980
který si můžeme představit
jako tajný klíč.

00:00:08.980 --> 00:00:14.510
Ukazuje se, že prvočíselný rozklad
je složitý problém.

00:00:14.510 --> 00:00:18.000
Vyjasníme si, co myslíme pojmy
"snadný" a "složitý"

00:00:18.000 --> 00:00:21.220
pomocí tzv. časové složitosti algoritmu.

00:00:21.220 --> 00:00:23.180
Všichni umíme násobit čísla

00:00:23.180 --> 00:00:27.550
a každý z nás pro urychlení
používá svůj vlastní postup.

00:00:27.550 --> 00:00:30.010
Pokud naprogramujeme počítač,
aby násobil čísla,

00:00:30.010 --> 00:00:33.460
tak to může provádět
mnohem rychleji než člověk.

00:00:33.460 --> 00:00:39.080
Zde je graf, který ukazuje kolik času potřebuje
počítač, aby vypočetl násobek dvou čísel.

00:00:39.080 --> 00:00:44.770
Potřebný čas pro získání výsledku
se zvyšuje s rostoucími čísly.

00:00:44.770 --> 00:00:50.700
Všimněte si, že čas pro výpočet se drží
pod 1s i s poměrně vysokými čísly.

00:00:50.700 --> 00:00:53.480
Proto je snadné provádět násobení.

00:00:53.480 --> 00:00:56.140
Teď to porovnejte
s prvočíselným rozkladem.

00:00:56.140 --> 00:01:00.220
Pokud by vám někdo řekl,
abyste našli prvočíselný rozklad čísla 589,

00:01:00.220 --> 00:01:03.180
tak si hned všimnete,
že se příklad zdá být těžší.

00:01:03.180 --> 00:01:06.790
Bez ohledu na vaši strategii to bude
vyžadovat použití metody pokus-omyl,

00:01:06.820 --> 00:01:10.760
dokud nenajdete číslo,
kterým lze 589 dělit.

00:01:10.760 --> 00:01:17.020
Až s tím dozápasíte, tak zjistíte,
že prvočíselný rozklad je (19 krát 31).

00:01:17.020 --> 00:01:22.980
Pokud byste měli najít
prvočíselný rozklad čísla 437231,

00:01:22.980 --> 00:01:26.510
tak byste to pravděpodobně
vzdali a vzali si na pomoc počítač.

00:01:26.510 --> 00:01:28.340
Tohle funguje dobře pro malá čísla,

00:01:28.340 --> 00:01:35.020
ale pokud zkusíme rozkládat větší čísla,
tak výsledek nebude spočítán "v rozumném čase".

00:01:35.020 --> 00:01:41.190
Čas potřebný k výpočtu rapidně
roste s přírůstkem potřebných kroků.

00:01:41.190 --> 00:01:44.480
A jak čísla rostou, tak počítač
potřebuje minuty a pak i hodiny.

00:01:44.480 --> 00:01:50.490
Nakonec bude potřebovat stovky nebo tisíce let
pro prvočíselný rozklad obrovských čísel.

00:01:50.490 --> 00:01:57.510
Proto říkáme, že je to těžký problém.
Kvůli nárůstu času potřebného k řešení.

00:01:57.510 --> 00:02:01.780
Takže prvočíselný rozklad je to, co Cocks použil
pro vytvoření řešení se zadními vrátky.

00:02:01.780 --> 00:02:03.170
Krok 1:

00:02:03.170 --> 00:02:09.880
Alice náhodně vygeneruje prvočíslo
přes 150 číslic dlouhé. Nazveme ho P1.

00:02:09.880 --> 00:02:15.250
Potom vygeneruje druhé náhodné prvočíslo
o zhruba stejné velikosti. Říkejme mu P2.

00:02:15.250 --> 00:02:18.410
Pak vynásobí tyto dvě prvočísla,

00:02:18.410 --> 00:02:23.660
aby dostala složené číslo N,
které má více než 300 číslic.

00:02:23.660 --> 00:02:26.720
Tento krok s násobením
zabere méně než sekundu.

00:02:26.720 --> 00:02:30.030
Zvládli byste to provést dokonce
i ve svém webovém prohlížeči.

00:02:30.030 --> 00:02:35.590
Potom vezme prvočíselný rozklad N,
(P1 krát P2), a schová ho.

00:02:35.590 --> 00:02:38.340
I kdyby se teď N dostalo
ke komukoliv jinému,

00:02:38.340 --> 00:02:43.020
tak by mu trvalo roky, než by na počítači
nalezl prvočíslený rozklad N.

00:02:43.020 --> 00:02:44.380
Krok 2:

00:02:44.380 --> 00:02:50.150
Cocks potřeboval nalézt funkci, která závisí
na znalosti prvočíselného rozkladu N.

00:02:50.150 --> 00:02:53.210
Kvůli tomu se podíval
do práce z roku 1760,

00:02:53.210 --> 00:02:56.960
jejímž autorem byl švýcarský
matematik Leonhard Euler.