Алгоритм исчисления порядка
(
index-calculus algorithm
) —
вероятностный алгоритм
вычисления
дискретного логарифма
в
кольце вычетов
по модулю
простого числа
. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с
криптографией
. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный
компьютер
. Примером такого алгоритма является
ГОСТ Р 34.10-2012
.
История
Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача
дискретного логарифмирования
становится важной для математики и криптоанализа. Это связано с созданием криптосистемы
Диффи-Хелмана
. В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.
Постановка задачи дискретного логарифмирования
Для заданного простого числа
и двух целых чисел
и
требуется найти целое число
, удовлетворяющее сравнению:
|
|
где
является элементом
циклической группы
, порожденной элементом
.
Алгоритм
Вход
:
g
— генератор циклической группы порядка
n
,
a
— из циклической подгруппы,
p
— простое число,
c
— параметр надёжности, обычно берут равным 10 или близкое к этому значению число (используется для реализации алгоритма на компьютере, если решает человек, то его не задают).
Задача
: найти
x
такое, что
.
-
Выбираем факторную базу
S
= {
p
1
,
p
2
,
p
3
, …,
p
t
} (Если
G
=
Z
*
p
, то база состоит из
t
первых простых чисел).
-
Возводим
g
в случайную степень
k
, где
k
такое, что
. Получаем
.
-
Представляем
g
k
следующим образом:
-
-
где
(то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
-
Из пункта 3 следует выражение
-
-
полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а
в группе
G
). В этом выражении неизвестны логарифмы. Их
t
штук. Необходимо получить таких уравнений
t
+
c
штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
-
Решаем получившуюся систему уравнений, с
t
неизвестными и
t
+
c
сравнениями.
-
Выбираем случайное число
k
такое, что
. Вычисляем
.
-
Повторяем пункт 3, только для числа
. Если не получается, то возвращаемся к 6-му пункту.
-
Аналогично пункту 4, получаем:
-
, где
(
), где
. В этом пункте мы и решили задачу дискретного логарифма, отыскав
.
Выход
:
.
Пример
Решить уравнение:
Выбираем факторную базу
Пусть k = 7
Вычисляем
Логарифмируем и обозначаем
И получаем систему уравнений
Решаем её
Действительно,
, следовательно
,
,
Находим k такое, чтобы
Следовательно
Логарифмируем данное выражение и получаем
Ответ
:
Сложность
В данном алгоритме, количество итераций зависит, как от размера
p
, так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется:
, где
,
— некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.
Усовершенствования
, суть которого состоит в том, чтобы использовать таблицу индексов.
Сложность
Вычислительная сложность снижена до
, по сравнению с оригинальном алгоритмом.
См. также
Ссылки