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

Алгоритм исчисления порядка (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

У этой статьи есть несколько проблем, помогите их исправить: В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (5 января 2016) Эту статью необходимо исправить в соответствии с правилами Википедии об оформлении статей. Пожалуйста, помогите улучшить эту статью. (5 января 2016) Достоверность этой статьи поставлена под сомнение. Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье. Соответствующую дискуссию можно найти на странице обсуждения. (5 января 2016) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.