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

Алгоритм исчисления порядка (index-calculusalgorithm) — вероятностный алгоритм вычисления дискретного алгоритмав кольце вычетов по модулю простого числа. На сложности нахождениядискретного логарифма основано множество алгоритмов связанных скриптографией. Так как для решения данной задачи с использованиембольших чисел требуется большое количество ресурсов, предоставитькоторые не может ни один современный компьютер. Примером такогоалгоритма является ГОСТ Р 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\textsuperscript*p, то база состоит из t первых простых чисел).
  2. Возводим g в случайную степень k, где k такое, что 0k<n. Получаем gk.
  3. Представляем g\textsuperscriptk следующим образом:
    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)), по сравнению соригинальном алгоритмом.