FRACTAL MAGMAS AND PUBLIC-KEY CRYPTOGRAPHY

Full Text

1. Предварительные сведения
Напомним, что группоидом ⟨U, (∗)⟩ называется множество (носитель) U с заданной на нем един-
ственной бинарной операцией ∗, относительно свойств которой не делается никаких дополнительных
предположений [1]. В англоязычной литературе за группоидами закреплен термин «магма», поэтому
для обозначения группоидов мы будем использовать символ M. Заметим, что частный случай группо-
идов – квазигруппы – находят широкое применение в криптографии [2].
Конечные группоиды, т. е. группоиды с конечным носителем U = {u1, . . . , un}, полностью определя-
ются таблицей Кэли, которая задает значения результата операции на значениях ее аргументов. Общий
вид таблицы Кэли представлен в табл. 1.1.
Структура таблицы Кэли зависит от свойств операции, например, таблица Кэли коммутативной опе-
рации симметрична, а таблица Кэли квазигруппы — это латинский квадрат. Если операция обладает
левым нейтральным элементом el (т.е. el ∗ u = u для любых u ∈ U), то в таблице Кэли ему будет
соответствовать строка u1, u2, . . . , un. То же самое относится и к правому нейтральному элементу и
соответствующему ему столбцу.
В дальнейшем нам будет удобно представлять элементы носителей конечных группоидов значениями
их индексов в некоторой нумерации. Нумерацию элементов будем начинать с единицы, т. е. вместо U =
= {u1, . . . , un} будем записывать 1..n = {1, . . . , n} ⊂ N.
24
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
Таблица 1.1
Общий вид таблицы Кэли
Table 1.1
General view of the Cayley table
∗ u1 . . . uj . . . un
u1 u1 ∗ u1 . . . u1 ∗ uj . . . u1 ∗ un
...
...
. . .
...
. . .
...
ui ui ∗ u1 . . . ui ∗ uj . . . ui ∗ un
...
...
. . .
...
. . .
...
un un ∗ u1 . . . un ∗ uj . . . un ∗ un
В свою очередь в таблице Кэли операции ∗ будем представлять целочисленной матрицей Кэли A =
= (ai,j) порядка n с положительными элементами, определенными правилом
ai,j = k,
где uk = ui ∗ uj , и i, j, k ∈ 1..n ⊂ N.
Понятно, что если на множестве 1..n определить операцию i ⋄ j = ai,j , то группоиды ⟨U, (∗)⟩ и
⟨1..n, (⋄)⟩ будут изоморфны.
Все последующие рассуждения имеют целью разработку математического аппарата для адаптации
схемы открытого распределения ключа шифрования на основе протокола Диффи — Хелмана — Меркла
(Diffie — Hellman — Merkle) [3; 4] применительно к группоидам.
2. Основные результаты
2.1. Фрактальные матрицы и шкалы фрактальных группоидов
Рассмотрим группоид ⟨1..n, (⋄)⟩ с матрицей Кэли A. Все дальнейшие построения опираются на «кло-
нирование» матрицы Кэли операции исходного группоида в качестве подматриц матрицы Кэли операции
группоида вдвое большей мощности.
Дадим следующие определения.
Определение 2.1.1. Диагональным расширением матрицы Кэли A = (ai,j) порядка n будем назы-
вать матрицу A(d) = (a(d)
i,j ) порядка 2n, элементы которой определены правилом
a(d)
i,j =


ai,j , i ∈ 1..n ∧ j ∈ 1..n
ai,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
ai−n,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
ai−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.1)
Определение 2.1.2. Cтроковым расширением матрицы Кэли A = (ai,j) порядка n будем называть
матрицу A(r) = (a(r)
i,j ) порядка 2n, элементы которой определены правилом
a(r)
i,j =


ai,j , i ∈ 1..n ∧ j ∈ 1..n
ai,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
ai−n,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
ai−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.2)
Определение 2.1.3. Столбцевым расширением матрицы Кэли A = (ai,j) порядка n будем называть
матрицу A(c) = (a(c)
i,j ) порядка 2n, элементы которой определены правилом
a(c)
i,j =


ai,j , i ∈ 1..n ∧ j ∈ 1..n
ai,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
ai−n,j , i ∈ n + 1..2n ∧ j ∈ 1..n
ai−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.3)
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 25
Определение 2.1.4. Тривиальным расширением матрицы Кэли A = (ai,j) порядка n будем называть
матрицу A(t) = (a(t)
i,j ) порядка 2n, элементы которой определены правилом
a(t)
i,j =


ai,j , i ∈ 1..n ∧ j ∈ 1..n
ai,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
ai−n,j , i ∈ n + 1..2n ∧ j ∈ 1..n
ai−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.4)
Все определенные выше расширения матрицы Кэли будем называть фрактальными.
Определение 2.1.5. Фрактальным расширением группоида ⟨1..n, (⋄)⟩ с матрицей Кэли A будем на-
зывать любой из группоидов ⟨1..2n, (⋄d)⟩, ⟨1..2n, (⋄r)⟩, ⟨1..2n, (⋄c)⟩, ⟨1..2n, (⋄t)⟩, матрицы Кэли которых
определены как A(d), A(r), A(c), A(t), соответственно. Сами операции ⋄d, ⋄r, ⋄c, ⋄t будем называть фрак-
тальным расширением операции ⋄. При необходимости уточнения конкретного типа расширения будем
говорить о диагональных, строковых, столбцевых и тривиальных расширениях.
Замечание 2.1.1. В качестве примера рассмотрим фрактальное расширение мультипликативного
группоида ⟨1..2, (· mod 3)⟩ с матрицей Кэли
A =
(
1 2
2 1
)
до группоида ⟨1..4, (⋄d)⟩ с матрицей Кэли
A(d) =


1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1


.
Заметим, что группоид ⟨1..2, (·mod 3)⟩ изоморфен группоиду ⟨2{1}, (△)⟩, где 2{1} = {∅, {1}} — булеан
над одноэлементным множеством, △ — симметрическая разность множеств, и 1 ∼ ∅, 2 ∼ {1}.
Нетрудно понять, что группоид ⟨1..4, (⋄d)⟩ изоморфен группоиду ⟨2{1,2}, (△)⟩, где 2{1,2} =
= {∅, {1}, {2}, {1, 2}} и 1 ∼ ∅, 2 ∼ {1}, 3 ∼ {2}, 4 ∼ {1, 2}.
В силу определения, диагональное расширение коммутативного группоида будет коммутативным
группоидом. Если в исходном группоиде имелись левые или/и правые нейтральные элементы, то они
будут сохранять эти свойства и в диагональном расширении. Кроме того, если матрица Кэли исходно-
го группоида являлась латинским квадратом, то латинским квадратом будет и матрица диагонального
расширения.
Также понятно, что группоид ⟨1..n, (⋄)⟩ является подгруппоидом своего диагонального расширения
⟨1..2n, (⋄d)⟩.
Замечание 2.1.2. Матрица Кэли строкового расширения группоида из примера предыдущего заме-
чания 2.1.1 будет иметь вид
A(r) =


1 2 1 2
2 1 2 1
3 4 3 4
4 3 4 3


.
Cтроковое расширение группоида не может быть коммутативным. Свойство нейтрального элемента
в строковом расширении будут сохранять только правые нейтральные элементы. Матрица строкового
расширения не может быть латинским квадратом.
Понятно, что группоиды ⟨1..n, (⋄)⟩ и ⟨n+1..2n, (⋄r)⟩ являются подгруппоидами строкового расширения
⟨1..2n, (⋄r)⟩.
Замечание 2.1.3. Матрица Кэли столбцевого расширения группоида из примера замечания 2.1.1
будет иметь вид
A(c) =


1 2 3 4
2 1 4 3
1 2 3 4
2 1 4 3


.
Столбцевое расширение группоида не может быть коммутативным. Свойство нейтрального элемента
в столбцевом расширении будут сохранять только левые нейтральные элементы. Матрица столбцевого
расширения не может быть латинским квадратом.
26
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
Понятно, что группоиды ⟨1..n, (⋄)⟩ и ⟨n + 1..2n, (⋄c)⟩ являются подгруппоидами столбцевого расши-
рения ⟨1..2n, (⋄c)⟩.
Замечание 2.1.4. Матрица Кэли тривиального расширения группоида из примера замечания 2.1.1
будет иметь вид
A(t) =


1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1


