1
00:00:01,332 --> 00:00:05,475
Нам потрібна числова процедура,
проста в одному напрямі

2
00:00:05,475 --> 00:00:07,401
і складна в іншому.

3
00:00:07,401 --> 00:00:12,689
Це приводить нас до модульної
(годинникової) арифметики

4
00:00:12,689 --> 00:00:20,120
Наприклад, щоб знайти остачу від ділення 46 на 
12, ми можемо взяти мотузку довжиною 46

5
00:00:20,120 --> 00:00:24,510
і обернути її навколо 12-ти поділок 
годинника, який називається модулістом,

6
00:00:24,510 --> 00:00:28,325
і там, де закінчиться 
мотузка, буде відповідь

7
00:00:28,325 --> 00:00:32,877
Отже, ми кажемо, що остача від ділення
46 на 12 дорівнює 10.

8
00:00:32,877 --> 00:00:38,985
Легко. Тепер, щоб це запрацювало, візьмемо як 
модуліст просте число, наприклад, 17

9
00:00:38,985 --> 00:00:44,085
Потім ми шукаємо примітивний корінь 17-ти, 
який рівний 3

10
00:00:44,085 --> 00:00:48,343
Що має таку важливу властивість:
якщо підносити 3 до різних степенів

11
00:00:48,343 --> 00:00:52,732
розв'язки рівномірно поширюватимуться
по годиннику

12
00:00:52,732 --> 00:01:00,102
Число 3 називається генератором.
Якщо ми піднесемо 3 у будь-яку степінь х,

13
00:01:00,102 --> 00:01:05,510
то розв'язок буде, з рівною вірогідністю,
цілим числом між 1 і 17.

14
00:01:05,510 --> 00:01:08,858
Тепер зворотня операція - складна.

15
00:01:08,858 --> 00:01:14,038
Наприклад, дано 12, знайдіть
степінь, у яку треба піднести 3.

16
00:01:14,038 --> 00:01:17,736
Це називається задача
дискретного логарифму.

17
00:01:17,736 --> 00:01:20,424
І тепер у нас є наша одностороння функція

18
00:01:20,424 --> 00:01:23,690
Легка у здійсненні, але складна
у протилежному нарпрямі дії.

19
00:01:23,690 --> 00:01:30,223
Дано 12 і маємо використати метод проб і помилок, 
щоб знайти відповідні показники.

20
00:01:30,223 --> 00:01:32,612
Наскільки це складно?

21
00:01:32,612 --> 00:01:39,073
З маленькими числами це легко, але якщо ми використаємо як модуліст просте число довжиною у сотні цифр,

22
00:01:39,073 --> 00:01:42,086
вирішити це стає неможливим.

23
00:01:42,086 --> 00:01:47,315
Навіть якщо б ви мали доступ до усієї обчислювальної потужності на Землі, перебирання усіх варіантів

24
00:01:47,315 --> 00:01:49,751
зайняло б тисячі років.

25
00:01:49,751 --> 00:01:54,535
Отже, сила односторонньої функції ґрунтується на часі, необхідному щоб виконати зворотній процес.

26
00:01:54,535 --> 00:01:55,194
Переклад на українську: Роман Берла, рев’ювер Оксана Кузьменко, благодійний фонд “Magneticone.org”