Loading [MathJax]/extensions/TeX/mathchoice.js

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

Алгоритм исчисления порядка (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*p, то база состоит из t первых простых чисел).
  2. Возводим g в случайную степень k, где k такое, что 0k<n. Получаем gk.
  3. Представляем gk следующим образом:
    gk=ti=1paii,
      где ai0 (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
  4. Из пункта 3 следует выражение
    k \equiv \sum_{i=1}^t a_i \log_g p_i \mod n,
      полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а g^n \equiv 1 в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
  5. Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
  6. Выбираем случайное число k такое, что 0 \leqslant k < n. Вычисляем cg^k.
  7. Повторяем пункт 3, только для числа cg^k. Если не получается, то возвращаемся к 6-му пункту.
  8. Аналоногично пункту 4, получаем:
    x = \log_gc = \sum_{i=1}^t a_i \log_g p_i - k \mod n, где \log_g p_i (1 \leqslant i \leqslant t), где k = \log _g g^k \mod n. В этом пункте мы и решили задачу дискретного логарифма, отыскав x = \log_g c.

Выход: x = \log_g c.

Пример


 Решить уравнение: 17 \equiv 10^x\;(mod47)
 Выбираем факторную базу S = \{2,3,5\} Пусть k = 7 Вычисляем g^k
k = 1 \;\;\;\; 10^1 mod 47 = 10 = 2 * 5
k = 2 \;\;\;\; 10^2 mod 47 \equiv 6 = 2 * 3
k = 3 \;\;\;\; 10^3 mod 47 \equiv 13
k = 4 \;\;\;\; 10^4 mod 47 \equiv 36 = 2 * 2 * 3 * 3
k = 5 \;\;\;\; 10^5 mod 47 \equiv 31
k = 6 \;\;\;\; 10^6 mod 47 \equiv 28 = 2 * 2* 7
k = 7 \;\;\;\; 10^7 mod 47 \equiv 45 = 3 * 3 * 5
 Логарифмируем и обозначаем U_i = log_gp_i И получаем систему уравнений\left\{\begin{matrix}U_1+U_3 = 1 \\ U_1 + U_2 = 2 \\ 2U_1 + 2U_2 = 4 \\ 2U_2 + U_3 = 7\end{matrix}\right.
 Решаем её
u_2 = \frac{8}{3} (mod46) = 8*3^{-1}(mod46) = \{\varphi(46) = \varphi(2*23)\} = 22 = 8*3^{22}(mod46)\equiv 17
 Действительно, 10^8 mod47 \equiv 3, следовательно U_1 = 30,U_2 = 18, U_3 = 17
 Находим k такое, чтобы cg^k = {\displaystyle\prod_{i=1}^{t} p^{a_i}_i}
17 * 10^1 (mod47) = 29
17 * 10 ^2 (mod47) = 8 = 2 * 2 * 2
 Следовательно k = 2
 Логарифмируем данное выражение и получаем
log_a17 = [(log_a2 + log_a2 + log_a2) -2] mod46 = (3*30 - 2)mod 46 \equiv 42
Ответ: x = 42

Сложность


 В данном алгоритме, количество итераций зависит, как от размераp, так и от размера факторной базы. Но факторную базу мывыбираем заранее, и её размер является фиксированным. Поэтому итоговаясложность определяется только размером простого числа и равняется:O(c_1*2^{(c_2 + o(1))\sqrt{logp\;loglogp}}) , где c_1,c_2 —некоторые константы, зависящие от промежуточных вычислений, в частности,от выбора факторной базы.

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


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

Сложность


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