.
Тривиальное расширение коммутативного группоида будет коммутативным. Нейтральные элементы
в тривиальном расширении будут отсутствовать. Матрица тривиального расширения не может быть
латинским квадратом.
Понятно, что группоид ⟨1..n, (⋄)⟩ является подгруппоидом своего тривиального расширения
⟨1..2n, (⋄t)⟩.
Определение 2.1.6. Однородной шкалой фрактальных группоидов M(σ)
k = ⟨1..nk, (⋄σk
)⟩ будем назы-
вать систему группоидов Sσ = {M(σ)
k
}∞
k=0, носители и матрицы Кэли Ak которых определены следующим
условием:
∃σ∀k σ ∈ {d, r, c, t} ∧ k ∈ N ∧ n0 ∈ N ∧ nk = 2nk−1 ∧ Ak = A(σ)
k−1.
Каждый из группоидов M(σ)
k при k ∈ N будем называть фрактальным, его индекс k — местом груп-
поида в заданной шкале, а σ — типом расширения. Группоид M(σ)
0 = ⟨1..nk, (⋄0)⟩, его операцию ⋄0 и
матрицу Кэли A0 будем называть базовыми в заданной шкале. Индексы 0 и σ в обозначениях базо-
вых группоидов, матриц и операций обычно будем опускать. При необходимости уточнения конкретного
типа шкалы будем говорить о диагональных, строковых, столбцевых или тривиальных шкалах.
В общем случае можно рассматривать смешанные шкалы, в которых тип расширений может из-
меняться в пределах шкалы. В данной статье смешанные шкалы не рассматриваются. Поэтому для
простоты изложения однородные шкалы в дальнейшем будем называть просто шкалами.
Замечание 2.1.5. В силу определений каждая шкала Sσ = {M(σ)
k
}∞
k=0 с базовой матрицей Кэли A
порождает при помощи сдвига места h ∈ N шкалу того же типа S′
σ = {M(σ)
k−h
}∞
k=h с базовой матрицей
Кэли Ah.
Рассмотрим последовательности из четырех первых матриц Кэли фрактальных шкал с базовым груп-
поидом M = ⟨{1}, (⋄)⟩, где 1 ⋄ 1 = 1.
1. Диагональные расширения (шкала Sd)
A =
(
1
)
,
A(d)
1 =
(
1 2
2 1
)
,
A(d)
2 =


1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1


,
A(d)
3 =


1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1


.
Нетрудно проверить, что соответствующая шкала группоидов изоморфна шкале групп булеанов
⟨2{1}, (△)⟩, ⟨2{1,2}, (△)⟩, ⟨2{1,2,3}, (△)⟩ с операцией симметрической разности.
2. Строковые расширения (шкала Sr)
A =
(
1
)
,
A(r)
1 =
(
1 1
2 2
)
,
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 27
A(r)
2 =


1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4


,
A(r)
3 =


1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8


.
Построенные расширения матриц Кэли определяют шкалу полугрупп левых нулей (правых еди-
ниц), операция которой ≀ определена правилом ui ≀ uj = ui.
3. Столбцевые расширения (шкала Sc)
A =
(
1
)
,
A(c)
1 =
(
1 2
1 2
)
,
A(c)
2 =


1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4


,
A(c)
3 =


1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

 .
Построенные расширения матриц Кэли определяют шкалу полугрупп правых нулей (левых еди-
ниц), операция которой ≀≀ определена правилом ui ≀ ≀ uj = uj .
4. Тривиальные расширения (шкала St)
A =
(
1
)
,
A(r)
1 =
(
1 1
1 1
)
,
A(r)
2 =


1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1


,
A(r)
3 =


1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1


