-
Нам нужна числовая процедура, которая легко выполняется в одном направлении
-
и гораздо труднее в обратном.
-
Это приводит нас к модульной арифметике, также известной как "арифметика часов" (или "остатков").
-
Например, для нахождения 46 по модулю 12 можно взять веревку длиной 46 единиц
-
и свернуть ее вокруг часов, которые называют модулем.
-
То место, где веревка заканчивается, и есть решение.
-
То есть 46 по модулю 12 эквивалентно 10-ти.
-
Все просто. Теперь для выполнения этого возьмем простой модуль. 17, к примеру.
-
Затем найдем первообразный корень 17-ти, в этом случае -- три.
-
Он имеет очень важное свойство при возведении в различные степени --
-
значения равномерно распределяются вокруг часов.
-
3 называют порождающим элементом или генератором. Если возвести 3 в любую степень x,
-
то результат равновероятно может оказаться любым числом от 1 до 16.
-
То есть обратная процедура довольно сложна.
-
Скажем, какая степень 3 даст в результате 12?
-
Это и есть задача вычисления дискретного логарифма.
-
И теперь у нас есть односторонняя функция.
-
Простая для прямого и сложная для обратного выполнения.
-
Для заданного числа 12 нам приходится прибегнуть к перебору многих ошибочных вариантов, чтобы найти нужный показатель степени.
-
Так насколько это сложно?
-
Ну, с небольшими значениями это просто, но если использован простой модуль длиной в сотни знаков,
-
задача становится практически неразрешимой.
-
Даже если есть доступ ко всем вычислительным мощностям Земли, перебор всех вариантов
-
может занять тысячи лет.
-
Таким образом, сила односторонней функции основана на времени, необходимом для обратного преобразования.
