Алгоритм Полига-Хеллмана: дискретный логарифм по частям

Алгоритм Полига-Хеллмана - это метод вычисления дискретного логарифма в конечной циклической группе, чей порядок раскладывается только на малые простые числа. Идея в том, чтобы не штурмовать большую задачу целиком, а разбить её на несколько маленьких подзадач по каждому простому делителю порядка, решить их по отдельности и собрать ответ китайской теоремой об остатках. Метод опубликовали Стивен Полиг и Мартин Хеллман в 1978 году, и именно он объясняет, почему в криптографии нельзя брать группу с «гладким» порядком: если порядок гладкий, дискретный логарифм считается быстро, и вся стойкость рушится. Ниже разбираем устройство алгоритма по шагам, его сложность и связь с выбором параметров - а собрать конкретный пример с числами можно в конструкторе сразу под введением.

Что вычисляет алгоритм Полига-Хеллмана

Задача дискретного логарифма формулируется так: дана циклическая группа $G$ порядка $n$, её образующая $g$ и элемент $h = g^x$. Нужно найти показатель $x$. В мультипликативной группе вычетов это значит: по известным $g$, $h$ и модулю $p$ найти такое $x$, что $g^x \equiv h \pmod p$.

Прямой перебор показателей стоит порядка $n$ операций, а универсальные методы вроде «больших и малых шагов» или $\rho$-метода Полларда - порядка $\sqrt{n}$. Алгоритм Полига-Хеллмана идёт другим путём: он использует структуру самого числа $n$. Если порядок группы

$n = \prod_{i} p_i^{e_i}$

раскладывается на простые $p_i$, то вместо одной задачи размера $n$ мы решаем по одной подзадаче в каждой подгруппе порядка $p_i^{e_i}$ - а они маленькие, когда простые $p_i$ малы.

Рассчитать для своей задачи

Почему важна гладкость порядка группы

Число называют гладким, если все его простые делители не превосходят некоторой небольшой границы. Гладкость порядка - это ровно то условие, при котором алгоритм Полига-Хеллмана работает быстро. Чем крупнее самый большой простой делитель $p_{\max}$ порядка $n$, тем тяжелее самая дорогая подзадача, потому что внутри подгруппы порядка $p_{\max}$ всё равно приходится решать дискретный логарифм размера $p_{\max}$.

Отсюда практический вывод: безопасность протоколов на дискретном логарифме (как в алгоритме Диффи-Хеллмана) требует, чтобы порядок группы делился на хотя бы одно большое простое число. Поэтому в стандартах берут «безопасные простые» вида $p = 2q + 1$, где $q$ тоже простое: тогда порядок $p - 1 = 2q$ имеет огромный делитель $q$, и Полиг-Хеллман упирается в подзадачу размера $q$, которую решить уже невозможно.

Шаг первый: разложение порядка и подгруппы

Пусть мы работаем в группе порядка $n$, и оно разложено: $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$. Идея алгоритма - найти не сам $x$, а его остатки $x \bmod p_i^{e_i}$ по каждому простому множителю, после чего восстановить $x$ по модулю $n$ через китайскую теорему об остатках.

Чтобы спроецировать задачу в подгруппу порядка $p_i^{e_i}$, обе части равенства $g^x = h$ возводят в степень $n / p_i^{e_i}$:

$\left(g^{\,n/p_i^{e_i}}\right)^{x} = h^{\,n/p_i^{e_i}}.$

Элемент $g_i = g^{\,n/p_i^{e_i}}$ имеет порядок ровно $p_i^{e_i}$, а $h_i = h^{\,n/p_i^{e_i}}$ лежит в порождённой им подгруппе. В этой подгруппе и ищется $x_i \equiv x \pmod{p_i^{e_i}}$ - задача того же типа, но крошечного размера.

Шаг второй: дискретный логарифм в подгруппе порядка p

Когда показатель простой ($e_i = 1$), подзадача - найти $x_i$ из равенства $g_i^{x_i} = h_i$ в группе порядка $p_i$. Здесь $x_i \in \{0, 1, \dots, p_i - 1\}$, и его можно найти простым перебором за $p_i$ шагов или методом «больших и малых шагов» за $\sqrt{p_i}$. Когда $p_i$ мало (десятки или сотни), это мгновенно.

Разберём это на учебном примере. Пусть $p = 29$, тогда порядок группы $\mathbb{Z}_{29}^*$ равен $n = 28 = 2^2 \cdot 7$. Возьмём образующую $g = 2$ и элемент $h = 2^x$. Чтобы найти $x \bmod 7$, обе части возводят в степень $n / 7 = 4$: получаем $g_7 = g^4$ порядка $7$ и $h_7 = h^4$, после чего перебором по семи значениям находят остаток. Аналогично, проекция в степень $n / 4 = 7$ даёт подзадачу в подгруппе порядка $4 = 2^2$. Два маленьких остатка склеиваются в $x \bmod 28$. Перебирать все $28$ показателей не пришлось ни разу - каждый шаг затрагивал лишь горстку значений.

Для степеней $e_i > 1$ применяют поразрядное «поднятие»: сначала находят $x_i \bmod p_i$, затем $x_i \bmod p_i^2$ и так далее, на каждом шаге решая задачу в группе порядка $p_i$. Записывая $x_i$ в системе счисления по основанию $p_i$,

$x_i = c_0 + c_1 p_i + c_2 p_i^2 + \dots + c_{e_i - 1} p_i^{\,e_i - 1},$

цифры $c_0, c_1, \dots$ восстанавливают по очереди, каждый раз отделяя уже найденную часть. Это превращает подзадачу размера $p_i^{e_i}$ в $e_i$ подзадач размера $p_i$.

Рассчитать для своей задачи

Шаг третий: сборка ответа китайской теоремой об остатках

После того как для каждого простого множителя найден остаток $x_i \equiv x \pmod{p_i^{e_i}}$, остаётся склеить их в единственное значение $x \bmod n$. Поскольку множители $p_i^{e_i}$ попарно взаимно просты, система

$x \equiv x_1 \pmod{p_1^{e_1}}, \quad x \equiv x_2 \pmod{p_2^{e_2}}, \quad \dots$

имеет ровно одно решение по модулю $n$ по китайской теореме об остатках. Это решение и есть искомый дискретный логарифм $x$. Проверить его легко: достаточно убедиться, что $g^x \equiv h \pmod p$.

Сложность алгоритма

Главное достоинство Полига-Хеллмана - сложность, определяемая не размером группы, а её крупнейшим простым делителем. Если применять метод «больших и малых шагов» внутри каждой подгруппы, общая стоимость составляет порядка

$O\!\left(\sum_i e_i \left(\log n + \sqrt{p_i}\right)\right)$

групповых операций. Доминирует слагаемое с самым большим $p_i$: фактически алгоритм работает за $O(\sqrt{p_{\max}})$ с точностью до логарифмических множителей.

Поэтому для группы порядка $n \approx 10^{40}$ с гладким разложением (все делители меньше, скажем, $10^6$) задача решается практически мгновенно, тогда как для группы того же размера с делителем $q \approx 10^{40}$ метод бесполезен - он упирается в $\sqrt{q}$.

Частые ошибки

• Путают модуль и порядок. Дискретный логарифм считают в группе порядка $n = p - 1$ (для $\mathbb{Z}_p^*$), а не по модулю $p$. Раскладывать на множители нужно именно $n$, а не сам модуль $p$.
• Берут не ту проекцию. Чтобы загнать задачу в подгруппу порядка $p_i^{e_i}$, возводят в степень $n / p_i^{e_i}$, а не $n / p_i$ при $e_i > 1$ - иначе теряется часть информации о показателе.
• Забывают про поразрядное поднятие. При $e_i > 1$ нельзя решить подзадачу одним разом: нужно последовательно находить цифры $c_0, c_1, \dots$ по основанию $p_i$.
• Считают, что большой модуль = стойкость. Если $p - 1$ гладкое, размер $p$ не спасает: Полиг-Хеллман решит логарифм за секунды.
• Ошибаются в сборке CRT. Остатки берут по модулям $p_i^{e_i}$ (со степенями), а не по простым $p_i$, иначе китайская теорема даёт неверный ответ.

FAQ

Когда алгоритм Полига-Хеллмана неэффективен? Когда порядок группы делится на большое простое число $q$: самая дорогая подзадача имеет размер $q$, и её приходится решать за $\sqrt{q}$ операций. Для криптографически больших $q$ (сотни бит) это вычислительно невозможно, поэтому защищённые параметры специально подбирают с большим простым делителем порядка.

Чем Полиг-Хеллман отличается от метода Полларда? $\rho$-метод Полларда решает дискретный логарифм за $\sqrt{n}$ без знания разложения порядка. Полиг-Хеллман эффективнее, когда порядок гладкий: он сводит задачу к подзадачам по делителям и тратит лишь $\sqrt{p_{\max}}$. На практике методы комбинируют: Полиг-Хеллман разбивает задачу, а внутри каждой подгруппы шаги делает Поллард.

Зачем нужна китайская теорема об остатках в этом алгоритме? Она склеивает остатки $x \bmod p_i^{e_i}$, найденные по отдельным простым множителям, в единственный показатель $x \bmod n$. Без неё мы получили бы набор независимых остатков, но не само значение дискретного логарифма.

Коротко

Алгоритм Полига-Хеллмана решает задачу дискретного логарифма, раскладывая порядок группы на простые множители, проецируя задачу в каждую подгруппу порядка $p_i^{e_i}$, решая там маленький логарифм (с поразрядным поднятием для степеней) и собирая ответ китайской теоремой об остатках. Его сложность определяется крупнейшим простым делителем порядка, поэтому гладкость порядка делает дискретный логарифм лёгким - а стойкие протоколы требуют группы с большим простым делителем.