.
Построенные расширения матриц Кэли определяют шкалу полугрупп с нулевым умножением, опе-
рация которой † определена правилом u1 † uj = u1.
28
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
Замечание 2.1.6. Понятно, что, с одной стороны, каждый из группоидов Mk (матрица Кэли Ak =
= (kai,j)) однозначно определяется по своему месту и базовому группоиду M (матрице A) в заданной
шкале. С другой стороны, для любых значений s, i ∈ 1..ns, j ∈ 1..ns и k > s имеет место равенство
sai,j = kai,j . Это позволяет определять элементы матриц kai,j , исходя только из значений их индексов
и элементов базовой матрицы A.
Сказанное в замечании 2.1.6 позволяет сформулировать простые рекурсивные алгоритмы определе-
ния значений элементов матриц Кэли kai,j фрактальной шкалы в диагональных, строковых, столбцевых
и тривиальных шкалах.
2.1.1. Алгоритм определения элемента матриц Кэли диагональных шкал по его индексам
(диагональный алгоритм) DA(A, i, j)
Входные данные: базовая матрица A = (ai,j); значения индексов i, j элементов фрактальной матрицы.
1. Вычислить порядок базовой матрицы A: n := ord(A).
2. Вычислить место наименьшего фрактального группоида, матрица Кэли которого содержит элемент
с индексами i, j: k := ⌈max(log( i
n), log( j
n))⌉, где ⌈x⌉ — потолок x — наименьшее целое, превосходящее
или равное x.
3. Если i 6 n ∧ j 6 n, то
3.1. Вывести ai,j ,
иначе
3.2. Если i 6 2k−1n ∧ j > 2k−1n, то
3.2.1. Вывести DA(A, i, j − 2k−1n) + 2k−1n,
иначе
3.2.2. Если i > 2k−1n ∧ j 6 2k−1n, то
3.2.2.1. Вывести DA(A, i − 2k−1n, j) + 2k−1n,
иначе
3.2.2.2. Вывести DA(A, i − 2k−1n, j − 2k−1n).
4. Завершить работу.
2.1.2. Алгоритм определения элемента матриц Кэли строковых шкал по его индексам
(строковый алгоритм) RA(A, i, j)
Входные данные: базовая матрица A = (ai,j); значения индексов i, j элементов фрактальной матрицы.
1. Вычислить порядок базовой матрицы A: n := ord(A).
2. Вычислить место наименьшего фрактального группоида, матрица Кэли которого содержит элемент
с индексами i, j: k := ⌈max(log( i
n), log( j
n))⌉.
3. Если i 6 n ∧ j 6 n, то
3.1. Вывести ai,j ,
иначе
3.2. Если i 6 2k−1n ∧ j > 2k−1n, то
3.2.1. Вывести RA(A, i, j − 2k−1n),
иначе
3.2.2. Если i > 2k−1n ∧ j 6 2k−1n, то
3.2.2.1. Вывести RA(A, i − 2k−1n, j) + 2k−1n,
иначе
3.2.2.2. Вывести RA(A, i − 2k−1n, j − 2k−1n) + 2k−1n.
4. Завершить работу.
2.1.3. Алгоритм определения элемента матриц Кэли столбцевых шкал по его индексам
(столбцевой алгоритм) CA(A, i, j)
Входные данные: базовая матрица A = (ai,j); значения индексов i, j элементов фрактальной матрицы.
1. Вычислить порядок базовой матрицы A: n := ord(A).
2. Вычислить место наименьшего фрактального группоида, матрица Кэли которого содержит элемент
с индексами i, j: k := ⌈max(log( i
n), log( j
n))⌉.
3. Если i 6 n ∧ j 6 n, то
3.1. Вывести ai,j ,
иначе
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 29
3.2. Если i 6 2k−1n ∧ j > 2k−1n, то
3.2.1. Вывести CA(A, i, j − 2k−1n) + 2k−1n,
иначе
3.2.2. Если i > 2k−1n ∧ j 6 2k−1n, то
3.2.2.1. Вывести CA(A, i − 2k−1n, j),
иначе
3.2.2.2. Вывести CA(A, i − 2k−1n, j − 2k−1n) + 2k−1n.
4. Завершить работу.
2.1.4. Алгоритм определения элемента матриц Кэли тривиальных шкал по его индексам
(тривиальный алгоритм) TA(A, i, j)
Входные данные: базовая матрица A = (ai,j); значения индексов i, j элементов фрактальной матрицы.
1. Вычислить порядок базовой матрицы A: n := ord(A).
2. Вычислить место наименьшего фрактального группоида, матрица Кэли которого содержит элемент
с индексами i, j: k := ⌈max(log( i
n), log( j
n))⌉.
3. Если i 6 n ∧ j 6 n, то
3.1. Вывести ai,j ,
иначе
3.2. Если i 6 2k−1n ∧ j > 2k−1n, то
3.2.1. Вывести TA(A, i, j − 2k−1n),
иначе
3.2.2. Если i > 2k−1n ∧ j 6 2k−1n, то
3.2.2.1. Вывести TA(A, i − 2k−1n, j),
иначе
3.2.2.2. Вывести TA(A, i − 2k−1n, j − 2k−1n).
4. Завершить работу.
2.2. Полугруппы бинарных операций и матриц Кэли
Для обозначения результатов бинарных операций на множестве U будем использовать как инфиксное
u1 ∗u2, так и префиксное ϕ∗(u1, u2) обозначения. Множество бинарных операций будем обозначать UU2 .
Следуя [5], дадим следующее
Определение 2.2.1. Композицией бинарных операций ϕ∗(u1, u2) и ϕ⋆(u1, u2) будем называть бинар-
ную операцию ϕ∗ ◦ ϕ⋆(u1, u2), определяемую правилом
u3 = ϕ∗ ◦ ϕ⋆(u1, u2) = ϕ⋆(ϕ∗(u1, u2), u2) = (u1 ∗ u2) ⋆ u2.
В [5] было показано, что множество UU2 замкнуто относительно операции ◦, а сама эта операция
ассоциативна. Кроме того, она обладает нейтральным элементом — операцией полугруппы левых нулей
(правых единиц) ≀, которая определена правилом u1 ≀ u2 = u1. Действительно,
(u1 ≀ u2) ∗ u2 = u1 ∗ u2 = (u1 ∗ u2) ≀ u2.
Таким образом, алгебра ⟨UU2
, (◦)⟩ является полугруппой с единицей ϕ≀, или моноидом.
Стандартным образом определим положительную степень m ∈ N бинарной операции ϕ∗
ϕ1
∗ = ϕ∗,
ϕm+1
∗ = ϕm∗
◦ ϕ∗.
(2.5)
Рассмотрим пару группоидов ⟨1..n, (⋄)⟩ и ⟨1..n, (◃)⟩ с матрицами Кэли A = (ai,j) и B = (bi,j), соот-
ветственно.
Нетрудно понять, что т. к. i ⋄ j = ai,j и i ◃ j = bi,j , то
ϕ⋄ ◦ ϕ◃(i, j) = ϕ◃(ϕ⋄(i, j), j) = (i ⋄ j) ◃ j = ai,j ◃ j = bai;j ,j ,
т. е. элементы матрицы Кэли C = (ci,j) композиции операций ϕ⋄(u1, u2) и ϕ◃(u1, u2) определяются пра-
вилом
ci,j = bai;j ,j . (2.6)
В частности, элементы матрицы Кэли A2 = (a2
i,j) операции ϕ2
⋄ — квадрата операции ⋄ — имеют вид
a2
i,j = aai;j ,j . (2.7)
30
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
Определение 2.2.2. Произведением матриц Кэли A = (ai,j) и B = (bi,j) одного порядка n будем
называть матрицу C = (ci,j) порядка n, элементы которой определены в соответствии с (2.6). Произве-
дение матриц будем обозначать A•B. Стандартным образом определим положительную степень m ∈ N
матрицы A
A1 = A,
Am+1 = Am • A.
(2.8)
Замечание 2.2.1.
Обозначим множество бинарных операций на конечном множестве 1..n как (1..n)(1..n)2 и рассмотрим
полугруппу ⟨(1..n)(1..n)2
, (◦)⟩.
Обозначим множество квадратных матриц (Кэли) A = (ai,j) порядка n с элементами ai,j ∈ 1..n как
K(1..n) и рассмотрим полугруппу ⟨K(1..n), (•)⟩.
Нетрудно понять, что полугруппы ⟨(1..n)(1..n)2
, (◦)⟩ и ⟨K(1..n), (•)⟩ изоморфны.
2.3. Свойства фрактальных матриц
Рассмотрим две базовые матрицы Кэли A = (ai,j) и B = (bi,j) одного порядка n, а также их фрак-
тальные расширения A(d), A(r), A(c), A(t), B(d), B(r), B(c), B(t).
2.3.1. Произведение расширений A(d) • B(d)
Рассмотрим произведение A(d) • B(d). В соответствии с (2.1), (2.6) и учетом того, что ai,j , bi,j ∈ 1..n
и ai,j + n, bi,j + n ∈ n + 1..2n, при i, j ∈ 1..n, получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(d) • b(d)
i,j = b(d)
a(d)
i;j ,j
= b(d)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(d) • b(d)
i,j = b(d)
a(d)
i;j ,j
= b(d)
ai;j−n+n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(d) • b(d)
i,j = b(d)
a(d)
i;j ,j
= b(d)
ai−n;j+n,j = bai−n;j ,j + n.
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(d) • b(d)
i,j = b(d)
a(d)
i;j ,j
= b(d)
ai−n;j−n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(d) • B(d) = (a(d) • b(d)
i,j), где
a(d) • b(d)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.9)
2.3.2. Произведение расширений A(d) • B(r)
Рассмотрим произведение A(d) •B(r). В соответствии с (2.1), (2.2), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(d) • b(r)
i,j = b(r)
a(d)
i;j ,j
= b(r)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(d) • b(r)
i,j = b(r)
a(d)
i;j ,j
= b(r)
ai;j−n+n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(d) • b(r)
i,j = b(r)
a(d)
i;j ,j
= b(r)
ai−n;j+n,j = bai−n;j,j + n.
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 31
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(d) • b(r)
i,j = b(r)
a(d)
i;j ,j
= b(r)
ai−n;j−n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(d) • B(r) = (a(d) • b(r)
i,j), где
a(d) • b(r)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.10)
2.3.3. Произведение расширений A(r) • B(d)
Рассмотрим произведение A(r) •B(d). В соответствии с (2.1), (2.2), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(r) • b(d)
i,j = b(d)
a(r)
i;j ,j
= b(d)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(r) • b(d)
i,j = b(d)
a(r)
i;j ,j
= b(d)
ai;j−n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(r) • b(d)
i,j = b(d)
a(r)
i;j ,j
= b(d)
ai−n;j+n,j = bai−n;j ,j + n.
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(r) • b(d)
i,j = b(d)
a(r)
i;j ,j
= b(d)
ai−n;j−n+n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(r) • B(d) = (a(r) • b(d)
i,j), где
a(r) • b(d)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.11)
2.3.4. Произведение расширений A(d) • B(c)
Рассмотрим произведение A(d) •B(c). В соответствии с (2.1), (2.3), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(d) • b(c)
i,j = b(c)
a(d)
i;j ,j
= b(c)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(d) • b(c)
i,j = b(c)
a(d)
i;j ,j
= b(c)
ai;j−n+n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(d) • b(c)
i,j = b(c)
a(d)
i;j ,j
= b(c)
ai−n;j+n,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(d) • b(c)
i,j = b(c)
a(d)
i;j ,j
= b(c)
ai−n;j−n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(d) • B(c) = (a(d) • b(c)
i,j), где
a(d) • b(c)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j ,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.12)
32
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
2.3.5. Произведение расширений A(c) • B(d)
Рассмотрим произведение A(c) •B(d). В соответствии с (2.1), (2.3), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(c) • b(d)
i,j = b(d)
a(c)
i;j ,j
= b(d)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(c) • b(d)
i,j = b(d)
a(c)
i;j ,j
= b(d)
ai;j−n+n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(c) • b(d)
i,j = b(d)
a(c)
i;j ,j
= b(d)
ai−n;j ,j = bai−n;j ,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(c) • b(d)
i,j = b(d)
a(c)
i;j ,j
= b(d)
ai−n;j−n+n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(c) • B(d) = (a(c) • b(d)
i,j), где
a(c) • b(d)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.13)
2.3.6. Произведение расширений A(d) • B(t)
Рассмотрим произведение A(d) •B(r). В соответствии с (2.1), (2.4), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(d) • b(t)
i,j = b(t)
a(d)
i;j ,j
= b(t)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(d) • b(t)
i,j = b(t)
a(d)
i;j ,j
= b(t)
ai;j−n+n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(d) • b(t)
i,j = b(t)
a(d)
i;j ,j
= b(t)
ai−n;j+n,j = bai−n;j ,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(d) • b(t)
i,j = b(t)
a(d)
i;j ,j
= b(t)
ai−n;j−n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(d) • B(t) = (a(d) • b(t)
i,j), где
a(d) • b(t)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.14)
2.3.7. Произведение расширений A(t) • B(d)
Рассмотрим произведение A(t) •B(d). В соответствии с (2.1), (2.4), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(t) • b(d)
i,j = b(d)
a(t)
i;j ,j
= b(d)
ai;j ,j = bai;j ,j .
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 33
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(t) • b(d)
i,j = b(d)
a(t)
i;j ,j
= b(d)
ai;j−n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(t) • b(d)
i,j = b(d)
a(t)
i;j ,j
= b(d)
ai−n;j ,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(t) • b(d)
i,j = b(d)
a(t)
i;j ,j
= b(d)
ai−n;j−n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(t) • B(d) = (a(c) • b(d)
i,j), где
a(r) • b(d)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.15)
2.3.8. Произведение расширений A(r) • B(r)
Рассмотрим произведение A(r) •B(r). В соответствии с (2.2), (2.6), как и ранее, получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(r) • b(r)
i,j = b(r)
a(r)
i;j ,j
= b(r)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(r) • b(r)
i,j = b(r)
a(r)
i;j ,j
= b(r)
ai;j−n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(r) • b(r)
i,j = b(r)
a(r)
i;j ,j
= b(r)
ai−n;j+n,j = bai−n;j,j + n.
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(r) • b(r)
i,j = b(d)
a(r)
i;j ,j
= b(r)
ai−n;j−n+n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(r) • B(d) = (a(r) • b(d)
i,j), где
a(r) • b(r)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j ,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.16)
2.3.9. Произведение расширений A(r) • B(c)
Рассмотрим произведение A(r) •B(c). В соответствии с (2.2), (2.3), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(r) • b(c)
i,j = b(c)
a(r)
i;j ,j
= b(c)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(r) • b(c)
i,j = b(c)
a(r)
i;j ,j
= b(c)
ai;j−n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(r) • b(c)
i,j = b(c)
a(r)
i;j ,j
= b(c)
ai−n;j+n,j = bai−n;j,j .
34
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(r) • b(c)
i,j = b(c)
a(r)
i;j ,j
= b(c)
ai−n;j−n+n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(r) • B(c) = (a(d) • b(c)
i,j), где
a(d) • b(c)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j ,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.17)
2.3.10. Произведение расширений A(c) • B(r)
Рассмотрим произведение A(c) •B(r). В соответствии с (2.2), (2.3), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(c) • b(r)
i,j = b(r)
a(c)
i;j ,j
= b(r)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(c) • b(r)
i,j = b(r)
a(c)
i;j ,j
= b(r)
ai;j−n+n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(c) • b(r)
i,j = b(r)
a(c)
i;j ,j
= b(r)
ai−n;j,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(c) • b(r)
i,j = b(r)
a(c)
i;j ,j
= b(r)
ai−n;j−n+n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(c) • B(r) = (a(c) • b(r)
i,j), где
a(c) • b(r)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.18)
2.3.11. Произведение расширений A(r) • B(t)
Рассмотрим произведение A(r) •B(t). В соответствии с (2.1), (2.4), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(r) • b(t)
i,j = b(t)
a(r)
i;j ,j
= b(t)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(r) • b(t)
i,j = b(t)
a(r)
i;j ,j
= b(t)
ai;j−n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(r) • b(t)
i,j = b(t)
a(r)
i;j ,j
= b(t)
ai−n;j+n,j = bai−n;j ,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(r) • b(t)
i,j = b(t)
a(r)
i;j ,j
= b(t)
ai−n;j−n+n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(d) • B(t) = (a(d) • b(t)
i,j), где
a(r) • b(t)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.19)
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 35
2.3.12. Произведение расширений A(t) • B(r)
Рассмотрим произведение A(t) •B(r). В соответствии с (2.2), (2.4), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(t) • b(r)
i,j = b(r)
a(t)
i;j ,j
= b(r)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(t) • b(r)
i,j = b(r)
a(t)
i;j ,j
= b(r)
ai;j−n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(t) • b(r)
i,j = b(r)
a(t)
i;j ,j
= b(r)
ai−n;j,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(t) • b(r)
i,j = b(r)
a(t)
i;j ,j
= b(r)
ai−n;j−n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(t) • B(r) = (a(t) • b(r)
i,j), где
a(t) • b(r)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.20)
2.3.13. Произведение расширений A(c) • B(c)
Рассмотрим произведение A(c) •B(c). В соответствии с (2.3), (2.6), как и ранее, получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(c) • b(c)
i,j = b(c)
a(c)
i;j ,j
= b(c)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(c) • b(c)
i,j = b(c)
a(c)
i;j ,j
= b(c)
ai;j−n+n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(c) • b(c)
i,j = b(c)
a(c)
i;j ,j
= b(c)
ai−n;j,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(c) • b(c)
i,j = b(c)
a(c)
i;j ,j
= b(c)
ai−n;j−n+n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(c) • B(c) = (a(c) • b(c)
i,j), где
a(c) • b(c)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.21)
2.3.14. Произведение расширений A(c) • B(t)
Рассмотрим произведение A(c) • B(t). В соответствии с (2.3), (2.4), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(c) • b(t)
i,j = b(t)
a(c)
i;j ,j
= b(t)
ai;j ,j = bai;j ,j .
36
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(c) • b(t)
i,j = b(t)
a(c)
i;j ,j
= b(t)
ai;j−n+n,j = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(c) • b(t)
i,j = b(t)
a(c)
i;j ,j
= b(t)
ai−n;j ,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(c) • b(t)
i,j = b(c)
a(c)
i;j ,j
= b(t)
ai−n;j−n+n,j = bai−n;j−n,j−n.
Таким образом, имеет место равенство A(c) • B(t) = (a(c) • b(t)
i,j), где
a(c) • b(t)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.22)
2.3.15. Произведение расширений A(t) • B(c)
Рассмотрим произведение A(t) • B(c). В соответствии с (2.3), (2.4), (2.6), как и ранее, получаем сле-
дующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a(t) • b(c)
i,j = b(c)
a(t)
i;j ,j
= b(c)
ai;j ,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a(t) • b(c)
i,j = b(c)
a(t)
i;j ,j
= b(c)
ai;j−n,j = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a(t) • b(c)
i,j = b(c)
a(t)
i;j ,j
= b(c)
ai−n;j,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a(t) • b(c)
i,j = b(c)
a(t)
i;j ,j
= b(c)
ai−n;j−n,j = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство A(t) • B(c) = (a(t) • b(c)
i,j), где
a(t) • b(c)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j ,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.23)
2.3.16. Расширение произведения (A • B)(d)
Рассмотрим диагональное расширение произведения матриц (A•B)(d). В соответствии с (2.2) и (2.6),
получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a • b(d)
i,j = a • bi,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a • b(d)
i,j = a • bi,j−n + n = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a • b(d)
i,j = a • bi−n,j + n = bai−n;j,j + n.
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 37
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a • b(d)
i,j = a • bi−n,j−n = bai−n;j−n,j−n.
Таким образом, имеет место равенство (A • B)(d) = (a • b(d)
i,j ), где
a • b(d)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.24)
2.3.17. Расширение произведения (A • B)(r)
Рассмотрим строковое расширение произведения матриц (A • B)(r). В соответствии с (2.2) и (2.6),
получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a • b(r)
i,j = a • bi,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a • b(r)
i,j = a • bi,j−n = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a • b(r)
i,j = a • bi−n,j + n = bai−n;j ,j + n.
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a • b(r)
i,j = a • bi−n,j−n + n = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство (A • B)(r) = (a • b(r)
i,j ), где
a • b(r)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j + n , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.25)
2.3.18. Расширение произведения (A • B)(c)
Рассмотрим столбцевое расширение произведения матриц (A • B)(c). В соответствии с (2.3) и (2.6),
получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a • b(c)
i,j = a • bi,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a • b(c)
i,j = a • bi,j−n + n = bai;j−n,j−n + n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a • b(c)
i,j = a • bi−n,j = bai−n;j,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a • b(c)
i,j = a • bi−n,j−n + n = bai−n;j−n,j−n + n.
Таким образом, имеет место равенство (A • B)(c) = (a • b(c)
i,j ), где
a • b(c)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n + n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n + n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.26)
38
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
2.3.19. Расширение произведения (A • B)(t)
Рассмотрим тривиальное расширение произведения матриц (A•B)(t). В соответствии с (2.4) и (2.6),
получаем следующее.
1. Если i ∈ 1..n ∧ j ∈ 1..n, то
a • b(c)
i,j = a • bi,j = bai;j ,j .
2. Если i ∈ 1..n ∧ j ∈ n + 1..2n, то
a • b(t)
i,j = a • bi,j−n = bai;j−n,j−n.
3. Если i ∈ n + 1..2n ∧ j ∈ 1..n, то
a • b(t)
i,j = a • bi−n,j = bai−n;j ,j .
4. Если i ∈ n + 1..2n ∧ j ∈ n + 1..2n, то
a • b(t)
i,j = a • bi−n,j−n = bai−n;j−n,j−n.
Таким образом, имеет место равенство (A • B)(t) = (a • b(t)
i,j ), где
a • b(t)
i,j =


