[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.05,0:00:02.79,Default,,0000,0000,0000,,Před 2000 lety Eukleides dokázal,
Dialogue: 0,0:00:02.79,0:00:06.29,Default,,0000,0000,0000,,že každé číslo má jedinečný\Nprvočíselný rozklad,
Dialogue: 0,0:00:06.29,0:00:08.98,Default,,0000,0000,0000,,který si můžeme představit\Njako tajný klíč.
Dialogue: 0,0:00:08.98,0:00:14.51,Default,,0000,0000,0000,,Ukazuje se, že prvočíselný rozklad\Nje složitý problém.
Dialogue: 0,0:00:14.51,0:00:18.00,Default,,0000,0000,0000,,Vyjasníme si, co myslíme pojmy\N"snadný" a "složitý"
Dialogue: 0,0:00:18.00,0:00:21.22,Default,,0000,0000,0000,,pomocí tzv. časové složitosti algoritmu.
Dialogue: 0,0:00:21.22,0:00:23.18,Default,,0000,0000,0000,,Všichni umíme násobit čísla
Dialogue: 0,0:00:23.18,0:00:27.55,Default,,0000,0000,0000,,a každý z nás pro urychlení\Npoužívá svůj vlastní postup.
Dialogue: 0,0:00:27.55,0:00:30.01,Default,,0000,0000,0000,,Pokud naprogramujeme počítač,\Naby násobil čísla,
Dialogue: 0,0:00:30.01,0:00:33.46,Default,,0000,0000,0000,,tak to může provádět\Nmnohem rychleji než člověk.
Dialogue: 0,0:00:33.46,0:00:39.08,Default,,0000,0000,0000,,Zde je graf, který ukazuje kolik času potřebuje\Npočítač, aby vypočetl násobek dvou čísel.
Dialogue: 0,0:00:39.08,0:00:44.77,Default,,0000,0000,0000,,Potřebný čas pro získání výsledku\Nse zvyšuje s rostoucími čísly.
Dialogue: 0,0:00:44.77,0:00:50.70,Default,,0000,0000,0000,,Všimněte si, že čas pro výpočet se drží\Npod 1s i s poměrně vysokými čísly.
Dialogue: 0,0:00:50.70,0:00:53.48,Default,,0000,0000,0000,,Proto je snadné provádět násobení.
Dialogue: 0,0:00:53.48,0:00:56.14,Default,,0000,0000,0000,,Teď to porovnejte\Ns prvočíselným rozkladem.
Dialogue: 0,0:00:56.14,0:01:00.22,Default,,0000,0000,0000,,Pokud by vám někdo řekl,\Nabyste našli prvočíselný rozklad čísla 589,
Dialogue: 0,0:01:00.22,0:01:03.18,Default,,0000,0000,0000,,tak si hned všimnete,\Nže se příklad zdá být těžší.
Dialogue: 0,0:01:03.18,0:01:06.79,Default,,0000,0000,0000,,Bez ohledu na vaši strategii to bude\Nvyžadovat použití metody pokus-omyl,
Dialogue: 0,0:01:06.82,0:01:10.76,Default,,0000,0000,0000,,dokud nenajdete číslo,\Nkterým lze 589 dělit.
Dialogue: 0,0:01:10.76,0:01:17.02,Default,,0000,0000,0000,,Až s tím dozápasíte, tak zjistíte,\Nže prvočíselný rozklad je (19 krát 31).
Dialogue: 0,0:01:17.02,0:01:22.98,Default,,0000,0000,0000,,Pokud byste měli najít\Nprvočíselný rozklad čísla 437231,
Dialogue: 0,0:01:22.98,0:01:26.51,Default,,0000,0000,0000,,tak byste to pravděpodobně\Nvzdali a vzali si na pomoc počítač.
Dialogue: 0,0:01:26.51,0:01:28.34,Default,,0000,0000,0000,,Tohle funguje dobře pro malá čísla,
Dialogue: 0,0:01:28.34,0:01:35.02,Default,,0000,0000,0000,,ale pokud zkusíme rozkládat větší čísla,\Ntak výsledek nebude spočítán "v rozumném čase".
Dialogue: 0,0:01:35.02,0:01:41.19,Default,,0000,0000,0000,,Čas potřebný k výpočtu rapidně\Nroste s přírůstkem potřebných kroků.
Dialogue: 0,0:01:41.19,0:01:44.48,Default,,0000,0000,0000,,A jak čísla rostou, tak počítač\Npotřebuje minuty a pak i hodiny.
Dialogue: 0,0:01:44.48,0:01:50.49,Default,,0000,0000,0000,,Nakonec bude potřebovat stovky nebo tisíce let\Npro prvočíselný rozklad obrovských čísel.
Dialogue: 0,0:01:50.49,0:01:57.51,Default,,0000,0000,0000,,Proto říkáme, že je to těžký problém.\NKvůli nárůstu času potřebného k řešení.
Dialogue: 0,0:01:57.51,0:02:01.78,Default,,0000,0000,0000,,Takže prvočíselný rozklad je to, co Cocks použil\Npro vytvoření řešení se zadními vrátky.
Dialogue: 0,0:02:01.78,0:02:03.17,Default,,0000,0000,0000,,Krok 1:
Dialogue: 0,0:02:03.17,0:02:09.88,Default,,0000,0000,0000,,Alice náhodně vygeneruje prvočíslo\Npřes 150 číslic dlouhé. Nazveme ho P1.
Dialogue: 0,0:02:09.88,0:02:15.25,Default,,0000,0000,0000,,Potom vygeneruje druhé náhodné prvočíslo\No zhruba stejné velikosti. Říkejme mu P2.
Dialogue: 0,0:02:15.25,0:02:18.41,Default,,0000,0000,0000,,Pak vynásobí tyto dvě prvočísla,
Dialogue: 0,0:02:18.41,0:02:23.66,Default,,0000,0000,0000,,aby dostala složené číslo N,\Nkteré má více než 300 číslic.
Dialogue: 0,0:02:23.66,0:02:26.72,Default,,0000,0000,0000,,Tento krok s násobením\Nzabere méně než sekundu.
Dialogue: 0,0:02:26.72,0:02:30.03,Default,,0000,0000,0000,,Zvládli byste to provést dokonce\Ni ve svém webovém prohlížeči.
Dialogue: 0,0:02:30.03,0:02:35.59,Default,,0000,0000,0000,,Potom vezme prvočíselný rozklad N,\N(P1 krát P2), a schová ho.
Dialogue: 0,0:02:35.59,0:02:38.34,Default,,0000,0000,0000,,I kdyby se teď N dostalo\Nke komukoliv jinému,
Dialogue: 0,0:02:38.34,0:02:43.02,Default,,0000,0000,0000,,tak by mu trvalo roky, než by na počítači\Nnalezl prvočíslený rozklad N.
Dialogue: 0,0:02:43.02,0:02:44.38,Default,,0000,0000,0000,,Krok 2:
Dialogue: 0,0:02:44.38,0:02:50.15,Default,,0000,0000,0000,,Cocks potřeboval nalézt funkci, která závisí\Nna znalosti prvočíselného rozkladu N.
Dialogue: 0,0:02:50.15,0:02:53.21,Default,,0000,0000,0000,,Kvůli tomu se podíval\Ndo práce z roku 1760,
Dialogue: 0,0:02:53.21,0:02:56.96,Default,,0000,0000,0000,,jejímž autorem byl švýcarský\Nmatematik Leonhard Euler.