Автор Неизвестен - Дискретное логарифмирование

больших-малых шагов.
Q
Если |G| = si=1 qiei , то для определения logg y потребуется выполнить
à s
!
X √
O
αi qi
i=1

групповых операций.
117

Пример 27.3. В первоначальном варианте своей схемы ЭльГамаль предлагал использовать в качестве g примитивный элемент F∗p , т. е. элемент порядка p − 1. Если p − 1 не имеет больших простых делителей, то с помощью метода
Поллига — Хеллмана можно достаточно эффективно находить личный ключ x = logg y. Поэтому требование наличия у p − 1 большого простого делителя q является весьма важным. Кроме этого, вместо примитивного элемента g
можно использовать элемент порядка q, поскольку сложность логарифмирования при таком переходе уменьшается
незначительно.
¤

27.4

λ-метод

λ-метод также был предложен Поллардом. Альтернативное название метода — метод кенгуру.
Идея. Пусть S ⊂ {0, 1, . . . , q − 1} и h : G → S — некоторая хэш-функция. Определим преобразование:
ϕ : G → G,

z 7→ zg h(z) .

Поставим в соответствие f граф, вершинами которого являются всевозможные элементы G; из каждой вершины z ∈ G выходит ровно одна дуга, которая заканчивается в f (z). Известно, что граф любого преобразования представляет собой набор связных компонент. В свою очередь, каждая связная компонента
представляет собой набор циклических вершин, к которым крепятся деревья.

Как и ρ-метод, λ-метод ориентирован на поиск коллизий в графе преобразования f . В отличие от ρметода, поиск коллизий ведется не только в циклических вершинах графа, но и в вершинах деревьев.
Шаги алгоритма.
1. Выберем u0 ∈ A, z0 = g u0 и построим последовательность
zt = ϕ(zt−1 ) = zt−1 g ut ,

ut = h(zt−1 ),

t = 1, . . . , T.

Запомним zT и сумму (u0 + . . . + uT ) mod q.
2. Выберем z0∗ = y = g v0 , где v0 — неизвестный дискретный логарифм. Построим последовательность
∗
∗
zt∗ = f (zt−1
) = zt−1
g vt ,

∗
vt = h(zt−1
),

t = 1, 2, . . . ,

?

и после определения очередного zt∗ будем проверять zt∗ = zT .
3. Если совпадение найдено, то
v0 + v1 + . . . + vt ≡ u0 + u1 + . . . + uT (mod q) ⇒ v0 = (u0 + u1 + . . . + uT − v1 − . . . − vt ) mod q.
Название алгоритма объясняется следующим образом: последовательность zt объявляется траекторией
прирученного кенгуру (мы знаем величины прыжков u0 , u1 , . . .), а последовательность zt∗ считается траекторией дикого кенгуру (мы не знаем величину первого прыжка v0 ).

118

√
Сложность. Для определения дискретного логарифма также требуется выполнить O( q) групповых операций.
Распараллеливание. Пусть для поиска дискретного логарифма используется не одно вычислительное
устройство (машина Тьюринга) а m устройств. Во сколько раз мы можем уменьшить время поиска?
√
Оказывается, что для λ-метода время можно уменьшить в m раз, а для ρ-метода — только в m раз.
Суть распараллеливания λ-метода состоит в следующем:
?

1. Выбрать в G подмножество различимых элементов G∗ такое, что принадлежность g ∈ G∗ можно проверить очень быстро (напр., элементы G кодируются бинарными строками, тогда элементы G∗ — это
строки, которые начинаются с определенного префикса).
2. На отдельных машинах вести расчет траекторий ручных и диких кенгуру. Вести общий массив различимых элементов, которые достигли кенгуру.
3. Анализировать пересечение траекторий кенгуру в различимых точках и, при возможности, определять
дискретный логарифм.

119

--">