Алгоритм Адельмана для дискретного логарифмирования

$ git clone https://github.com/hse-malloc/adleman.git

$ cd adleman

$ docker-compose up

Задача дискретного логарифмирования

Пусть заданы простое число p и вычет a, показатель которого по модулю p равен q, то есть ord_p a = q и q | p-1. Пусть задан вычет b, удовлетворяющий сравнению

a^x ≡ b (mod p)

Задача определения вычета x (mod q) называется задачей вычисления дискретного логарифма элемента b по основанию a.

Принято использовать обозначение

x ≡ log_a b (mod q)

Сравнение разрешимо только в том случае, когда вычет b принадлежит множеству A = {1, a, a², ..., a^q-1}

Свойства дискретного логарифма аналогичны свойствам обычного логарифма. Так, например, если верно, что

b ≡ b₁^α₁ * ... * b_k^α_k (mod p)

то выполняется равенство

log_a b ≡ α₁ log_a b₁ + ... + α_k log_a b_k (mod q)

Это свойство будет использоваться дальше в методе Адельмана.

Метод Адельмана

Базовая идея

Допустим, что у нас есть таблица простых чисел меньших B

F = {p₁, p₂, ..., p_s}, ∀p∈F p<B

мы будем называть эту таблицу факторной базой. И допустим, что мы знаем значения логарифмов всех элементов факторной базы по основанию a, то есть мы знаем величины

x₁ ≡ log_a p₁ (mod q)

x₂ ≡ log_a p₂ (mod q)

...

x_s ≡ log_a p_s (mod q)

Тогда, если мы нашли вычет ξ ∈ F_q^* такой, что

b^ξ ≡ p₁^α₁ * ... * p_s^α_s (mod p),

где α_i ≥ 0 и p_i ∈ F ∀ i=0,...,s, то воспользовавшись свойством логарифма, описанным выше, получаем искомое решение поставленной задачи

log_a b ≡ ξ^-1 * (α₁ log_a p₁ + ... + α_s log_a p_s) (mod q)

Таким образом метод Адельмана сводится к двум последовательным шагам:

1. Построение факторной базы и нахождение логарифмов элементов этой базы
2. Подсчёт значения искомого логарифма.

Нахождение логарифмов элементов факторной базы.

При случайном выборе ξ ∈ F_q может возникнуть ситуация, когда вычет a^ξ полностью раскладывается по элементам факторной базы, то есть

a^ξ ≡ p₁^α₁ * ... * p_s^α_s (mod p)

в таком случае можно утверждать, что было получено уравнение на неизвестные нам x₁ ≡ log_a p₁ (mod q), ..., x_s ≡ log_a p_s (mod q) :

ξ ≡ α₁ x₁ + ... + α_s x_s (mod q)

Задача нахождения искомых x₁, ..., x_s сводится к генерации s линейно независимых уравнений и нахождении их решения. Итоговая система линейных урванений будет выглядеть как:

ξ₁ ≡ α₁¹ x₁ + ... + α_s¹ x_s (mod q)

ξ₂ ≡ α₁² x₁ + ... + α_s² x_s (mod q)

...

ξ_s ≡ α₁^s x₁ + ... + α_s^s x_s (mod q)

Или в матричном виде, как

ξ ≡ A x

В реализации до получения искомой матрицы A мы генерируем по s новых уравнений за один проход цикла, добавлям их к уже найденым и ищем среди них линейнонезависимые. Для получения разложения числа a^ξ на множители мы используем встроенную в Sage функцию factor, предаврительно запустив тест Миллера-Рабина.

Для упрощения работы учебного примера в настоящее время работа поддерживается только для простых q.

Для демонтарции работы алгоритма были сгенерированы простые числа p Софи Жермен порядков 2¹⁶, 2³², 2⁶⁴ и выбраны соответсвующие элементы a с мультипликативным порядком равным q = (p-1)/2

Сложность алгоритма и выбор границы факторной базы.

Обозначим за π(B) число простых чисел, непревосходящих B ( π(B) ~ B / ln B ).

Тогда сложность составления системы линейных уравнений будет O(π²(B) / p_a), где p_a - вероятность того, что a^ξ будет разлагаться на множители по факторной базе.

Сложность решениея системы линейных уравнений будет O(π³(B))

Сложность нахождения значения логарифма по известным логарифмам факторной базы будет O(π(B) / p_b), где p_b - вероятность того, что b^ξ будет разлагаться на множители по факторной базе.

Итоговая сложность будет O(π³(B) + π²(B) / p_a + π(B) / p_b).

Стоит заметить, что все величины: π(B), p_a и p_b существенно зависят от B.

Так, например, если выбрать большое число B, то итоговая сложность будет упираться в решение системы линейных уравнений, т.к. π(B) так же возрастёт (несмотря на то, что вероятности разложения по факторной базе не будут давать большой вклад).

Если же выбрать B достаточно маленьким, то и влад сложности решения системы линейных урванений будет невелик, однако тогда при случайном выборе ξ мы будем достаточно редко получать исходы при которых a^ξ и b^ξ будут разладться по факторной базе. То есть большой влкад в сложность будут играть маленькие вероятности p_a и p_b.

Для баланса между этими крайностями была выбрана теоретическая оценка B ~ L(1/2 , 1/2, q),

где L(1, 1/2, q) = e^{ln1/2q * (ln ln q)1/2} - субэкспоненциальная функция