USSR (29.03.2016 08:51, просмотров: 1) ответил Крок на Насколько быстрый?
Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом.
Классическими криптографическими схемами на её основе являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции. Последняя вычисляется достаточно эффективно, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.
Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Теоретически доказано, что с их помощью дискретный логарифм можно вычислить за полиномиальное время[2]. В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе.