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

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

История Править

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

Постановка задачи дискретного логарифмирования Править

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

$g^x\equiv <!--\; \equiv \; -->c(\mathrm{mod}p),$$g^{x}\equiv c\;{\pmod {p}},$

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

Алгоритм Править

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

Задача: найти x такое, что $g^x\equiv <!--\; \equiv \; -->c$$g^{x}\equiv c$ .

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

   $g^k=\underset{i=1}{\overset{t}{\prod <!--\; \prod \; -->}}{p}_i^{a_i},$$g^{k}=\prod _{i=1}^{t}p_{i}^{a_{i}},$ 

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

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

   $k\equiv <!--\; \equiv \; -->\underset{i=1}{\overset{t}{\sum <!--\; \sum \; -->}}{a}_i{\log }_g<!--\; \; -->p_i\mathrm{mod}n,$$k\equiv \sum _{i=1}^{t}a_{i}\log _{g}p_{i}\mod n,$ 

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

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

   $x={\log }_g<!--\; \; -->c=\underset{i=1}{\overset{t}{\sum <!--\; \sum \; -->}}{a}_i{\log }_g<!--\; \; -->p_i-<!--\; -\; -->k\mathrm{mod}n$$x=\log _{g}c=\sum _{i=1}^{t}a_{i}\log _{g}p_{i}-k\mod n$ , где ${\log }_g<!--\; \; -->p_i$$\log _{g}p_{i}$  ($1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->t$$1\leqslant i\leqslant t$ ), где $k={\log }_g<!--\; \; -->g^k\mathrm{mod}n$$k=\log _{g}g^{k}\mod n$ . В этом пункте мы и решили задачу дискретного логарифма, отыскав $x={\log }_g<!--\; \; -->c$$x=\log _{g}c$ .

Выход: $x={\log }_g<!--\; \; -->c$$x=\log _{g}c$ .

Пример Править

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

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

$k=1{10}^{1}mod47=10=2\ast <!--\; \ast \; -->5$$k=1\;\;\;\;10^{1}mod47=10=2*5$ 

$k=2{10}^{2}mod47\equiv <!--\; \equiv \; -->6=2\ast <!--\; \ast \; -->3$$k=2\;\;\;\;10^{2}mod47\equiv 6=2*3$ 

$k=3{10}^{3}mod47\equiv <!--\; \equiv \; -->13$$k=3\;\;\;\;10^{3}mod47\equiv 13$ 

$k=4{10}^{4}mod47\equiv <!--\; \equiv \; -->36=2\ast <!--\; \ast \; -->2\ast <!--\; \ast \; -->3\ast <!--\; \ast \; -->3$$k=4\;\;\;\;10^{4}mod47\equiv 36=2*2*3*3$ 

$k=5{10}^{5}mod47\equiv <!--\; \equiv \; -->31$$k=5\;\;\;\;10^{5}mod47\equiv 31$ 

$k=6{10}^{6}mod47\equiv <!--\; \equiv \; -->28=2\ast <!--\; \ast \; -->2\ast <!--\; \ast \; -->7$$k=6\;\;\;\;10^{6}mod47\equiv 28=2*2*7$ 

$k=7{10}^{7}mod47\equiv <!--\; \equiv \; -->45=3\ast <!--\; \ast \; -->3\ast <!--\; \ast \; -->5$$k=7\;\;\;\;10^{7}mod47\equiv 45=3*3*5$ 

Логарифмируем и обозначаем $U_i=lo{g}_g{p}_i$$U_{i}=log_{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}$$\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\ast <!--\; \ast \; -->3^{-<!--\; -\; -->1}(mod46)=\{\mathrm{\phi <!--\; \phi \; -->}(46)=\mathrm{\phi <!--\; \phi \; -->}(2\ast <!--\; \ast \; -->23)\}=22=8\ast <!--\; \ast \; -->3^{22}(mod46)\equiv <!--\; \equiv \; -->18$$u_{2}={\frac {8}{3}}(mod46)=8*3^{-1}(mod46)=\{\varphi (46)=\varphi (2*23)\}=22=8*3^{22}(mod46)\equiv 18$ 

Действительно, ${10}^{18}mod47\equiv <!--\; \equiv \; -->3$$10^{18}mod47\equiv 3$ , следовательно $U_1=30$$U_{1}=30$ , $U_2=18$$U_{2}=18$ , $U_3=17$$U_{3}=17$ 

Находим k такое, чтобы $c{g}^k=\underset{i=1}{\overset{t}{\prod <!--\; \prod \; -->}}{p}_i^{a_i}$$cg^{k}={\displaystyle \prod _{i=1}^{t}p_{i}^{a_{i}}}$ 

$17\ast <!--\; \ast \; -->{10}^1(mod47)=29$$17*10^{1}(mod47)=29$ 

$17\ast <!--\; \ast \; -->{10}^2(mod47)=8=2\ast <!--\; \ast \; -->2\ast <!--\; \ast \; -->2$$17*10^{2}(mod47)=8=2*2*2$ 

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

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

$lo{g}_{a}17=[(lo{g}_{a}2+lo{g}_{a}2+lo{g}_{a}2)-<!--\; -\; -->2]mod46=(3\ast <!--\; \ast \; -->30-<!--\; -\; -->2)mod46\equiv <!--\; \equiv \; -->42$$log_{a}17=[(log_{a}2+log_{a}2+log_{a}2)-2]mod46=(3*30-2)mod46\equiv 42$ 

Ответ: $x=42$$x=42$ 

Сложность Править

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

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

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

Сложность Править

Вычислительная сложность снижена до $O(2lo{g}_2(p))$$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