-
Нам потрібна числова процедура,
проста в одному напрямі
-
і складна в іншому.
-
Це приводить нас до модульної
(годинникової) арифметики
-
Наприклад, щоб знайти остачу від ділення 46 на
12, ми можемо взяти мотузку довжиною 46
-
і обернути її навколо 12-ти поділок
годинника, який називається модулістом,
-
і там, де закінчиться
мотузка, буде відповідь
-
Отже, ми кажемо, що остача від ділення
46 на 12 дорівнює 10.
-
Легко. Тепер, щоб це запрацювало, візьмемо як
модуліст просте число, наприклад, 17
-
Потім ми шукаємо примітивний корінь 17-ти,
який рівний 3
-
Що має таку важливу властивість:
якщо підносити 3 до різних степенів
-
розв'язки рівномірно поширюватимуться
по годиннику
-
Число 3 називається генератором.
Якщо ми піднесемо 3 у будь-яку степінь х,
-
то розв'язок буде, з рівною вірогідністю,
цілим числом між 1 і 17.
-
Тепер зворотня операція - складна.
-
Наприклад, дано 12, знайдіть
степінь, у яку треба піднести 3.
-
Це називається задача
дискретного логарифму.
-
І тепер у нас є наша одностороння функція
-
Легка у здійсненні, але складна
у протилежному нарпрямі дії.
-
Дано 12 і маємо використати метод проб і помилок,
щоб знайти відповідні показники.
-
Наскільки це складно?
-
З маленькими числами це легко, але якщо ми використаємо як модуліст просте число довжиною у сотні цифр,
-
вирішити це стає неможливим.
-
Навіть якщо б ви мали доступ до усієї обчислювальної потужності на Землі, перебирання усіх варіантів
-
зайняло б тисячі років.
-
Отже, сила односторонньої функції ґрунтується на часі, необхідному щоб виконати зворотній процес.
-
Переклад на українську: Роман Берла, рев’ювер Оксана Кузьменко, благодійний фонд “Magneticone.org”
