Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Полига Хеллмана

Алгоритм Полига — Хеллмана — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным.
Важной особенностью этого метода является то, что для простых чисел специального вида, можно находить дискретный логарифм за полиномиальное время.

История

Данный алгоритм был впервые публично описан американскими математиками Роланом Силвером, Стефаном Полигом и Мартином Хеллманом в 1978 году в статье «An improved algorithm for computing logarithms over GF and its cryptographic significance».

На самом деле, честь открытия этого алгоритма принадлежит советским криптоаналитикам А.О.Гельфонду и В.И.Нечаеву. В 1972 году Василий Ильич Нечаев установил, что среди детерминированных алгоритмов нет лучших. Поскольку задача отыскания оптимального алгоритма вычисления дискретного логарифма принадлежит к числу важнейших в криптографии, не удивительно, что до последних лет истинные первооткрыватели этого метода находились "в тени".
До сих пор продолжаются исследования в отыскании других алгоритмов вычисления дискретных логарифмов и уже предложен целый ряд таких алгоритмов, использующих вероятностные соображения.