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

0:00:02.790,0:00:06.290
že každé číslo má jedinečný[br]prvočíselný rozklad,

0:00:06.290,0:00:08.980
který si můžeme představit[br]jako tajný klíč.

0:00:08.980,0:00:14.510
Ukazuje se, že prvočíselný rozklad[br]je složitý problém.

0:00:14.510,0:00:18.000
Vyjasníme si, co myslíme pojmy[br]"snadný" a "složitý"

0:00:18.000,0:00:21.220
pomocí tzv. časové složitosti algoritmu.

0:00:21.220,0:00:23.180
Všichni umíme násobit čísla

0:00:23.180,0:00:27.550
a každý z nás pro urychlení[br]používá svůj vlastní postup.

0:00:27.550,0:00:30.010
Pokud naprogramujeme počítač,[br]aby násobil čísla,

0:00:30.010,0:00:33.460
tak to může provádět[br]mnohem rychleji než člověk.

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

0:00:39.080,0:00:44.770
Potřebný čas pro získání výsledku[br]se zvyšuje s rostoucími čísly.

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

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

0:00:53.480,0:00:56.140
Teď to porovnejte[br]s prvočíselným rozkladem.

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

0:01:00.220,0:01:03.180
tak si hned všimnete,[br]že se příklad zdá být těžší.

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

0:01:06.820,0:01:10.760
dokud nenajdete číslo,[br]kterým lze 589 dělit.

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

0:01:17.020,0:01:22.980
Pokud byste měli najít[br]prvočíselný rozklad čísla 437231,

0:01:22.980,0:01:26.510
tak byste to pravděpodobně[br]vzdali a vzali si na pomoc počítač.

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

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

0:01:35.020,0:01:41.190
Čas potřebný k výpočtu rapidně[br]roste s přírůstkem potřebných kroků.

0:01:41.190,0:01:44.480
A jak čísla rostou, tak počítač[br]potřebuje minuty a pak i hodiny.

0:01:44.480,0:01:50.490
Nakonec bude potřebovat stovky nebo tisíce let[br]pro prvočíselný rozklad obrovských čísel.

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

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

0:02:01.780,0:02:03.170
Krok 1:

0:02:03.170,0:02:09.880
Alice náhodně vygeneruje prvočíslo[br]přes 150 číslic dlouhé. Nazveme ho P1.

0:02:09.880,0:02:15.250
Potom vygeneruje druhé náhodné prvočíslo[br]o zhruba stejné velikosti. Říkejme mu P2.

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

0:02:18.410,0:02:23.660
aby dostala složené číslo N,[br]které má více než 300 číslic.

0:02:23.660,0:02:26.720
Tento krok s násobením[br]zabere méně než sekundu.

0:02:26.720,0:02:30.030
Zvládli byste to provést dokonce[br]i ve svém webovém prohlížeči.

0:02:30.030,0:02:35.590
Potom vezme prvočíselný rozklad N,[br](P1 krát P2), a schová ho.

0:02:35.590,0:02:38.340
I kdyby se teď N dostalo[br]ke komukoliv jinému,

0:02:38.340,0:02:43.020
tak by mu trvalo roky, než by na počítači[br]nalezl prvočíslený rozklad N.

0:02:43.020,0:02:44.380
Krok 2:

0:02:44.380,0:02:50.150
Cocks potřeboval nalézt funkci, která závisí[br]na znalosti prvočíselného rozkladu N.

0:02:50.150,0:02:53.210
Kvůli tomu se podíval[br]do práce z roku 1760,

0:02:53.210,0:02:56.960
jejímž autorem byl švýcarský[br]matematik Leonhard Euler.