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

Алгоритм исчисления порядка (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 такое, что $g^x\equiv c$.

1. Выбираем факторную базу S = {p₁, p₂, p₃, …, p_t} (Если G = Z^*_p, то база состоит из t первых простых чисел).
2. Возводим g в случайную степень k, где k такое, что $0⩽k<n$. Получаем $g^k$.
3. Представляем g^k следующим образом:

   $g^k=\prod _{i=1}^t{p}_i^{a_i},$

   где $a_i⩾0$ (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.

4. Из пункта 3 следует выражение

   $k\equiv \sum _{i=1}^t{a}_i{\log }_g{p}_{i}modn,$

   полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а $g^n\equiv 1$ в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).

5. Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
6. Выбираем случайное число k такое, что $0⩽k<n$. Вычисляем $c{g}^k$.
7. Повторяем пункт 3, только для числа $c{g}^k$. Если не получается, то возвращаемся к 6-му пункту.
8. Аналогично пункту 4, получаем:

   $x={\log }_{g}c=\sum _{i=1}^t{a}_i{\log }_g{p}_i-kmodn$, где ${\log }_g{p}_i$ ($1⩽i⩽t$), где $k={\log }_g{g}^{k}modn$. В этом пункте мы и решили задачу дискретного логарифма, отыскав $x={\log }_{g}c$.

Выход: $x={\log }_{g}c$.

Пример

Решить уравнение: $17\equiv 10^x(mod47)$

Выбираем факторную базу $S=\{2,3,5\}$ Пусть k = 7 Вычисляем $g^k$

$k=110^{1}mod47=10=2*5$

$k=210^{2}mod47\equiv 6=2*3$

$k=310^{3}mod47\equiv 13$

$k=410^{4}mod47\equiv 36=2*2*3*3$

$k=510^{5}mod47\equiv 31$

$k=610^{6}mod47\equiv 28=2*2*7$

$k=710^{7}mod47\equiv 45=3*3*5$

Логарифмируем и обозначаем $U_i=lo{g}_g{p}_i$ И получаем систему уравнений $\{\begin{array}{c}{U}_1+U_3=1\\ U_1+U_2=2\\ 2U_1+2U_2=4\\ 2U_2+U_3=7\end{array}$

Решаем её

$u_2=\frac{8}{3}(mod46)=8*3^{-1}(mod46)=\{\phi (46)=\phi (2*23)\}=22=8*3^{21}(mod46)\equiv 18$

Действительно, $10^{18}mod47\equiv 3$, следовательно $U_1=30$, $U_2=18$, $U_3=17$

Находим k такое, чтобы $c{g}^k=\prod _{i=1}^t{p}_i^{a_i}$

$17*10^1(mod47)=29$

$17*10^2(mod47)=8=2*2*2$

Следовательно $k=2$

Логарифмируем данное выражение и получаем

$lo{g}_{a}17=[(lo{g}_{a}2+lo{g}_{a}2+lo{g}_{a}2)-2]mod46=(3*30-2)mod46\equiv 42$

Ответ: $x=42$

Сложность

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

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

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

Сложность

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

См. также

• Дискретное логарифмирование
• Алгоритм Полига — Хеллмана
• Ρ-алгоритм Полларда
• Алгоритм COS

Ссылки

• http://refdb.ru/look/1629414-pall.html
• http://pratsi.opu.ua/app/webroot/articles/1414145386.pdf