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