3 этап.
Сначала представим
p
i
в виде
p
y
ik
k
, выразив
y
ik
через неизвест-
ные
x
i
,
p
i
=
a
x
i
=
p
y
ik
k
= (
a
x
k
)
y
ik
)
y
ik
=
x
i
x
−
1
k
mod
n.
(9)
Поскольку
8
k
ord (
p
k
) =
n
, то
НОД
(
x
k
, n
) = 1
, поэтому существу-
ет
x
−
1
k
.
Аналогичным образом представим
b
в виде
p
z
k
k
:
b
=
a
x
=
p
z
k
k
= (
a
x
k
)
z
k
)
z
k
=
xx
−
1
k
mod
n.
(10)
Теперь переходим к третьему этапу алгоритма. Подразумевая представле-
ние
b
=
p
z
k
k
, после перехода в подгруппу получаем аргумент логарифма
h
,
а из
p
k
— основание логарифма
g
k
. Затем, подавая значения
h
и
g
k
на вход
соотношений (2), вычисляем многомерную матрицу
S
k
. Для всех значений
k
= 1
. . .
|
F
|
вычисляются матрицы
S
k
. Также вычисляется матрица
S
для
h
и
g
.
4 этап.
Для всех вычисленных матриц проводятся последовательные
деления чисел из матриц на числа из факторной базы до тех пор, пока они
не перестанут делиться.
5 этап.
На основе совпадающих элементов в матрицах после деления
составляются уравнения следующим образом. Пусть совпали два числа из
матриц
S
m
и
S
n
. Это может быть одна и та же матрица. Обозначим число
из матрицы
S
m
через
v
, а из матрицы
S
n
через
w
. Пусть в ходе делений на
числа из факторной базы число
v
делилось на числа из
F
1
F
c набором
степеней
D
1
N
|
F
|
, а число
w
— на числа из
F
2
F
с набором степеней
D
2
N
|
F
|
. Теперь представим эти числа через определенные переменные:
v
=
p
deg
1
m
, deg
1 =
t
[
i
] [
j
] [
q
]
−
X
k
:
p
k
2
F
1
(
y
km
∙
D
1
k
)
mod
r,
где
t
[
i
] [
j
] [
q
]
— элемент матрицы
T
,
i, j, q
−
позиция
v
в матрице
S
m
,
D
1
k
—
степень
p
k
в разложении (
t
[
i
] [
j
] [
q
] =
c
1
z
m
+
c
2
(
mod
r
)
, где коэффициенты
c
1
и
c
2
определены, исходя из позиции
i, j, q
, как описано выше). Учитывая
(10) выразим
z
m
:
t
[
i
] [
j
] [
q
] =
c
1
xx
−
1
m
+
c
2
(
mod
r
)
.
В итоге получаем
v
=
p
deg
1
m
, deg
1 =
c
1
xx
−
1
m
+
c
2
−
X
k
:
p
k
2
F
1
(
y
km
D
1
k
)
mod
r.
Аналогичным образом для
w
имеем
w
=
p
deg
2
n
, deg
2 =
c
3
xx
−
1
n
+
c
4
−
X
k
:
p
k
2
F
2
(
y
kn
D
2
k
)
mod
r.
Далее, зная, что
p
m
=
a
x
m
,
p
n
=
a
x
n
, запишем
v
=
a
x
m
∙
deg
1
, w
=
a
x
n
∙
deg
2
.
Учитывая, что
v
=
w
, приравниваем показатели и получаем следующее
уравнение mod
r
:
88 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
