Задача вычисления дискретного логарифма в циклических группах по сей
день не имеет эффективного решения. На вычислительной сложности это-
го преобразования основано подавляющее большинство алгоритмов асимме-
тричной криптографии. Задача состоит в следующем. Пусть задана цикли-
ческая группа
(
G,
•
)
с образующим (примитивным) элементом
g
, известен
порядок группы
ord(
G
) =
n
. Для некоторого
h
2
G
:
h
=
g
y
,
y
2
N
, требуется
найти показатель степени
y
, в которую возведен образующий элемент.
В настоящее время самым эффективным алгоритмом решения такой
задачи для случая произвольной циклической группы является алгоритм
Сильвера–Полига–Хэллмана [1] (теорема В.И. Нечаева, 1965 г.). Алгоритм
сводится к переходу для логарифмирования в подгруппы группы
G
простого
порядка и достаточно эффективен в том случае, если порядок группы
n
не
имеет больших простых чисел в разложении на множители.
Логарифмирование в подгруппах проводится с помощью алгоритма Гель-
фонда –Шенкса, более известного как алгоритм согласования [2]. Его слож-
ность составляет
O
√
p
+ log
2
p
, где
p
— простой порядок подгруппы, в
которой осуществляется логарифмирование.
Таким образом, в случае, если в разложении порядка группы на множите-
ли есть простое число, сравнимое с
n
, например
n
= 2
p
, задача вычисления
дискретного логарифма потребует выполнения
√
p
операций. При этом в
памяти будут храниться
2
√
p
элементов группы
G
. В современной криптогра-
фии требования к значениям наименьших простых делителей
p
составляют
250 бит, поэтому для взлома таких криптосистем потребуется
√
2
250
опе-
раций. Это число космических масштабов, собственно на этом и основана
криптографическая стойкость асимметричных систем.
В настоящей статье предлагается еще один способ вычисления дискрет-
ного логарифма в произвольных циклических группах. Этот алгоритм не
привнесет каких-либо улучшений, оценка сложности логарифмирования про-
извольного элемента группы по-прежнему будет составлять
√
p
, тем не менее,
на любом шаге алгоритма после проведения
k
операций умножения можно
успешно находить
k
2
/
2
показателей.
Как и хорошо известный
ρ
-метод Полларда [3, 4], алгоритм использует
технику многократного итерирования отображений, но в отличие от
ρ
-метода
справедлив для любых циклических групп, так как не использует каких-либо
специфических свойств группы
G
, кроме свойства цикличности относитель-
но операции “
•
”.
Алгоритм использует отображение
F
:
G
k
→
G
k
,
k
2
N
, которое в некото-
рых источниках называется
отображением Ньютона
. Пусть вектор
v
2
G
k
и
v
[
i
]
2
G
—
i
-я координата вектора
v
. Тогда вектор
w
=
F
(
v
)
получается
следующим образом:
w
[
i
] =
v
[
i
]
•
v
[
i
+ 1]
,
0
≤
i < k
−
1;
(1)
w
[
k
−
1] =
v
[0]
•
v
[
k
−
1]
.
Описание алгоритма.
Постановка задачи.
Для
b
=
a
y
, требуется най-
ти
y
. Порядок группы
ord(
G
) =
n
. Сначала переходим в подгруппу простого
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 81
