Задача дискретного логарифмирования применяется во многих алгоритмах криптографии с открытым ключом. Предложенная в 1976 году У. Диффи (W. Diffie) и М. Хеллманом (М. Hellman) для установления сеансового ключа, эта задача послужила основой для создания протоколов шифрования и цифровой подписи, доказательств с нулевым разглашением и других криптографических протоколов.
Следует отметить, что в криптографии эта задача возникла еще в 1950;х годах, когда вместо роторных машин стали использоваться регистры сдвига, и нужно было определить место конкретного элемента в данной последовательности сдвигов.
Пусть G — мультипликативная абелева группа,. Задачей дискретного логарифмирования в группе G называется задача нахождения решения уравнения .
Ее решение х называется дискретным логарифмом элемента b по основанию а и обозначается, если основание фиксировано и если решение существует;
если .
Рассмотрим уравнение:
(1).
в группе, где р — простое число. Пусть порядок равен. Тогда уравнение (1) разрешимо, и решение х является элементом. Безопасность соответствующих криптосистем основана на том, что, зная числа а, х, р вычислить легко (например, алгоритмом В-арного возведения в степень), а решить задачу дискретного логарифмирования трудно.
Рассмотрим некоторые методы решения этой задачи.
