Дискретное логарифмирование

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:45, 1 апреля 2016.
TemplateDifinitionIcon.svg Определение «Дискретное логарифмирование»
Дискретное логарифмирование (DLOG) — задача обращения функции в некоторой конечной группе .

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

Задачу нахождения дискретного логарифма можно ставить для любой группы . Рассмотрим элемент

Пусть дано: Найти: постановка вопроса.

Для некоторых групп задача решается просто.

Пример в аддитивной группе

Выясняем, когда узнаем количество решений и находим их. Решение простое.

Пример в кольце вычетов

Проще всего рассмотреть задачу дискретного логарифмирования в кольце вычетов[1] по модулю простого числа.

Под кольцом понимается абелева группа по сложению, на которой задана операция умножения, обладающая в общем случае свойствами ассоциативности и дистрибутивности.

  1.  — ассоциативность умножения;
  2.  — дистрибутивность.

Пусть задано сравнение

Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 33≡27 — остаток от деления на 17 равен 10).

31 ≡ 3 32 ≡ 9 33 ≡ 10 34 ≡ 13 35 ≡ 5 36 ≡ 15 37 ≡ 11 38 ≡ 16
39 ≡ 14 310 ≡ 8 311 ≡ 7 312 ≡ 4 313 ≡ 12 314 ≡ 2 315 ≡ 6 316 ≡ 1

Теперь легко увидеть, что решением рассматриваемого сравнения является x=4, поскольку 34≡13.

На практике модуль обычно является достаточно большим числом, и метод перебора является слишком медленным, поэтому возникает потребность в более быстрых алгоритмах.

Ссылки

  1. Сравнение по модулю — Википедия https://ru.wikipedia.org/wiki/Сравнение_по_модулю