порядка
p
, где
p
— делитель
n
:
d
=
n
p
;
g
=
a
d
;
h
=
b
d
.
Теперь переформулируем задачу логарифмирования для этой подгруп-
пы — необходимо вычислить
x
= log
g
h
,
g
— образующий в подгруппе.
Вычисляем все степени двоек, такие, что
2
i
< p
. Возводим образующий
элемент
g
во все эти степени:
g
1
g
2
g
4
. . .
g
2
k
, k
= log
2
p.
Каждый из получившихся элементов умножаем на
g
x
=
h
:
s
0
:
hg
1
hg
2
hg
4
. . .
hg
2
k
.
(2)
Показатели элементов последовательности (2) запишем в виде последо-
вательности
t
0
:
x
+ 2
0
x
+ 2
1
x
+ 2
2
. . .
x
+ 2
k
(
mod
p
)
.
(3)
К последовательности (2), интерпретируя ее как вектор
v
в соотноше-
ниях (1), применим отображение Ньютона и получим последовательность
s
1
=
F
(
s
0
)
. Затем для всех
i
≤
k
вычислим
s
i
=
F
(
s
i
−
1
)
. В итоге получим
k
+ 1
векторов, которые запишем в виде матрицы
S
:
S
=
s
0
s
1
s
2
...
s
k
=
s
[0][0]
s
[0][1]
. . . s
[0][
k
]
s
[1][0]
s
[1][1]
. . . s
[1][
k
]
s
[2][0]
s
[2][1]
. . . s
[2][
k
]
...
...
. . .
...
s
[
k
][0]
s
[
k
][1]
. . . s
[
k
][
k
]
.
(4)
В результате между элементами матрицы установятся следующие соот-
ношения:
s
[
i
] [
j
] =
s
[
i
−
1] [
j
]
•
s
[
i
−
1] [
j
+ 1]
,
1
≤
i
≤
k,
0
≤
j
≤
k
−
1
s
[
i
] [
k
] =
s
[
i
−
1] [0]
•
s
[
i
−
1] [
k
]
,
1
≤
i
≤
k.
Каждый элемент матрицы
S
есть образующий
g
, возведенный в некото-
рую степень. Обозначим ее через
t
[
i
][
j
]
и запишем матрицу показателей
T
:
T
=
t
0
t
1
. . .
t
k
=
2
0
2
1
. . .
2
k
2
0
×
x t
[0][0]
t
[0][1]
. . .
t
[0][
k
]
2
1
×
x t
[1][0]
t
[1][1]
. . .
t
[1][
k
]
. . .
2
k
×
x
. . .
t
[
k
][0]
. . .
t
[
k
][1]
. . .
. . .
. . .
t
[
k
][
k
]
.
(5)
Соотношения для элементов матрицы
Т
следующие:
t
[
i
] [
j
] =
t
[
i
−
1] [
j
] +
t
[
i
−
1] [
j
+ 1] (
mod
p
)
,
1
≤
i
≤
k,
0
≤
j
≤
k
−
1
t
[
i
] [
k
] =
t
[
i
−
1] [0] +
t
[
i
−
1] [
k
]
,
1
≤
i
≤
k.
82 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