bai;j ,j , i ∈ 1..n ∧ j ∈ 1..n
bai;j−n,j−n , i ∈ 1..n ∧ j ∈ n + 1..2n
bai−n;j,j , i ∈ n + 1..2n ∧ j ∈ 1..n
bai−n;j−n,j−n , i ∈ n + 1..2n ∧ j ∈ n + 1..2n.
(2.27)
Из (2.9) и (2.27) следует
Утверждение 2.3.1. Пусть A = (ai,j) и B = (bi,j) — матрицы Кэли одного порядка n. Тогда
A(d) • B(d) = A(r) • B(r) = (A • B)(r),
A(d) • B(r) = A(r) • B(d) = (A • B)(d),
A(d) • B(c) = A(t) • B(d) = A(r) • B(c) = A(c) • B(r) = A(c) • B(c) = A(t) • B(c) = (A • B)(c),
A(c) • B(d) = A(d) • B(t) = A(r) • B(t) = A(t) • B(r) = A(c) • B(t) = (A • B)(t).
Из утверждения 2.3.1 следует
Утверждение 2.3.2. Пусть A = (ai,j) — матрица Кэли и m ∈ N. Тогда степени фрактальных
расширений матрицы Кэли A удовлетворяют следующим равенствам:
(A(d))m = (Am)(r), m = 2s ∧ s ∈ N;
(A(d))m = (Am)(d), m = 2s − 1 ∧ s ∈ N;
(A(r))m = (Am)(r), m ∈ N;
(A(c))m = (Am)(c), m ∈ N;
(A(t))m = (Am)(t), m ∈ N.
Из утверждений 2.3.1, 2.3.2 и замечания 2.1.5 следует
Утверждение 2.3.3. Пусть Sσ = {M(σ)
k
}∞
k=1– шкала фрактальных группоидов M(σ)
k = ⟨1..nk, (⋄k)⟩
с матрицами Кэли Ak и базовой матрицей A. Тогда семейство группоидов Mm
k = ⟨1..nk, (ϕm⋄
k )⟩, при
фиксированном значении m ∈ N, образует шкалу группоидов Sm
σ′ с базовой матрицей Am, при этом тип
шкалы Sm
σ′ будет определяться следующими условиями:
σ′ = r, σ = d ∧ m = 2s ∧ s ∈ N;
σ′ = d, σ = d ∧ m = 2s − 1 ∧ s ∈ N;
σ′ = σ, σ ∈ {r, c, t} ∧ m ∈ N.
Замечание 2.3.1.
Утверждение 2.3.3 фактически означает, что для представления матрицами Кэли степеней фрак-
тальных расширений операции базового группоида нет необходимости вычислять степени матриц Кэли
этих расширений, а достаточно вычислить соответствующую степень матрицы Кэли базовой операции
и затем построить матрицу нужного расширения.
С учетом алгоритмов 2.1.1–2.1.4 это позволяет получить существенный выигрыш при вычислении
результатов операций во фрактальных шкалах группоидов. Напомним, что порядок матрицы Кэли A(σ)
k
фрактального группоида зависит от его места k в шкале и порядка n = ord(A) базовой матрицы Кэли,
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 39
как 2kn, т. е. экспоненциально от k. В свою очередь глубина рекурсии алгоритмов 2.1.1–2.1.4 не пре-
вышает k.
В качестве примера рассмотрим конечную последовательность степеней матриц Кэли (A(σ)
k )m фрак-
тальных шкал, построенных для базового группоида со случайной матрицей Кэли
A =


