x
m
c
1
xx
−
1
m
+
c
2
−
X
k
:
p
k
2
F
1
(
y
km
D
1
k
)
=
=
x
n
c
3
xx
−
1
n
+
c
4
−
X
k
:
p
k
2
F
2
(
y
kn
D
2
k
)
.
Подставив вместо
y
km
и
y
kn
соответствующие выражения, получаем:
x
m
c
1
xx
−
1
m
+
c
2
−
X
k
:
p
k
2
F
1
(
x
k
x
−
1
m
D
1
k
)
=
=
x
n
c
3
xx
−
1
n
+
c
4
−
X
k
:
p
k
2
F
2
(
x
k
x
−
1
n
D
2
k
)
(
mod
r
)
.
Раскроем скобки:
c
1
x
+
c
2
x
m
−
X
k
:
p
k
2
F
1
(
x
k
D
1
k
) =
=
c
3
x
+
c
4
x
n
−
X
k
:
p
k
2
F
2
(
x
k
D
2
k
) (
mod
r
)
.
(11)
Получили линейное уравнение от
|
F
|
+ 1
неизвестного.
Аналогичным образом составляются еще
|
F
|
линейных уравнений ви-
да (11). Таким образом, для решения логарифма необходима
(
|
F
|
+ 1)
пара
совпадающих чисел среди матриц
S, S
1
, . . . , S
|
F
|
.
6 этап.
Решение системы из
(
|
F
|
+ 1)
линейных уравнений с
(
|
F
|
+ 1)
неизвестным и нахождение
x
(
mod
r
)
.
7 этап.
В остальных подгруппах группы
Z
p
определяют
x
(
mod
r
i
)
,
повторяя этапы 2. . . 6 для нахождения искомого
x
(
mod
n
)
(см. алгоритм
Полига–Хэллмана [1]).
Сложность обобщенного алгоритма
. Для оценки сложности алгоритма
применим технику, которая использовалась для оценки сложности алгоритма
Диксона для факторизации чисел [6]. В основе этой техники лежит теоре-
ма де Брейна–Эрдеша [7], которая утверждает следующее. Обозначим через
Ψ (
n, M
)
— число натуральных чисел
a
≤
n
, в разложении которых при-
сутствуют только числа из факторной базы
F
=
{
p
i
:
p
i
< M
}
. Теорема
утверждает, что
Ψ (
n, M
) =
nu
−
u
, u
=
ln
n
ln
M
.
Как и в описании алгоритма,
n
— это порядок мультипликативной группы
Z
p
, наибольшее число в группе. В нашем случае, в отличие от алгоритма Дик-
сона, требуется оценить не вероятность попадания в гладкое число (т.е. число,
разложимое по факторной базе), а вероятность нахождения пары чисел, кото-
рые имеют общий делитель, взаимно простой со всеми числами из факторной
базы. Тогда при попадании в такую пару после четвертого этапа алгоритма
в матрицах найдется пара совпадающих чисел и составится уравнение. Рас-
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 89
