Таблица 2
Эксперимент с трехмерными массивами
Простой модуль
Число различных
показателей
Верхняя
граница (max)
Разность,
Δ
115 351 339
92 916 501
193 444 524
100 528 023
573 402 943
264 890 324
364 095 000
99 204 676
724 321 489
280 872 622
364 095 000
83 222 378
992 421 757
298 719 546
364 095 000
65 375 454
1 324 324 513
369 115 716
443 290 080
74 174 364
1 548 023 513
377 469 238
443 290 080
65 820 842
1 742 359 279
383 145 258
443 290 080
60 144 822
Как следует из табл. 2 число линейно зависимых уравнений стало замет-
но больше, но по-прежнему число линейно независимых соответствует по
порядку значению max.
Преобразование (1) можно распространить на случай массивов произ-
вольной мерности естественным образом:
T
[
i
] [
j
]
. . .
[
w
] =
T
[
i
−
1] [
j
]
. . .
[
w
] +
T
[
i
−
1] [
j
+ 1]
. . .
[
w
] (
mod
p
) ;
1
≤
i
≤
k,
0
≤
j
≤
k
−
1; 0
≤
w
≤
k
;
T
[
i
] [
k
]
. . .
[
w
] =
T
[
i
−
1] [0]
. . .
[
w
] +
T
[
i
−
1] [
k
]
. . .
[
w
] (
mod
p
) ;
1
≤
i
≤
k,
0
≤
w
≤
k.
Обобщенный алгоритм логарифмирования в группе
Z
p
на основе
отображения Ньютона и алгоритма Адлемана.
Поскольку элементами
группы
Z
p
являются числа, воспользуемся возможностью представления чи-
сла в виде произведения простых множителей. Аналогичную технику фак-
торизации использует алгоритм Адлемана [3, 5]. Описанный далее подход
немного видоизменяет этапы этого алгоритма за счет применения приведен-
ной техники сравнения пар в матрице. Неизменным остается использование
факторной базы, способ построения которой несколько другой. Проведем
поэтапное описание алгоритма. Вопрос о таких параметрах алгоритма, как
размер факторной базы, мерность матрицы
S
, рассмотрим несколько позднее,
на этапе теоретических и экспериментальных оценок.
Требуется вычислить
log
a
b
в мультипликативной группе
Z
p
. Обозначим
порядок группы через
n
=
p
−
1
.
1 этап.
Составление факторной базы
F
. Для простых чисел
p
i
, начиная
с 2, определяем порядок
ord (
p
i
)
в группе
Z
p
. Если
ord (
p
i
) =
n
, то доба-
вляем это простое число в факторную базу:
F
=
F
∪
p
i
. Иначе, переходим к
следующему простому числу.
2 этап.
Переход в подгруппу группы
Z
p
простого порядка
r
, в которой
будем вычислять логарифм
h
=
b
n
r
, g
=
a
n
r
, g
1
=
p
n
r
1
, g
2
=
p
n
r
2
, . . . , g
|
F
|
=
p
n
r
|
F
|
;
p
i
2
F,
исходим из того, что
p
i
=
a
x
i
,
b
=
a
x
;
x, x
i
—
неизвестные
,
i
= 1
÷ |
F
|
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2 87