2 2 1
1 3 3
2 1 1

.
1. Степени базовой матрицы (Am, m ∈ 1..4)
A =


2 2 1
1 3 3
2 1 1

, A2 =


1 3 1
2 1 1
1 2 1

, A3 =


2 1 1
1 2 1
2 3 1

, A4 =


1 2 1
2 3 1
1 1 1


.
2. Степени диагонального расширения ((A(d)
1 )m, m ∈ 1..4)
(A(d)
1 ) =


2 2 1 5 5 4
1 3 3 4 6 6
2 1 1 5 4 4
5 5 4 2 2 1
4 6 6 1 3 3
5 4 4 2 1 1


, (A(d)
1 )2 =


1 3 1 1 3 1
2 1 1 2 1 1
1 2 1 1 2 1
4 6 4 4 6 4
5 4 4 5 4 4
4 5 4 4 5 4


,
(A(d)
1 )3 =


2 1 1 5 4 4
1 2 1 4 5 4
2 3 1 5 6 4
5 4 4 2 1 1
4 5 4 1 2 1
5 6 4 2 3 1


, (A(d)
1 )4 =


1 2 1 1 2 1
2 3 1 2 3 1
1 1 1 1 1 1
4 5 4 4 5 4
5 6 4 5 6 1
4 4 4 4 4 4


.
3. Степени диагонального расширения ((A(d)
2 )m, m ∈ 1..4)
(A(d)
2 ) =


2 2 1 5 5 4 8 8 7 11 11 10
1 3 3 4 6 6 7 9 9 10 12 12
2 1 1 5 4 4 8 7 7 11 10 10
5 5 4 2 2 1 11 11 10 8 8 7
4 6 6 1 3 3 10 12 12 7 9 9
5 4 4 2 1 1 11 10 10 8 7 7
8 8 7 11 11 10 2 2 1 5 5 4
7 9 9 10 12 12 1 3 3 4 6 6
8 7 7 11 10 10 2 1 1 5 4 4
11 11 10 8 8 7 5 5 4 2 2 1
10 12 12 7 9 9 4 6 6 1 3 3
11 10 10 8 7 7 5 4 4 2 1 1


,
(A(d)
2 )2 =


1 3 1 1 3 1 1 3 1 1 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
4 4 4 4 4 4 4 4 4 4 4 4
5 4 4 5 4 4 5 4 4 5 4 4
4 5 4 4 5 4 4 5 4 4 5 4
7 9 7 7 9 7 7 9 7 7 9 7
8 7 7 8 7 7 8 7 7 8 7 7
7 8 7 7 8 7 7 8 7 7 8 7
10 12 10 10 12 10 10 12 10 10 12 10
11 10 10 11 10 10 11 10 10 11 10 10
10 11 10 10 11 10 10 11 10 10 11 10


,
40
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
(A(d)
2 )3 =


2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
5 4 4 2 1 1 11 10 10 8 7 7
4 5 4 1 2 1 10 11 10 7 8 7
5 6 4 2 3 1 11 12 10 8 9 7
8 7 7 11 10 10 2 1 1 5 4 4
7 8 7 10 11 10 1 2 1 4 5 4
8 9 7 11 12 10 2 3 1 5 6 4
11 10 10 8 7 7 5 4 4 2 1 1
10 11 10 7 8 7 4 5 4 1 2 1
11 12 10 8 9 7 5 6 4 2 3 1


,
(A(d)
2 )4 =


1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
1 1 1 1 1 1 1 1 1 1 2 1
4 5 4 4 5 4 4 5 4 4 5 4
5 6 4 5 6 4 5 6 4 5 6 4
4 4 4 4 4 4 4 4 4 4 4 4
7 8 7 7 8 7 7 8 7 7 8 7
8 9 7 8 9 7 8 9 7 8 9 7
7 7 7 7 7 7 7 7 7 7 7 7
10 11 10 10 11 10 10 11 10 10 11 10
11 12 10 11 12 10 11 12 10 11 12 10
10 10 10 10 10 10 10 10 10 10 10 10


.
4. Степени строкового расширения ((A(r)
1 )m, m ∈ 1..4)
(A(r)
1 ) =


2 2 1 2 2 1
1 3 3 1 3 3
2 1 1 2 1 1
5 5 4 5 5 4
4 6 6 4 6 6
5 4 4 5 4 4


, (A(r)
1 )2 =


1 3 1 1 3 1
2 1 1 2 1 1
1 2 1 1 2 1
4 6 4 4 6 4
5 4 4 5 4 4
4 5 4 4 5 4


,
(A(r)
1 )3 =


2 1 1 2 1 1
1 2 1 1 2 1
2 3 1 2 3 1
5 4 4 5 4 4
4 5 4 5 4 4
5 6 4 5 6 4


, (A(r)
1 )4 =


1 2 1 1 2 1
2 3 1 2 3 1
1 1 1 1 1 1
4 5 4 4 5 4
5 6 4 5 6 4
4 4 4 4 4 4


.
5. Степени строкового расширения ((A(r)
2 )m, m ∈ 1..4)
(A(r)
2 ) =


