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

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

Решение сравнения находится за арифметических операций.

Можно также сказать, что решение находится за арифметических операций, где q — наибольший простой делитель p-1.

Если все простые делители q_i не превосходят то алгоритм Полига-Хеллмана является полиномиальным и имеет сложность , где c_1,2 — некоторые положительные постоянные.

Применение

Как уже было сказано, алгоритм Полига-Хеллмана крайне эффективен, если p-1 раскладывается на небольшие простые множители. Например, для чисел вида и т. д. Если же у p-1 есть большой простой делитель то алгоритм имеет экспоненциальную сложность. Это очень важно учитывать при выборе параметров криптографических схем.

Замечание

Для применения алгоритма Полига-Хеллмана необходимо знать разложение p-1 на множители. В общем случае задача факторизации — достаточно трудоёмкая, однако если делители числа — небольшие, то это число можно быстро разложить на множители даже методом последовательного деления. Таким образом, в том случае, когда эффективен алгоритм Полига-Хеллмана, необходимость факторизации не усложняет задачу.