0:00:00.326,0:00:03.761
Ponad 2000 lat temu Euklides wykazał,[br]że każda liczba

0:00:03.860,0:00:08.811
ma dokładnie jeden rozkład na czynniki[br]pierwsze. Uznajmy go za tajny klucz.

0:00:08.911,0:00:13.780
Okazuje się, że rozkład na czynniki[br]pierwsze to trudny problem.

0:00:14.605,0:00:17.879
Wyjaśnijmy, co rozumiemy[br]przez „łatwy” i „trudny”,

0:00:17.979,0:00:21.153
wprowadzając pojęcie[br]tzw. złożoności czasowej.

0:00:21.253,0:00:23.382
Każdy z nas mnożył liczby

0:00:23.482,0:00:27.477
i ma własne sposoby,[br]żeby to przyspieszyć.

0:00:27.577,0:00:30.038
Odpowiednio zaprogramowany komputer

0:00:30.138,0:00:33.343
będzie mnożył liczby[br]znacznie szybciej niż człowiek.

0:00:33.443,0:00:36.942
Na wykresie przedstawiono[br]czas potrzebny komputerowi

0:00:37.042,0:00:39.032
do pomnożenia dwu liczb.

0:00:39.132,0:00:41.819
Czas potrzebny[br]do znalezienia odpowiedzi

0:00:41.919,0:00:44.675
wydłuża się wraz ze wzrostem liczb.

0:00:44.775,0:00:46.672
Zauważcie, że czas obliczeniowy

0:00:46.772,0:00:50.642
jest znacznie krótszy od sekundy[br]nawet przy dużych liczbach.

0:00:50.742,0:00:53.083
Dlatego wykonanie jest „łatwe”.

0:00:53.183,0:00:56.076
Porównajmy to z rozkładem[br]na czynniki pierwsze.

0:00:56.176,0:01:00.186
Gdyby ktoś kazał wam[br]rozłożyć liczbę 589,

0:01:00.286,0:01:03.042
od razu byście wiedzieli,[br]że będzie trudno.

0:01:03.142,0:01:05.153
Niezależnie od obranej strategii,

0:01:05.253,0:01:08.127
metodą prób i błędów[br]będziecie szukać liczby,

0:01:08.227,0:01:10.704
przez którą[br]bez reszty dzieli się 589.

0:01:10.804,0:01:16.121
Pomęczycie się trochę i ustalicie,[br]że ten rozkład to 19 razy 31.

0:01:17.090,0:01:22.941
Gdyby kazano wam rozłożyć[br]na czynniki pierwsze liczbę 437231,

0:01:23.041,0:01:26.412
zapewne poddalibyście się[br]i zaprzęgli do pomocy komputer.

0:01:26.512,0:01:28.739
Uda się to przy małych wartościach,

0:01:28.839,0:01:32.531
ale gdy każemy komputerowi[br]rozkładać coraz większe liczby,

0:01:32.631,0:01:34.110
wystąpi efekt lawiny.

0:01:35.062,0:01:37.384
Czas potrzebny do wykonania obliczeń

0:01:37.484,0:01:41.122
będzie rósł bardzo szybko,[br]bo jest więcej etapów.

0:01:41.222,0:01:45.593
W miarę wzrostu liczb, komputer[br]będzie potrzebował minut, godzin…

0:01:45.693,0:01:47.984
aż wreszcie - setek lub tysięcy lat,

0:01:48.084,0:01:50.457
by przeprowadzić[br]rozkład ogromnych liczb.

0:01:50.557,0:01:53.452
Dlatego zadanie nazwiemy trudnym,

0:01:53.552,0:01:57.283
z powodu czasu potrzebnego[br]na znalezienie rozwiązania.

0:01:57.383,0:02:01.811
Rozkładu na czynniki pierwsze[br]użył Cocks w rozwiązaniu zapadkowym.

0:02:01.911,0:02:06.246
Krok pierwszy: że Alicja losowo[br]wygenerowała liczbę pierwszą

0:02:06.346,0:02:09.683
o długości ponad 150 cyfr.[br]Nazwijmy ją P1.

0:02:09.782,0:02:15.100
Wygenerowała kolejną liczbę pierwszą,[br]podobnej wielkości; nazwiemy ją P2.

0:02:15.200,0:02:18.089
Teraz mnoży te liczby pierwsze

0:02:18.189,0:02:20.503
i uzyskuje liczbę złożoną N,

0:02:20.603,0:02:23.429
mającą ponad 300 cyfr.

0:02:23.529,0:02:26.608
Mnożenie potrwa mniej niż sekundę;

0:02:26.708,0:02:29.722
poradzi sobie z nim[br]nawet przeglądarka internetowa.

0:02:29.822,0:02:32.369
Potem Alicja[br]bierze czynniki pierwsze N,

0:02:32.469,0:02:35.411
czyli P1 razy P2, i ukrywa je.

0:02:35.511,0:02:38.058
Gdyby podała komuś N,

0:02:38.158,0:02:41.610
przez wiele lat[br]komputerowo szukałby rozwiązania.

0:02:42.980,0:02:46.161
Krok drugi:[br]Cocks musiał znaleźć funkcję,

0:02:46.261,0:02:49.993
która zależy od tego, czy znamy[br]rozkład N na czynniki pierwsze.

0:02:50.093,0:02:53.121
Sięgnął więc do opublikowanej[br]w 1760 roku pracy

0:02:53.221,0:02:56.751
szwajcarskiego matematyka[br]Leonharda Eulera.