2 2 1 2 2 1 2 2 1 2 2 1
1 3 3 1 3 3 1 3 3 1 3 3
2 1 1 2 1 1 2 1 1 2 1 1
5 5 4 5 5 4 5 5 4 5 5 4
4 6 6 4 6 6 4 6 6 4 6 6
5 4 4 5 4 4 5 4 4 5 4 4
8 8 7 8 8 7 8 8 7 8 8 7
7 9 9 7 9 9 7 9 9 7 9 9
8 7 7 8 7 7 8 7 7 8 7 7
11 11 10 11 11 10 11 11 10 11 11 10
10 12 12 10 12 12 10 12 12 10 12 12
11 10 10 11 10 10 11 10 10 11 10 10


,
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 41
(A(r)
2 )2 =


1 3 1 1 3 1 1 3 1 1 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
4 4 4 4 4 4 4 4 4 4 4 4
5 4 4 5 4 4 5 4 4 5 4 4
4 5 4 4 5 4 4 5 4 4 5 4
7 9 7 7 9 7 7 9 7 7 9 7
8 7 7 8 7 7 8 7 7 8 7 7
7 8 7 7 8 7 7 8 7 7 8 7
10 12 10 10 12 10 10 12 10 10 12 10
11 10 10 11 10 10 11 10 10 11 10 10
10 11 10 10 11 10 10 11 10 10 11 10


,
(A(r)
2 )3 =


2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
5 4 4 5 4 4 5 4 4 5 4 4
4 5 4 4 5 4 4 5 4 4 5 4
5 6 4 5 6 4 5 6 4 5 6 4
8 7 7 8 7 7 8 7 7 8 7 7
7 8 7 7 8 7 7 8 7 7 8 7
8 9 7 8 9 7 8 9 7 8 9 7
11 10 10 11 10 10 11 10 10 11 10 10
10 11 10 10 11 10 10 11 10 10 11 10
11 12 10 11 12 10 11 12 10 11 12 10


,
(A(r)
2 )4 =


1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
1 1 1 1 1 1 1 1 1 1 2 1
4 5 4 4 5 4 4 5 4 4 5 4
5 6 4 5 6 4 5 6 4 5 6 4
4 4 4 4 4 4 4 4 4 4 4 4
7 8 7 7 8 7 7 8 7 7 8 7
8 9 7 8 9 7 8 9 7 8 9 7
7 7 7 7 7 7 7 7 7 7 7 7
10 11 10 10 11 10 10 11 10 10 11 10
11 12 10 11 12 10 11 12 10 11 12 10
10 10 10 10 10 10 10 10 10 10 10 10


.
6. Степени столбцевого расширения ((A(c)
1 )m, m ∈ 1..4)
(A(c)
1 ) =

 2
2
1
5
5
4
1 3 3 4 6 6
2 1 1 5 4 4
2 2 1 5 5 4
1 3 3 4 6 6
2 1 1 5 4 4


, (A(c)
1 )2 =


1 3 1 4 6 4
2 1 1 5 4 4
1 2 1 4 5 4
1 3 1 4 6 4
2 1 1 5 4 4
1 2 1 4 5 4


,
(A(c)
1 )3 =


2 1 1 5 4 4
1 2 1 4 5 4
2 3 1 5 6 4
2 1 1 5 4 4
1 2 1 4 5 4
2 3 1 5 6 4


, (A(c)
1 )4 =


1 2 1 4 5 4
2 3 1 5 6 4
1 1 1 4 4 4
1 2 1 4 5 4
2 3 1 5 6 4
1 1 1 4 4 4


.
42
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
7. Степени столбцевого расширения ((A(t)
2 )m, m ∈ 1..4)
(A(c)
2 ) =


2 2 1 5 5 4 8 8 7 11 11 10
1 3 3 4 6 6 7 9 9 10 12 12
2 1 1 5 4 4 8 7 7 11 10 10
2 2 1 5 5 4 8 8 7 11 11 10
1 3 3 4 6 6 7 9 9 10 12 12
2 1 1 5 4 4 8 7 7 11 10 10
2 2 1 5 5 4 8 8 7 11 11 10
1 3 3 4 6 6 7 9 9 10 12 12
2 1 1 5 4 4 8 7 7 11 10 10
2 2 1 5 5 4 8 8 7 11 11 10
1 3 3 4 6 6 7 9 9 10 12 12
2 1 1 5 4 4 8 7 7 11 10 10


,
(A(c)
2 )2 =


1 3 1 4 6 4 7 9 7 10 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
1 3 1 4 6 4 7 9 7 10 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
1 3 1 4 6 4 7 9 7 10 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
1 3 1 4 6 4 7 9 7 10 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10


,
(A(c)
2 )3 =


2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
2 1 1 5 4 4 8 7 7 11 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10


,
(A(c)
2 )4 =


1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
1 1 1 4 4 4 7 7 7 10 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
1 1 1 4 4 4 7 7 7 10 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
1 1 1 4 4 4 7 7 7 10 10 10
1 2 1 4 5 4 7 8 7 10 11 10
2 3 1 5 6 4 8 9 7 11 12 10
1 1 1 4 4 4 7 7 7 10 10 10


.
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 43
8. Степени тривиального расширения ((A(t)
1 )m, m ∈ 1..4)
(A(t)
1 ) =


2 2 1 2 2 1
1 3 3 1 3 3
2 1 1 2 1 1
2 2 1 2 2 1
1 3 3 1 3 3
2 1 1 2 1 1


, (A(t)
1 )2 =


1 3 1 1 3 1
2 1 1 2 1 1
1 2 1 1 2 1
1 3 1 1 3 1
2 1 1 2 1 1
1 2 1 1 2 1


,
(A(t)
1 )3 =


2 1 1 2 1 1
1 2 1 1 2 1
2 3 1 2 3 1
2 1 1 2 1 1
1 2 1 1 2 1
2 3 1 2 3 1


, (A(t)
1 )4 =


1 2 1 1 2 1
2 3 1 2 3 1
1 1 1 1 1 1
1 2 1 1 2 1
2 3 1 2 3 1
1 1 1 1 1 1


.
9. Степени тривиального расширения ((A(t)
2 )m, m ∈ 1..4)
(A(t)
2 ) =


2 2 1 2 2 1 2 2 1 2 2 1
1 3 3 1 3 3 1 3 3 1 3 3
2 1 1 2 1 1 2 1 1 2 1 1
2 2 1 2 2 1 2 2 1 2 2 1
1 3 3 1 3 3 1 3 3 1 3 3
2 1 1 2 1 1 2 1 1 2 1 1
2 2 1 2 2 1 2 2 1 2 2 1
1 3 3 1 3 3 1 3 3 1 3 3
2 1 1 2 1 1 2 1 1 2 1 1
2 2 1 2 2 1 2 2 1 2 2 1
1 3 3 1 3 3 1 3 3 1 3 3
2 1 1 2 1 1 2 1 1 2 1 1


,
(A(t)
2 )2 =


1 3 1 1 3 1 1 3 1 1 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
1 3 1 1 3 1 1 3 1 1 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
1 3 1 1 3 1 1 3 1 1 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
1 3 1 1 3 1 1 3 1 1 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1


,
(A(t)
2 )3 =


2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1


,
44
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
(A(t)
2 )4 =


1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
1 1 1 1 1 1 1 1 1 1 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
1 1 1 1 1 1 1 1 1 1 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
1 1 1 1 1 1 1 1 1 1 1 1
1 2 1 1 2 1 1 2 1 1 2 1
2 3 1 2 3 1 2 3 1 2 3 1
1 1 1 1 1 1 1 1 1 1 1 1


