Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Дискретное логарифмирование (DLOG) – задача обращения функции g^x в некоторой конечной мультипликативной группе G.

В основном данную задачу рассматривают в мультипликативной группе конечного поля или в группе точек на эллиптической кривой.

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

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

Постановка задачиПравить

Пусть в некоторой конечной мультипликативной абелевой группе G задано уравнение

g^x=a. (1)

Решение задачи дискретного логарифмирования состоит в нахождении некоторо целого неотрицательного числа x, удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху — алгоритм полного перебора нашел бы решение за число шагов, не выше порядка данной группы.

Чаще всего рассматривается случай, когда G=\langle g\rangle, то есть группа является циклической, порождённой элементом g. В этом случае уравнение всегда имеет решение. В случае же произвольной группы, вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

ПримерПравить

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

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

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


Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 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.

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

Алгоритмы решенияПравить

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

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья BuchmannJ., Jacobson M.J., Teske E. On some computational problems in finite abelian groups[1]. В алгоритме используется таблица, состоящая из O(\sqrt{|\langle g\rangle|}) пар элементов и выполняется O(\sqrt{|\langle g\rangle|}) умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.

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

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

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

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

x=\sum\limits_{i=1}^{p-1}(1-a^i)^{-1}b^i\mod{p}.

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

Следующий алгоритм имеет сложность O(p^{\frac{1}{2}}\log{p})

Алгоритм

  1. Присвоить H:=[p^{\frac{1}{2}}]+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. Алгоритм Шенкса (алгоритм больших и малых шагов, baby-step giant-step)
  2. Алгоритм Полига-Хеллмана — работает, если известно разложение числа p-1=\prod\limits_{i=1}^{s}q_i^{\alpha_i} на простые множители. Сложность: O(\sum\limits_{i=0}^{s}\alpha_i(\log{p}+q_i)). Если множители, на которые раскладывается p-1, достаточно маленькие, то алгоритм очень эффективен.
  3. ρ-метод Полларда имеет эвристическую оценку сложности O(p^{\frac{1}{2}}).

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

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

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

Наилучшими параметрами в оценке сложности на данный момент является c=(92+26\sqrt{13})^{\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), где q=p^n, p — простое.

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

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

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

mP=A

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

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек элиптической кривой. Впоследствии, Менезес (Alfred J. Menezes), Окамото (Tatsuaki Okamoto) и Венстон (Scott A. Vanstone) предложили алгоритм, использующий спаривание Вейля. Для эллитической кривой, определённой над полем GF(q), данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле GF(q^k). Однако, данное сведение полезно, только если степень k мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.

Вычислительная сложность и приложения в криптографииПравить

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Идея, лежащая в основе подобных систем, опирается на высокую вычислительную сложность обращения некоторых числовых функций. В данном случае, операция дискретного логарифмирования является обратной к степенной функции. Последняя вычисляется достаточно просто, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Вместе с тем, хотя задача отыскания дискретного логарифма принадлежит классу NP, NP-полнота её на сегодняшний день не доказана (также как и для проблемы факторизации). Поэтому, нахождение полиномиального алгоритма вычисления дискретного логарифма, не будет ещё означать равенства P=NP.

Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Теоретически доказано, что, используя их, дискретный логарифм может быть вычислен за полиномиальное время[2]. В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе.

Классическими криптографическими схемами, базирующимися на сложности задачи дискретного логарифмирования, являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений.

ЛитератураПравить

  1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии – Москва: МЦМНО, 2003. – 328 c. ISBN 5-94057-103-4
  2. Коблиц Н. Курс теории чисел и криптографии – Москва: Научное издательство ТВПб 2001. – 254с. ISBN 5-85484-014-6
  3. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // Advances in Crytology: Proceedings of EuroCrypt’84 /Thomas Beth, Norbert Cot, and Igemar Ingemarsson, editors. Berlin: Springer-Verlag, 1984 (Lect. Notes in Computer Science; V. 209). P. 224-316.
  4. Buchmann J., Jacobson M.J., Teske E. On some computational problems in finite abelian groups// Math. Comp. 1997. V. 66 (220). P. 1663-1687.

Ссылки Править

СноскиПравить

  1. Электронную версию см. на http://citeseer.ist.psu.edu/716900.html
  2. http://cs.mipt.ru/docs/comp/rus/develop/other/quantum_comp

Шаблон:Хорошая статья


cs:Diskrétní logaritmushe:בעיית לוגריתם דיסקרטיpl:Logarytm dyskretny vi:Lôgarit rời rạc

Викия-сеть

Случайная вики