02.01.2023

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

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

История

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

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

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

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

Алгоритм

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

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

Выбираем факторную базу S = {p1, p2, p3, …, pt} (Если G = Z*p, то база состоит из t первых простых чисел).

Возводим g в случайную степень k, где k такое, что 0 ⩽ k < n {displaystyle 0leqslant k<n} . Получаем g k {displaystyle g^{k}} .

Представляем gk следующим образом: g k = ∏ i = 1 t p i a i , {displaystyle g^{k}=prod _{i=1}^{t}p_{i}^{a_{i}},} где a i ⩾ 0 {displaystyle a_{i}geqslant 0} (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.

Из пункта 3 следует выражение k ≡ ∑ i = 1 t a i log g ⁡ p i mod n , {displaystyle kequiv sum _{i=1}^{t}a_{i}log _{g}p_{i}mod n,} полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а g n ≡ 1 {displaystyle g^{n}equiv 1} в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).

Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.

Выбираем случайное число k такое, что 0 ⩽ k < n {displaystyle 0leqslant k<n} . Вычисляем c g k {displaystyle cg^{k}} .

Повторяем пункт 3, только для числа c g k {displaystyle cg^{k}} . Если не получается, то возвращаемся к 6-му пункту.

Аналогично пункту 4, получаем: x = log g ⁡ c = ∑ i = 1 t a i log g ⁡ p i − k mod n {displaystyle x=log _{g}c=sum _{i=1}^{t}a_{i}log _{g}p_{i}-kmod n} , где log g ⁡ p i {displaystyle log _{g}p_{i}} ( 1 ⩽ i ⩽ t {displaystyle 1leqslant ileqslant t} ), где k = log g ⁡ g k mod n {displaystyle k=log _{g}g^{k}mod n} . В этом пункте мы и решили задачу дискретного логарифма, отыскав x = log g ⁡ c {displaystyle x=log _{g}c} .

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

Пример

Решить уравнение: 17 ≡ 10 x ( m o d 47 ) {displaystyle 17equiv 10^{x};(mod47)}

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

k = 1 10 1 m o d 47 = 10 = 2 ∗ 5 {displaystyle k=1;;;;10^{1}mod47=10=2*5}

k = 2 10 2 m o d 47 ≡ 6 = 2 ∗ 3 {displaystyle k=2;;;;10^{2}mod47equiv 6=2*3}

k = 3 10 3 m o d 47 ≡ 13 {displaystyle k=3;;;;10^{3}mod47equiv 13}

k = 4 10 4 m o d 47 ≡ 36 = 2 ∗ 2 ∗ 3 ∗ 3 {displaystyle k=4;;;;10^{4}mod47equiv 36=2*2*3*3}

k = 5 10 5 m o d 47 ≡ 31 {displaystyle k=5;;;;10^{5}mod47equiv 31}

k = 6 10 6 m o d 47 ≡ 28 = 2 ∗ 2 ∗ 7 {displaystyle k=6;;;;10^{6}mod47equiv 28=2*2*7}

k = 7 10 7 m o d 47 ≡ 45 = 3 ∗ 3 ∗ 5 {displaystyle k=7;;;;10^{7}mod47equiv 45=3*3*5}

Логарифмируем и обозначаем U i = l o g g p i {displaystyle U_{i}=log_{g}p_{i}} И получаем систему уравнений { U 1 + U 3 = 1 U 1 + U 2 = 2 2 U 1 + 2 U 2 = 4 2 U 2 + U 3 = 7 {displaystyle left{{egin{matrix}U_{1}+U_{3}=1U_{1}+U_{2}=22U_{1}+2U_{2}=42U_{2}+U_{3}=7end{matrix}} ight.}

Решаем её

u 2 = 8 3 ( m o d 46 ) = 8 ∗ 3 − 1 ( m o d 46 ) = { φ ( 46 ) = φ ( 2 ∗ 23 ) } = 22 = 8 ∗ 3 22 ( m o d 46 ) ≡ 18 {displaystyle u_{2}={frac {8}{3}}(mod46)=8*3^{-1}(mod46)={varphi (46)=varphi (2*23)}=22=8*3^{22}(mod46)equiv 18}

Действительно, 10 18 m o d 47 ≡ 3 {displaystyle 10^{18}mod47equiv 3} , следовательно U 1 = 30 {displaystyle U_{1}=30} , U 2 = 18 {displaystyle U_{2}=18} , U 3 = 17 {displaystyle U_{3}=17}

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

17 ∗ 10 1 ( m o d 47 ) = 29 {displaystyle 17*10^{1}(mod47)=29}

17 ∗ 10 2 ( m o d 47 ) = 8 = 2 ∗ 2 ∗ 2 {displaystyle 17*10^{2}(mod47)=8=2*2*2}

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

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

l o g a 17 = [ ( l o g a 2 + l o g a 2 + l o g a 2 ) − 2 ] m o d 46 = ( 3 ∗ 30 − 2 ) m o d 46 ≡ 42 {displaystyle log_{a}17=[(log_{a}2+log_{a}2+log_{a}2)-2]mod46=(3*30-2)mod46equiv 42}

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

Сложность

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