1
00:00:00,050 --> 00:00:02,790
Před 2000 lety Eukleides dokázal,

2
00:00:02,790 --> 00:00:06,290
že každé číslo má jedinečný
prvočíselný rozklad,

3
00:00:06,290 --> 00:00:08,980
který si můžeme představit
jako tajný klíč.

4
00:00:08,980 --> 00:00:14,510
Ukazuje se, že prvočíselný rozklad
je složitý problém.

5
00:00:14,510 --> 00:00:18,000
Vyjasníme si, co myslíme pojmy
"snadný" a "složitý"

6
00:00:18,000 --> 00:00:21,220
pomocí tzv. časové složitosti algoritmu.

7
00:00:21,220 --> 00:00:23,180
Všichni umíme násobit čísla

8
00:00:23,180 --> 00:00:27,550
a každý z nás pro urychlení
používá svůj vlastní postup.

9
00:00:27,550 --> 00:00:30,010
Pokud naprogramujeme počítač,
aby násobil čísla,

10
00:00:30,010 --> 00:00:33,460
tak to může provádět
mnohem rychleji než člověk.

11
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.

12
00:00:39,080 --> 00:00:44,770
Potřebný čas pro získání výsledku
se zvyšuje s rostoucími čísly.

13
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.

14
00:00:50,700 --> 00:00:53,480
Proto je snadné provádět násobení.

15
00:00:53,480 --> 00:00:56,140
Teď to porovnejte
s prvočíselným rozkladem.

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

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

18
00:01:03,180 --> 00:01:06,790
Bez ohledu na vaši strategii to bude
vyžadovat použití metody pokus-omyl,

19
00:01:06,820 --> 00:01:10,760
dokud nenajdete číslo,
kterým lze 589 dělit.

20
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).

21
00:01:17,020 --> 00:01:22,980
Pokud byste měli najít
prvočíselný rozklad čísla 437231,

22
00:01:22,980 --> 00:01:26,510
tak byste to pravděpodobně
vzdali a vzali si na pomoc počítač.

23
00:01:26,510 --> 00:01:28,340
Tohle funguje dobře pro malá čísla,

24
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".

25
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ů.

26
00:01:41,190 --> 00:01:44,480
A jak čísla rostou, tak počítač
potřebuje minuty a pak i hodiny.

27
00:01:44,480 --> 00:01:50,490
Nakonec bude potřebovat stovky nebo tisíce let
pro prvočíselný rozklad obrovských čísel.

28
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í.

29
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.

30
00:02:01,780 --> 00:02:03,170
Krok 1:

31
00:02:03,170 --> 00:02:09,880
Alice náhodně vygeneruje prvočíslo
přes 150 číslic dlouhé. Nazveme ho P1.

32
00:02:09,880 --> 00:02:15,250
Potom vygeneruje druhé náhodné prvočíslo
o zhruba stejné velikosti. Říkejme mu P2.

33
00:02:15,250 --> 00:02:18,410
Pak vynásobí tyto dvě prvočísla,

34
00:02:18,410 --> 00:02:23,660
aby dostala složené číslo N,
které má více než 300 číslic.

35
00:02:23,660 --> 00:02:26,720
Tento krok s násobením
zabere méně než sekundu.

36
00:02:26,720 --> 00:02:30,030
Zvládli byste to provést dokonce
i ve svém webovém prohlížeči.

37
00:02:30,030 --> 00:02:35,590
Potom vezme prvočíselný rozklad N,
(P1 krát P2), a schová ho.

38
00:02:35,590 --> 00:02:38,340
I kdyby se teď N dostalo
ke komukoliv jinému,

39
00:02:38,340 --> 00:02:43,020
tak by mu trvalo roky, než by na počítači
nalezl prvočíslený rozklad N.

40
00:02:43,020 --> 00:02:44,380
Krok 2:

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

42
00:02:50,150 --> 00:02:53,210
Kvůli tomu se podíval
do práce z roku 1760,

43
00:02:53,210 --> 00:02:56,960
jejímž autorem byl švýcarský
matematik Leonhard Euler.