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

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

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

Для заданного простого числа ${\displaystyle p}$ и двух целых чисел ${\displaystyle g}$ и ${\displaystyle c}$ требуется найти целое число ${\displaystyle x}$, удовлетворяющее сравнению:

${\displaystyle g^{x}\equiv c\;{\pmod {p}},}$

где ${\displaystyle c}$ является элементом циклической группы ${\displaystyle G}$, порожденной элементом ${\displaystyle g}$.

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

Задача: найти x такое, что ${\displaystyle g^{x}\equiv c}$.

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

   ${\displaystyle g^{k}=\prod _{i=1}^{t}p_{i}^{a_{i}},}$

   где ${\displaystyle a_{i}\geqslant 0}$ (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.

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

   ${\displaystyle k\equiv \sum _{i=1}^{t}a_{i}\log _{g}p_{i}\mod n,}$

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

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

   ${\displaystyle x=\log _{g}c=\sum _{i=1}^{t}a_{i}\log _{g}p_{i}-k\mod n}$, где ${\displaystyle \log _{g}p_{i}}$ (${\displaystyle 1\leqslant i\leqslant t}$), где ${\displaystyle k=\log _{g}g^{k}\mod n}$. В этом пункте мы и решили задачу дискретного логарифма, отыскав ${\displaystyle x=\log _{g}c}$.

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

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

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

${\displaystyle k=1\;\;\;\;10^{1}mod47=10=2*5}$

${\displaystyle k=2\;\;\;\;10^{2}mod47\equiv 6=2*3}$

${\displaystyle k=3\;\;\;\;10^{3}mod47\equiv 13}$

${\displaystyle k=4\;\;\;\;10^{4}mod47\equiv 36=2*2*3*3}$

${\displaystyle k=5\;\;\;\;10^{5}mod47\equiv 31}$

${\displaystyle k=6\;\;\;\;10^{6}mod47\equiv 28=2*2*7}$

${\displaystyle k=7\;\;\;\;10^{7}mod47\equiv 45=3*3*5}$

Логарифмируем и обозначаем ${\displaystyle U_{i}=log_{g}p_{i}}$ И получаем систему уравнений ${\displaystyle \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.}$

Решаем её

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

Действительно, ${\displaystyle 10^{18}mod47\equiv 3}$, следовательно ${\displaystyle U_{1}=30}$, ${\displaystyle U_{2}=18}$, ${\displaystyle U_{3}=17}$

Находим k такое, чтобы ${\displaystyle cg^{k}={\displaystyle \prod _{i=1}^{t}p_{i}^{a_{i}}}}$

${\displaystyle 17*10^{1}(mod47)=29}$

${\displaystyle 17*10^{2}(mod47)=8=2*2*2}$

Следовательно ${\displaystyle k=2}$

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

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

Ответ: ${\displaystyle x=42}$

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

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

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

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

• http://refdb.ru/look/1629414-pall.html
• http://pratsi.opu.ua/app/webroot/articles/1414145386.pdf
• https://en.wikipedia.org/wiki/Index_calculus_algorithm