·
2.4. Циклические полугруппы фрактальных расширений и криптография
с открытым ключом
Рассмотрим базовый группоид M = ⟨1..n, (⋄)⟩ с матрицей Кэли A = (ai,j) и некоторую шкалу его
фрактальных расширений Sσ = {M(σ)
k
}∞
k=0. Зафиксируем место k0 в этой шкале и соответствующий ему
группоид M(σ)
k0
= ⟨1..nk0 , (⋄σk
0
)⟩. Для упрощения записи будем обозначать его как M∗ = ⟨1..N, (∗)⟩, где
N = 2k0n и ϕ∗ = ϕ⋄k
0
. Матрицу Кэли операции ∗ обозначим как A = (αi,j).
В дальнейшем нас будет интересовать циклическая полугруппа степеней операции
∗ — ⟨{ϕm∗
}∞
m=1, (◦)⟩ ⊂ ⟨UU2
, (◦)⟩.
В [5] была предложена следующая модификация протокола Диффи — Хелмана — Меркла (DHM)
открытого распределения ключей шифрования на основе группоидов.
Протокол Диффи — Хелмана — Меркла на группоидах DHM-M
1. Опубликованные общедоступные значения: группоид ⟨U, (∗)⟩; p ∈ N; последовательность значений
аргументов {(ui
1, ui
2)}p
i=1, ui
1, ui
2
∈ U, i ∈ 1..p.
2. Вычисляемые значения на стороне A: операция ϕ⋆ = ϕm∗
– m-я степень операции ∗, последова-
тельность значений результатов операции {ϕ⋆(ui
1, ui
2)}p
i=1. Значения, передаваемые по открытому
каналу связи: {ϕ⋆(ui
1, ui
2)}p
i=1. Секретное значение: m.
3. Вычисляемые значения на стороне B: операция ϕ⋆′ = ϕm
′
∗ – m′-я степень операции ∗, последова-
тельность значений результатов операции {ϕ⋆′ (ui
1, ui
2)}p
i=1. Значения, передаваемые по открытому
каналу связи: {ϕ⋆′ (ui
1, ui
2)}p
i=1. Секретное значение: m′.
4. Вычисляемое значение секретного ключа на стороне A: K = {ϕ⋆(ϕ⋆′ (ui
1, ui
2), ui
2)}p
i=1.
5. Вычисляемое значение секретного ключа на стороне B: K = {ϕ⋆′ (ϕ⋆(ui
1, ui
2), ui
2)}p
i=1.
6. Значения, известные третьей стороне C: ⟨U, (∗)⟩, p, {(ui
1, ui
2)}p
i=1, {ϕ⋆m(ui
1, ui
2)}p
i=1, {ϕ⋆m
′ (ui
1, ui
2)}p
i=1.
Так как в силу ассоциативности операции ◦ имеет место правило степеней
ϕ⋆ ◦ ϕ⋆′ = ϕm∗
◦ ϕm
′
∗ = ϕm+m
′
∗ = ϕm
′
∗ ◦ ϕm∗
= ϕ⋆′ ◦ ϕ⋆,
то значения секретных ключей ϕ⋆(ϕ⋆′ (ui
1, ui
2), ui
2) = ϕ⋆′ ◦ ϕ⋆(u1, u2) и ϕ⋆′ (ϕ⋆(ui
1, ui
2), ui
2) = ϕ⋆ ◦ ϕ⋆′ (u1, u2),
вычисленные на сторонах A и B, совпадают.
Хорошо известно [6], что сложность вычисления операции ϕ⋆ = ϕm∗
с применением быстрого алго-
ритма возведения в степень оценивается как O(log(m)) полугрупповых операций ◦.
Возможности практического применения протокола DHM-M в первую очередь определяются потреб-
ностями в памяти для представления операций ϕ⋆ = ϕm∗
и ϕ⋆′ = ϕm
′
∗ на носителе большой мощности и
вычислительной сложностью алгоритма построения секретного ключа.
В [5] рассматривался способ представления операции ϕ⋆ = ϕm∗
индикатором ее графика, точнее, пред-
ставлением индикатора в форме трехиндексного массива двоичных значений rm
i,j,k, i, j, k ∈ 1..N, который
в случае группоида M∗ = ⟨1..N, (∗)⟩ определяется правилом
rm
i,j,k =
{
1 , ϕm∗
(i, j) = k
0 , ϕm∗
(i, j) ̸= k
.
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 45
Нетрудно показать [5], что циклическая полугруппа ⟨{ϕm∗
}∞
m=1, (◦)⟩ изоморфна полугруппе
⟨{rm
i,j,k
}∞
m=1, (·)⟩, где
rm
i,j,s
· rn
s,j,k = maxs∈1..N (min(rm
i,j,s, rn
s,j,k)),
ri,j,k =
{
1 , i ∗ j = k
0 , i ∗ j ̸= k
,
r1
i,j,k = ri,j,k,
rm+1
i,j,k = rm
i,j,s
· rs,j,k, i, j, k ∈ 1..N, m ∈ N.
При таком способе представления сложность реализации операции ◦ оценивается как O(N4) эле-
ментарных операций (взятия минимума и максимума из двоичных значений). Cложность нахождения
результата операции ϕm∗
(i, j) оценивается как O(N) элементарных операций сравнения (двоичных зна-
чений). Грубые верхние оценки потребности в памяти и вычислительная сложность алгортима построе-
ния секретного ключа составляют O(N3) бит и O(N4) элементарных операций, соответственно. Таким
образом, даже при мощности носителя группоида N ∼ 220 потребности в памяти и вычислительная
сложность будут весьма велики и составят O(260) и O(280) единиц измерения.
Изученные в предыдущих разделах фрактальные группоиды пригодны для снижения вычислитель-
ных затрат при реализации протокола DHM-M. В силу замечания 2.3.1 для вычисления результата
операции ϕ⋆(i, j) = ϕm∗
(i, j) фрактального группоида M∗ = ⟨1..N, (∗)⟩ потребуется хранение только мат-
рицы Кэли A = (ai,j) базового группоида M = ⟨1..n, (⋄)⟩, где N = 2k0n, и применение к ней одного из
алгоритмов 2.1.1–2.1.4, глубина рекурсии каждого из которых не превзойдет k0.
Для более точных оценок рассмотрим пару матриц Кэли A = (ai,j) и B = (bi,j) порядка n и мат-
ричную операцию •, определенную в соответствии с (2.6) как A • B = (bai;j ,j). Нетрудно понять, что
реализация операции • потребует 2n2 операций последовательного доступа к элементам матриц A и B
и одной операции записи итогового значения в результирующий массив. Последовательность этих трех
операций будем считать элементарной операцией доступа. Таким образом, вычислительная сложность
операции • может быть оценена как 2n2 элементарных операций доступа.
В силу замечания 2.2.1, циклические полугруппы ⟨{ϕm⋄
}∞
m=1, (◦)⟩ и ⟨{Am}∞
m=1, (•)⟩ изоморфны, по-
этому вычислительную сложность реализации операции ϕm⋄
можно оценить как O(mn2) элементарных
операций доступа.
Для представления i ∈ 1..N потребуется не более log(N)+1 = k0+log(n)+1 бит. При этом потребности
в памяти для представления операции ϕ⋄ матрицей Кэли можно оценить как O(n2 log(n) бит.
Для оценки вычислительной сложности определения результата операции ϕ⋆(i, j) = ϕm∗
(i, j) достаточ-
но проанализировать операции, выполняемые на шаге 3.2 каждого из алгоритмов 2.1.1–2.1.4. На каждом
уровне рекурсии будет выполняться не более двух операций вычитания для индексов i−n, j−n, не бо-
лее одной операции сложения для возвращаемого значения процедуры D/R/C/TA+n и не более трех
операций целочисленного сравнения. Таким образом, вычислительную сложность определения значения
ϕ⋆(i, j) можно оценить как O(k0) арифметических операций и операций целочисленного сравнения.
Сформулируем протокол Диффи — Хелмана — Меркла для фрактальных группоидов.
Протокол Диффи — Хелмана — Меркла на группоидах DHM-FM
1. Опубликованные общедоступные значения: базовый группоид ⟨1..n, (⋄)⟩ (базовая матрица Кэли A =
= (ai,j)); тип расширения σ ∈ {d, r, c, t}, p ∈ N; последовательность значений аргументов фракталь-
ных группоидов {(is, js)}p
s=1, is, js ∈ 1..nks , s ∈ 1..p.
2. Вычисляемые значения на стороне A: операция ϕm⋄
— m-я степень операции ⋄, последовательность
значений результатов операции {ϕ⋆(is, js)}p
s=1 = {ϕm ⋄k
s
(is, js)}p
s=1. Значения, передаваемые по откры-
тому каналу связи: {ϕ⋆(is, js)}p
s=1. Секретное значение: m (для диагонального расширения – четное
число).
3. Вычисляемые значения на стороне B: операция ϕm
′
⋄ — m′-я степень операции ⋄, последователь-
ность значений результатов операции {ϕ⋆′ (is, js)}p
s=1, где ϕ⋆′ (is, js) = ϕm
′
⋄k
s
(is, js). Значения, переда-
ваемые по открытому каналу связи: {ϕ⋆′ (is, js)}p
s=1. Секретное значение: m′ (для диагонального
расширения – четное число).
4. Вычисляемое значение секретного ключа на стороне A: K = {ϕ⋆(ϕ⋆′ (is, js), js)}p
s=1.
46
Цветов В.П. Фрактальные группоиды и криптография с открытым ключом
Tsvetov V.P. Fractal magmas and public-key cryptography
5. Вычисляемое значение секретного ключа на стороне B: K = {ϕ⋆′ (ϕ⋆(is, js), js)}p
s=1.
6. Значения, известные третьей стороне C: ⟨1..n, (⋄)⟩, p, {(is, js)}p
s=1, {ϕ⋆(is, js)}p
s=1, {ϕ⋆′ (is, js)}p
s=1.
Замечание 2.4.1
В силу замечания 2.1.6, можно считать, что целочисленные интервалы 1..nks о которых идет речь
в п. 1 протокола DHM-FM, являются наименьшими по включению из содержащих заданные значения
is, js ∈ 1..nks , т.е. is, js ∈ 1..nks , и is, js /∈
1..nk для любого nk = 2kn < nks = 2ksn.
Для вычисления значений результатов операции ϕ⋆′ (is, js) = ϕm
′
⋄k
s
(is, js) в зависимости от типа рас-
ширения σ применяется один из алгоритмов 2.1.1–2.1.4.
В качестве примера приведем результаты численного эксперимента реализации протокола DHM-FM.
1. Опубликованные общедоступные значения: базовая матрица Кэли
A =


16 7 5 13 4 11 13 3 9 1 1 8 2 9 13 16
9 6 16 7 13 13 16 1 6 10 15 8 6 9 12 14
13 2 16 5 3 7 12 5 2 13 16 9 1 7 15 9
14 14 8 5 5 1 9 9 8 5 11 5 2 7 2 12
5 7 16 10 15 10 6 7 15 13 3 3 16 5 7 4
8 2 6 3 12 11 6 2 13 10 10 9 9 7 11 13
4 5 3 12 6 16 7 9 12 7 2 12 12 10 4 3
11 15 9 12 13 4 16 14 8 16 14 2 1 10 7 2
11 2 2 8 5 15 13 15 13 2 7 2 7 13 10 4
11 5 2 16 8 1 10 2 4 14 6 1 7 10 14 11
3 3 9 15 2 3 14 1 2 9 1 6 10 3 7 16
9 9 1 9 12 8 9 16 7 7 7 16 8 6 13 4
2 7 8 11 9 9 12 13 5 14 1 14 6 3 1 13
10 14 3 15 10 15 6 12 7 16 4 12 10 16 16 14
2 9 14 9 7 15 15 16 6 11 7 12 9 9 10 12
5 15 7 11 7 16 1 6 11 2 4 15 8 10 16 1

 ,
тип расширения d — диагональное, длина последовательности значений аргументов 4, последова-
тельность значений аргументов {(53, 6), (3273, 234), (11529, 2149), (434490, 39752)},
2. Секретное значение на стороне A: показатель степени m = 4. Вычисляемые значения на стороне A:
степень базовой матрицы Кэли
Am =


5 5 3 9 7 16 13 9 15 1 1 2 7 7 1 1
13 2 16 8 15 15 12 7 15 2 15 2 12 7 13 14
11 6 16 11 3 16 12 15 5 2 1 2 9 10 16 4
3 14 16 11 6 7 9 6 8 16 1 2 7 10 1 4
5 5 16 15 12 3 6 16 5 2 11 8 2 5 12 12
13 6 6 16 12 16 6 5 6 2 6 2 8 10 2 13
11 7 3 12 12 16 7 6 7 7 2 12 2 10 13 12
2 6 7 12 15 3 12 6 8 14 1 8 9 10 12 14
2 6 3 8 6 15 13 2 6 16 7 8 1 10 16 12
2 7 3 9 5 7 10 5 8 10 10 8 1 10 16 16
9 2 7 12 5 16 6 7 5 14 1 8 8 10 12 1
13 2 7 9 12 11 9 1 12 7 7 16 6 10 1 12
3 5 16 8 7 15 12 13 13 10 1 15 12 10 13 13
13 14 3 12 9 15 6 2 12 14 1 12 8 10 16 14
3 2 7 9 12 15 15 1 15 10 7 12 8 7 16 4
5 6 7 8 12 16 9 3 13 16 1 15 6 10 16 16


.
Последовательность значений результатов операции, вычисленных при помощи алгоритма 2.1.1 и
передаваемых по открытому каналу связи: {51, 3120, 9574, 408181}.
3. Секретное значение на стороне B: показатель степени m′ = 10. Вычисляемые значения на сто-
роне B: степень базовой матрицы Кэли
Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 2. С. 23–49
Vestnik of Samara University. Natural Science Series, 2020, vol. 26, no. 2, pp. 23–49 47
Am
′
=


5 5 3 9 12 16 13 3 13 1 1 2 9 10 1 1
2 2 16 8 12 15 12 1 13 14 15 2 7 10 13 14
3 6 16 8 3 16 12 5 6 14 1 2 6 10 16 4
13 14 16 8 12 16 9 9 8 10 1 2 9 10 1 4
5 5 16 12 12 16 6 7 6 14 1 8 1 5 1 12
2 6 6 9 12 16 6 2 5 14 6 2 12 10 13 13
3 7 3 12 12 16 7 9 7 7 2 12 1 10 13 12
9 6 7 12 12 16 12 9 8 2 1 8 6 10 1 14
9 6 3 8 12 15 13 15 5 10 7 8 8 10 16 12
9 7 3 9 12 16 10 2 8 16 10 8 8 10 16 16
11 2 7 12 12 16 6 1 6 2 1 8 12 10 1 1
2 2 7 9 12 16 9 16 12 7 7 16 2 10 1 12
13 5 16 8 12 15 12 13 15 16 1 15 7 10 13 13
2 14 3 12 12 15 6 15 12 2 1 12 12 10 16 14
13 2 7 9 12 15 15 16 13 16 7 12 12 10 16 4
5 6 7 8 12 16 9 6 15 10 1 15 2 10 16 16


.
Последовательность значений результатов операции, вычисленных при помощи алгоритма 2.1.1 и
передаваемых по открытому каналу связи: {64, 3114, 9580, 408178}.
4. Вычисляемое при помощи алгоритма 2.1.1 значение секретного ключа на стороне A:
{64, 3274, 11532, 434487}.
5. Вычисляемое при помощи алгоритма 2.1.1 значение секретного ключа на стороне B:
{64, 3274, 11532, 434487}.
Выводы
В статье определены понятия фрактальных расширений конечных группоидов M = ⟨U, (∗)⟩, а так-
же связанные с ними понятия типов и шкал расширений. Конечный группоид полностью описывается
своей таблицей Кэли, поэтому группоиды и таблицы Кэли их операций естественным образом отож-
дествляются. Фрактальное расширение позволяет удваивать мощность носителя исходного (базового)
группоида, определяя новую бинарную операцию путем «клонирования» базовой таблицы Кэли. При
этом каждый группоид является подгруппоидом своего расширения. Для представления группоидов ис-
пользовались целочисленные диапазоны 1..n и матрицы Кэли A = (ai,j) с элементами ai,j ∈ 1..n. Система
последовательных расширений некоторого «базового» группоида M = ⟨1..n, (⋄)⟩ с матрицей A = (ai,j)
образует шкалу фрактальных расширений Sσ = {M(σ)
k
}∞
k=0 с фрактальными матрицами Ak = (kai,j).
Самоподобная структура матриц Кэли Ak позволяет сформулировать простые алгоритмы для вычис-
ления результатов операций во фрактальных шкалах исключительно на основании базовой матрицы
Кэли. Таким образом, несмотря на то что мощность носителей группоидов фрактальной шкалы воз-
растает экспоненциально как 2kn, для нахождения результатов их операций достаточно оперировать с
элементами базовой матрицы порядка n, а не фрактальных матриц порядка 2kn. При этом сложность
алгоритмов вычисления результатов оценивается как O(k) целочисленных арифметических операций.
Тем самым обеспечивается существенная экономия вычислительных ресурсов при расчетах.
Примечательным является тот факт, что фрактальные расширения сохраняют свойства фракталь-
ности относительно композиции своих операций. Ранее было установлено [5], что композиция бинарных
операций группоидов с общим носителем обладает свойством ассоциативности, что позволило использо-
вать ее для модификации протокола протокола Диффи — Хелмана — Меркла открытого распределе-
ния ключей шифрования. Однако в случае произвольных группоидов данная модификация предъявляла
весьма высокие требования к вычислительным ресурсам и памяти для своей реализации. Шкалы фрак-
тальных группоидов позволяют снизить требуемые объемы вычислений до приемлемого уровня.
Все определяемые в статье понятия сопровождаются подробными примерами, также приведен пример
результатов численного эксперимента по выработке общего ключа шифрования в асимметричной схеме
с двумя участниками.

About the authors

V. P. Tsvetov

Author for correspondence.
Email: tsf-su@mail.ru
ORCID iD: 0000-0001-6744-224X

Candidate of Physical and Mathematical Sciences, assistant professor of the Department of Information Security

References

Supplementary files