Алгоритм исчисления порядка

Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного алгоритма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.

История


 Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана. В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.

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


 Для заданного простого числа p и двух целых чисел g и c требуется найти целое число x, удовлетворяющее сравнению:
 где c является элементом циклической группы G, порожденной элементом g.

Алгоритм


Вход: g — генератор циклической группы порядка n, a — из циклической подгруппы, p — простое число, c — параметр надёжности, обычно берут равным 10 или близкое к этому значению число (используется для реализации алгоритма на компьютере, если решает человек, то его не задают).
Задача: найти x такое, что gxc.

  1. Выбираем факторную базу S = \{p1, p2, p3, \ldots, pt\} (Если G = Z*p, то база состоит из t первых простых чисел).
  2. Возводим g в случайную степень k, где k такое, что 0k<n. Получаем gk.
  3. Представляем gk следующим образом:
    gk=i=1tpiai,

      где ai0 (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
  4. Из пункта 3 следует выражение
    ki=1tailoggpimodn,

      полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а gn1 в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
  5. Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
  6. Выбираем случайное число k такое, что 0k<n. Вычисляем cgk.
  7. Повторяем пункт 3, только для числа cgk. Если не получается, то возвращаемся к 6-му пункту.
  8. Аналоногично пункту 4, получаем:
    x=loggc=i=1tailoggpikmodn
    , где loggpi (1it), где k=logggkmodn. В этом пункте мы и решили задачу дискретного логарифма, отыскав x=loggc.

Выход: x=loggc.

Пример


 Решить уравнение: 1710x(mod47)
 Выбираем факторную базу S={2,3,5} Пусть k = 7 Вычисляем gk
k=1101mod47=10=25
k=2102mod476=23
k=3103mod4713
k=4104mod4736=2233
k=5105mod4731
k=6106mod4728=227
k=7107mod4745=335
 Логарифмируем и обозначаем Ui=loggpi И получаем систему уравнений {U1+U3=1U1+U2=22U1+2U2=42U2+U3=7
 Решаем её
u2=83(mod46)=831(mod46)={φ(46)=φ(223)}=22=8322(mod46)17
 Действительно, 108mod473, следовательно U1=30, U2=18, U3=17
 Находим k такое, чтобы cgk=i=1tpiai
17101(mod47)=29
17102(mod47)=8=222
 Следовательно k=2
 Логарифмируем данное выражение и получаем
loga17=[(loga2+loga2+loga2)2]mod46=(3302)mod4642
Ответ: x=42

Сложность


 В данном алгоритме, количество итераций зависит, как от размера p, так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется: O(c12(c2+o(1))logploglogp) , где c1,c2 — некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.

Усовершенствования


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

Сложность


 Вычислительная сложность снижена до O(2log2(p)), по сравнению с оригинальном алгоритмом.