Интернет магазин китайских планшетных компьютеров



Компьютеры - Дискретное логарифмирование - Пример

23 января 2011


Оглавление:
1. Дискретное логарифмирование
2. Пример
3. Вычислительная сложность и приложения в криптографии



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

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

3^x\equiv 13\mod{17}.

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


3 ≡ 3 3 ≡ 9 3 ≡ 10 3 ≡ 13 3 ≡ 5 3 ≡ 15 3 ≡ 11 3 ≡ 16
3 ≡ 14 3 ≡ 8 3 ≡ 7 3 ≡ 4 3 ≡ 12 3 ≡ 2 3 ≡ 6 3 ≡ 1


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

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

Алгоритмы решения

В произвольной мультипликативной группе

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья J. Buchmann, M. J. Jacobson и E. Teske. В алгоритме используется таблица, состоящая из O пар элементов и выполняется O умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.

В кольце вычетов по простому модулю

Рассмотрим уравнение

a^x\equiv b\mod{p}, )

где p - простое, b не делится на p. Если a является образующим элементом группы \mathbb{Z}/p\mathbb{Z}, то уравнение имеет решение при любых b. Такие числа a называются ещё первообразными корнями, и их количество равно φ, где φ — функция Эйлера. Решение уравнения можно находить по формуле:

x=\sum\limits_{i=1}^{p-2}^{-1}b^i\mod{p}.

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

Следующий алгоритм имеет сложность O

Алгоритм

  1. Присвоить H:=+1
  2. Найти c\equiv a^H\mod{p}
  3. Составить таблицу значений c^u\mod{p}, 1\leq u\leq H, и упорядочить её.
  4. Составить таблицу значений b\cdot a^v\mod{p}, 0\leq v\leq H, и упорядочить её.
  5. Найти совпавшие элементы из первой и второй таблиц. Для них
    c^u=b\cdot a^v\mod{p},
    откуда a^{Hu-v}\equiv b\mod{p}.
  6. Выдать x\equiv Hu-v\mod{p-1}.

Конец алгоритма

Существует также множество других алгоритмов для решения задачи дискретного логарифмирования в поле вычетов. Их принято разделять на экспоненциальные и субэкспоненциальные. Полиномиального алгоритма для решения этой задачи пока не существует.

Алгоритмы с экспоненциальной сложностью

  1. Алгоритм Шенкса
  2. Алгоритм Полига-Хеллмана — работает, если известно разложение числа p-1=\prod\limits_{i=1}^{s}q_i^{\alpha_i} на простые множители. Сложность: O). Если множители, на которые раскладывается p − 1, достаточно маленькие, то алгоритм очень эффективен.
  3. ρ-метод Полларда имеет эвристическую оценку сложности O.

Субэкспоненциальные алгоритмы

Данные алгоритмы имеют сложность O^{d})})~ арифметических операций, где c~ и  0\leq d<1 — некоторые константы. Эффективность алгоритма во многом зависит от близости c к 1 и d — к 0.

  1. Алгоритм Адлемана появился в 1979 году. Это был первый субэкспоненциалный алгоритм дискретного логарифмирования. На практике он всё же недостаточно эффективен. В этом алгоритме d=\frac{1}{2}.
  2. Алгоритм COS был предложен в 1986 году математиками Копперсмитом, Одлыжко и Шреппелем. В этом алгоритме константа c=1~, d=\frac{1}{2}. В 1991 году с помощью этого метода было проведено логарифмирование по модулю p \approx 10^{58}. В 1997 году Вебер провел дискретное логарифмирование по модулю p \approx 10^{85} с помощью некоторой версии данного алгоритма. Экспериментально показано, что при p \leq 10^{90} алгоритм COS лучше решета числового поля.
  3. Решето числового поля было применено к дискретному логарифмированию позднее, чем к факторизации чисел. Первые идеи появились в 1990-х годах. Алгоритм, предложенный Д. Гордоном в 1993 году, имел эвристическую сложность O^{\frac{1}{3}}}), но оказался достаточно непрактичным. Позднее было предложено множество различных улучшений данного алгоритма. Было показано, что при p \geq 10^{100} решето числового поля быстрее, чем COS. Современные рекорды в дискретном логарифмировании получены именно с помощью этого метода.

Наилучшими параметрами в оценке сложности на данный момент является c=^{\frac{1}{3}}/3\approx 1,902, d=\frac{1}{3}.

Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут c\approx 1,00475, d=\frac{2}{5}. За счёт того, что константа c достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с d=\frac{1}{3}.

В произвольном конечном поле

Задача рассматривается в поле GF, где q = p, p — простое.

  1. Алгоритм исчисления индексов эффективен, если p невелико. В этом случае он имеет эвристическую оценку сложности O^{\frac{1}{2}}}).
  2. Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при n = 2 и имеет сложность O^{\frac{1}{2}}}) арифметических операций.
  3. Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой d=\frac{1}{3} в оценки сложности. Данный алгоритм появился в 1984 году — до изобретения решета числового поля.

В группе точек на эллиптической кривой

Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда mP — это \underbrace{P+\ldots+P}\limits_{m}. Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа m, что

mP = A

для заданных точек P и A.

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии, Менезес, Окамото и Венстон предложили алгоритм, использующий спаривание Вейля. Для эллиптической кривой, определённой над полем GF, данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле GF. Однако, данное сведение полезно, только если степень k мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.



Просмотров: 3895


<<< Доверенная загрузка (аппаратные средства)