O
(
N
) =
O
exp
C
0
+
C
00
ln ln
r
(ln ln
n
)
1
−
q
×
×
(ln
n
)
q
(ln ln
n
)
1
−
q
−
q
ln ln
n
=
=
O
exp
2
√
3
√
ln
n
∙
ln ln
n
−
0
,
5 ln ln
n
=
L
n
[1
/
2
,
1
,
15]
.
В основе приведенного алгоритма лежит сравнение двух элементов из
набора массивов после их приведения по факторной базе. Возникает зако-
номерный вопрос: дает ли выигрыш в сложности такое разбиение на пары?
Ответ на этот вопрос можно получить, оценив сложность другого алгорит-
ма, в котором после этапа приведения по факторной базе (этап 4) проводится
поиск элементов, равных единице, т.е. разложившихся по факторной базе. Ка-
ждый такой элемент также даст одно уравнение. Чтобы оценить сложность,
запишем аналогичное (14) неравенство, но уже для данного случая:
N >
h
+ 1
P
0
→
(ln
r
+ 1)
dim
>
ln
n
ln
M
ln
n
ln
M
.
Проведя преобразования, аналогичные описанным ранее, получаем слож-
ность алгоритма без разбиения на пары
L
n
[1
/
2
,
2]
. Следовательно, сравнение
двух элементов на совпадение после приведения по факторной базе дает не-
который выигрыш, который особенно заметен на небольших
n
.
При оценке сложности считали, что в матрицах после этапа их постро-
ения (этап 3) не окажется совпадающих элементов. Но, вообще говоря, со-
впадения возможны. В случае совпадения каких-либо двух элементов по-
прежнему можно составить уравнение вида (11), из которого будут исключе-
ны суммы по делителям из факторной базы. Следует иметь в виду, что неко-
торые из полученных уравнений могут оказаться линейно зависимыми. Под-
считать число линейно зависимых уравнений для многомерных матриц по-
ка не представляется возможным из-за сложности теоретических выкладок,
но вполне допустима экспериментальная оценка, аналогичная проведенной
для трехмерных матриц. Следовательно, в алгоритме присутствует некоторая
доля эвристики, обусловленная характеристиками применяемого отображе-
ния для генерации последовательности чисел. Был предложен лишь один
из способов на основе отображения Ньютона над многомерными матрицами
и показано, что для маломерных матриц число линейно зависимых уравне-
ний незначительно. На момент написания статьи эксперименты с матрицами
размера больше 3 не проводились.
Заключение.
В настоящее время известны алгоритмы дискретного
логарифмирования для числовых полей
GF
(
p
)
, которые имеют сложность
L
n
[1
/
3
,
const
]
,
n
=
p
−
1
, это алгоритмы на основе решета числового по-
ля [8, 9]. Все они очень эффективны для больших
n
, асимптотически стремя-
щихся к бесконечности. Для меньших
n
(
n <
10
100
)
существуют более эффек-
тивные алгоритмы, например алгоритм Копперсмита – Одлизко –Шреппеля
(COS) [10], который имеет сложность
L
n
[1
/
2
,
1]
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 93
