Модульная экспонента

Возведение очень большого числа A в очень большую степень x (), то есть вычисление , где модуль M тоже большое число, является также несложной задачей для ЭВМ. Однако решение обратной задачи – нахождения степени x по известным у, A, M является задачей дискретного логарифмирования, , которая практически не разрешима за приемлемое время на современных ЭВМ (эффективного алгоритма вычисления дискретного логарифма пока не найдено). Поэтому модульную экспоненту можно считать также однонаправленной функцией.

Рассмотрим простую интерпретацию сказанного. Пусть задано: А=2, х=2, М=4. Тогда = 0. Пусть А=2, х=3, М=4. Тогда = 0. Отсюда видно, что по у вычислить х можно только полным перебором всех вариантов даже, если известны А и М.

Кроме однонаправленных функций важное значение для криптографии с открытым ключом имеют однонаправленные функции с «потайным входом», эффективное обращение которых возможно, если известен секретный «потайной ход» (секретное число или другая информация, ассоциируемая с функцией).