20-10-2023
Алгоритм Полига — Хеллмана (также называемый алгоритм Силвера — Полига — Хеллмана) — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным.
Содержание |
Данный алгоритм был впервые описан американскими математиками Роланом Силвером (Roland Silver), Стефаном Полигом (Stephan Pohlig) и Мартином Хеллманом (Martin Hellman) в 1978 году в статье «An improved algorithm for computing logarithms over GF(p) and its cryptographic significance». Важной особенностью этого метода является то, что для простых чисел специального вида, можно находить дискретный логарифм за полиномиальное время.
Пусть задано сравнение
| ((1)) |
и известно разложение на простые множители:
| ({{{2}}}) |
Необходимо найти натуральное число x, удовлетворяющее сравнению (1). Заметим, что на практике обычно рассматривается случай, когда a — первообразный корень по модулю p. В этом случае сравнение (1) имеет решение при любом b, взаимно простом с p.
Суть алгоритма в том, что достаточно найти x по модулям для всех i, а затем решение исходного сравнения можно найти с помощью китайской теоремы об остатках. Чтобы найти x по каждому из таких модулей, нужно решить сравнение:
| ((2)) |
Данное сравнение решается за полиномиальное время в случае, если — небольшое (то есть, не превосходит , где c — некоторая константа).
Шаг 1 (составление таблицы). Составить таблицу значений , где Шаг 2 (вычисление ). Для i от 1 до s: Пусть где Тогда из (1) следует, что С помощью таблицы, составленной на шаге 1, находим Для j от 1 до Рассматриваем сравнение Решение опять же находится по таблице Конец цикла по i Конец цикла по j Шаг 3 (нахождение ответа). Найдя для всех i, находим по китайской теореме об остатках.
Решение сравнения (1) находится за арифметических операций (см. [1]).
Можно также сказать, что решение находится за арифметических операций, где q — наибольший простой делитель p-1 (см. [3]).
Если все простые делители не превосходят то алгоритм Полига-Хеллмана является полиномиальным и имеет сложность , где c1,2 — некоторые положительные постоянные.
Как уже было сказано, алгоритм Полига-Хеллмана крайне эффективен, если p-1 раскладывается на небольшие простые множители. Например, для чисел вида и т. д. Если же у p-1 есть большой простой делитель то алгоритм имеет экспоненциальную сложность. Это очень важно учитывать при выборе параметров криптографических схем.
Для применения алгоритма Полига-Хеллмана необходимо знать разложение p-1 на множители. В общем случае задача факторизации — достаточно трудоёмкая, однако если делители числа — небольшие (в том смысле, о котором сказано выше), то это число можно быстро разложить на множители даже методом последовательного деления. Таким образом, в том случае, когда эффективен алгоритм Полига-Хеллмана, необходимость факторизации не усложняет задачу.
Алгоритм Полига — Хеллмана.