Дискретные логарифмы в конечном поле
В качестве другой однонаправленной функции в криптографии часто используется возведение в степень по модулю. Легко вычислить:
ax mod n
Задачей, обратной возведению в степень по модулю, является поиск дискретного логарифма. А это уже нелегкая задача:
Найти x, для которого ax ? b (mod n).
Например:
Если 3x ? 15 mod 17, то x = 6
Решения существуют не для всех дискретных логарифмов (помните, речь идет только о целочисленных решениях). Легко заметить, что следующее уравнение не имеет решений
3x ?7 (mod 13)
Еще сложнее решать эту задачу для 1024-битовых чисел.