Симметрические группы преобразования и симметрические группы подстановок ряда факториальных множеств и их таблицы умножения

Российский федеральный ядерный центр   
Всероссийский научно-исследовательский институт  
экспериментальной физики 
Ю. В. Кузнецов, А. П. Мартынов,  
И. А. Мартынова, Д. Б. Николаев
Симметрические группы преобразования  
и симметрические группы подстановок  
ряда факториальных множеств  
и их таблицы умножения 
Саров 
2023 

УДК 004.056(075.8) 
ББК 32.81я73 
        С37 
DOI 10.53403/9785951505262 
Одобрено научно-методическим советом Саровского физико-технического  
института Национального исследовательского ядерного университета «МИФИ»  
и ученым советом ФГБУ «Института управления образования» Российской  
академии образования
Рецензент: старший научный сотрудник ФГКВОУ «Военная академия РВСН  
имени Петра Великого», заслуженный деятель науки РФ в области образования, 
доктор технических наук, профессор Ю. А. Романенко 
С37 
Кузнецов Ю. В., Мартынов А. П., Мартынова И. А., Николаев Д. Б. 
Симметрические группы преобразования и симметрические 
группы подстановок ряда факториальных множеств и их таблицы 
умножения. – Саров: ФГУП «РФЯЦ-ВНИИЭФ», 2023. – 294 с.: ил. 
ISBN  978-5-9515-0526-2 
Рассмотрены множества с операциями и симметрические группы 
преобразования, отображения, соответствия, образы, прообразы и операции на множестве, подстановки как элементы групп преобразований, вопросы формирования и преобразования элементов ряда факториальных множеств в функции подстановки и перестановки, групповые преобразования подстановок ряда факториальных множеств и их 
таблицы умножения. Представленные материалы обобщают результаты 
исследований и преобразования симметрических групп подстановок 
как операций над элементами факториальных множеств. 
Представленные материалы исследований могут быть использованы студентами и аспирантами технических специальностей, а также 
предназначены для широкого круга инженерно-технических и научных работников, занимающихся разработкой информационных технологий и защитой информации. 
УДК 004.056(075.8) 
ББК 32.81я73 
ISBN  978-5-9515-0526-2    
 © ФГУП «РФЯЦ-ВНИИЭФ», 2023 
 © Кузнецов Ю. В., Мартынов А. П., 
 Мартынова И. А., Николаев Д. Б. 

Содержание 
 
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
7 
Глава 1. Множества с операциями и симметрические группы преобразований . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
9 
1. Множества с операциями и их аксиомы. Классификация 
алгебраических структур . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
9 
2. Отображения, соответствия, образы, прообразы и операции на множестве . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
21 
3. Одиночные подстановки как элементы групп преобразований . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
38 
 
3.1. Перестановки и подстановки. Задание подстановок . . . . . 
38 
 
3.2. Последовательное выполнение подстановок, ассоциативность умножения подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
40 
 
3.3. Тождественные или единичные подстановки . . . . . . . . . . . 
44 
 
3.4. Изображение подстановок в схемном виде . . . . . . . . . . . . .  45 
 
3.5. Обратные подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
46 
 
3.6. Разложение подстановок, циклические подстановки . . . . .  48 
 
3.7. Возведение подстановок в степень . . . . . . . . . . . . . . . . . . . .  55 
 
3.8. Разложение подстановок в транспозиции . . . . . . . . . . . . . .  59 
 
3.9. Умножение подстановок с независимыми циклами . . . . .  
63 
 
3.10. Циклические подстановки в дискретной математике и 
их свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
65 
 
3.11. Правила, облегчающие перемножение подстановок . . . . . 
68 
 
3.12. Общие характеристики подстановок . . . . . . . . . . . . . . . . . 
72 
 
3.13. Способ разложения любой подстановки в произведение 
транспозиций, равное декременту . . . . . . . . . . . . . . . . . . . . . . . .  
 
74 
 
3.14. Разложение подстановок на классы . . . . . . . . . . . . . . . . . . 
77 
 
3.15. Выводы к главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  78 
 
 
82 
Глава 2. Формирование и преобразование элементов ряда 
факториальных множеств в функции подстановки и перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
82 
4. Нумерация перестановок ряда факториальных множеств . . .  82 
 
4.1. Основные функции криптографических систем и их 
структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

4.2. Функции факториала и ряд факториальных множеств . . . . .  
86 
 
4.3. Задача нумерации элементов ряда факториальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
89 
 
4.4. Модель преобразования чисел десятичной системы счисления в перестановки ряда факториальных множеств . . . . . . . 
 
90 
5. Анализ перестановок ряда факториальных множеств . . . . . 106 
 
5.1. Симметрические группы и перестановки ряда факториальных множеств. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
106 
 
5.2. Задание перестановок. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 
 
5.3. Последовательное выполнение перестановок, умножение 
перестановок. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
108 
 
5.4. Изображение перестановок в схемном и циклическом 
видах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
109 
 
5.5. Свойства умножения и ассоциативность перестановок . . . . .  111 
 
5.6. Тождественные перестановки . . . . . . . . . . . . . . . . . . . . . . . .  112 
 
5.7. Обратные перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 
6. Результаты анализа перестановок ряда факториальных 
множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
115 
7. Состав и запись подстановок ряда факториальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
121 
 
7.1. Состав и запись подстановок факториальных множеств 
Ф2 и Ф3 и групп подстановок G2(S) и G3(S) . . . . . . . . . . . . . . . . . 
 
121 
 
7.2. Состав и запись подстановок факториальных множеств 
Ф3 и Ф4 и групп подстановок G3(S) и G4(S) . . . . . . . . . . . . . . . . . 
 
123 
 
7.3. Состав и запись подстановок факториальных множеств 
Ф4 и Ф5 и групп подстановок G4(S) и G5(S) . . . . . . . . . . . . . . . .  
 
130 
 
126 
 
7.4. Вариант разложения подстановок факториальных множеств и групп подстановок на классы . . . . . . . . . . . . . . . . . . . . . 
Глава 3. Групповые преобразования подстановок факториальных множеств и их таблицы умножения . . . . . . . . . . . . 
 
135 
8. Группы подстановок и их таблицы умножения . . . . . . . . . .  135 
 
8.1. Группа подстановок G2(S) факториального множества 
Ф2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
137 
 
8.2. Группа подстановок G3(S) факториального множества 
Ф3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
141 
 
8.3. Группа подстановок G4(S) факториального множества Ф4 . . . 148 
 
8.3.1. Структура подстановок группы G4(S) . . . . . . . . . . . . .  148 
 
8.3.2. Таблицы умножения подстановок группы G4(S) . . . . .  151 

8.3.3. Анализ таблиц умножения подстановок группы 
G4(S) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
156 
 
8.4. Группы подстановок 
5( )
G
S  ряда факториальных множеств 
 
160 
5
Φ  и направления исследований . . . . . . . . . . . . . . . . . . . . . . . . . 
 
8.5. Анализ таблиц умножения групп подстановок на соответствие аксиомам группы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
162 
 
8.6. Варианты умножения последовательности подстановок . . . 163 
 
8.6.1. Алгоритм формирования последовательности умножения подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
163 
 
8.6.2. Модели вариантов умножения нескольких подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
171 
 
164 
 
8.7. Независимые циклы и варианты коммутативности умножения подстановок ряда факториальных множеств . . . . . . . . .  
9. Варианты умножения групп подстановок и их взаимосвязь с латинскими преобразованиями . . . . . . . . . . . . . . . . .  
 
173 
 
9.1. Варианты операций умножения симметрических групп 
подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
173 
 
9.2. Умножение подстановки на подстановку . . . . . . . . . . . . . .  174 
 
9.3. Примеры умножения подстановок и групп подстановок . . .  175 
 
9.4. Умножения группы на группу и результаты анализа . . . . . 178 
 
9.5. Общий вид умножения подстановок Gn(S)×Gn(S) . . . . . . .  181 
 
9.6. Результаты анализа вариантов умножения групп подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
187 
 
9.7. Таблицы умножения симметрических групп подстановок 
и латинские преобразования . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
189 
 
9.7.1. Понятие латинского квадрата . . . . . . . . . . . . . . . . . . .  189 
 
9.7.2. Латинские преобразования и таблицы умножения 
симметрических групп подстановок . . . . . . . . . . . . . . . . . . . .  
 
191 
 
9.7.3. Способ формирования и нумерации латинских преобразований . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
193 
 
9.7.4. Примеры применения латинских преобразований . . . . . .  195 
10. Операция деления подстановок . . . . . . . . . . . . . . . . . . . . . . . .  196 
 
10.1. Варианты операций деления и метод последовательного 
перемещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
203 
 
196 
 
10.2. Метод группового перемещения . . . . . . . . . . . . . . . . . . . .  200 
11. Взаимосвязь операций сдвига и одиночных подстановок 
с одним циклом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

12. Возведение в степень подстановок факториальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
206 
 
12.1. Возведение в степень подстановок факториальных 
множеств Ф1 и Ф2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
206 
 
12.2. Возведение в степень подстановок факториального 
множества Ф3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
207 
 
12.3. Возведение в степень подстановок факториального 
множества Ф4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
228 
 
210 
 
12.4. Возведение в степень подстановок факториального 
множества порядка Ф5 и более . . . . . . . . . . . . . . . . . . . . . . . . . .  
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  234 
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  235 
Приложение 1. Выполнение операций над цифровыми последовательностями как элементами конечного поля . . . . . . . . . . . 
 
238 
 
244 
Приложение 2. Левая таблица умножения элементов симметрических групп подстановок G4(S)×G4(S) . . . . . . . . . . . . . . . . . . . 
Приложение 3. Классы подстановок и их таблицы . . . . . . . . . .  278 
 
 

Введение 
 
Развитие автоматизированных систем управления объектами 
сложной функциональной структуры, которая может динамически 
корректироваться и изменяться в процессе своего функционирования, предопределило необходимость совершенствования средств 
идентификации и аутентификации. Важным фактором в данном 
направлении является то, что все программно-технические и алгоритмические решения должны базироваться на отечественных 
разработках и соответствовать современному уровню развития технологий и промышленности. Отечественные аппаратные решения, особенно в части реализации специфических функций и экстремальных условий эксплуатации, ограничены как на уровне вычислительных возможностей, так и в части скорости обработки и объема 
хранения данных. Единственным выходом из сложившейся ситуации 
является построение алгоритмически модифицируемых программных платформ, имеющих возможность адаптации под требуемую 
конфигурацию аппаратных ресурсов. Применительно к процессам 
идентификации и аутентификации требуется определить базовые 
критерии, по которым будет осуществляться адаптация процедуры 
идентификации объекта в каждом конкретном режиме функционирования системы управления. Подобными критериями, в частности, являются длина идентифицирующего признака, вычислительная сложность алгоритма идентификации, скорость его выполнения 
и объем памяти, требуемый для проведения вычислительных операций. В качестве алгоритмических платформ, учитывающих совокупность критериев идентификации, целесообразно использовать 
криптографические системы, которые позволяют осуществить все 
необходимые процедуры, такие как шифрования, хеширования 
и т. д. Подобные системы строятся, основываясь на применении 
различных линейных и нелинейных преобразований, притом безопасность (стойкость алгоритма к атакам) обеспечивает именно использование нелинейных преобразований. 
Процессы синтеза и анализа систем преобразования и обработки информации показывают, что основными функциями преобра

зования в них являются функции подстановки и перестановки, 
обеспечивающие рассеивание и перемешивание информации. Они 
могут быть представлены как группы подстановок ряда факториальных множеств. При задании групп указывается, из каких элементов она состоит и какая групповая операция на них задана. Если 
не обращать внимания на эти требования, то можно обобщить подобные группы в отдельные классы с одинаковыми характеристиками. Такие классы обладают высокой степенью абстракции 
и характеризуются не индивидуальными, а групповыми операциями. При этом групповые операции подобны друг другу. 
При рассмотрении нелинейных преобразований в системах 
преобразования информации следует учитывать особенности 
функционирования и условий применения алгоритмов, использующих данные отображения. Основными требованиями современных алгоритмов преобразования данных являются замкнутость 
и взаимооднозначность операций внутри используемых множеств. 
Эти отображения наряду с классическими свойствами обладают, по 
аналогии с физическими процессами, групповыми характеристиками, транслируемыми в том или ином виде, при видоизменении 
множества или введении новых условий. 
В работе рассмотрены множества с операциями и симметрические группы преобразования, отображения, соответствия, образы, 
прообразы и операции на множестве, подстановки как элементы 
групп преобразований, вопросы формирования и преобразования 
элементов ряда факториальных множеств в функции подстановки 
и перестановки, групповые преобразования подстановок ряда факториальных множеств и их таблицы умножения. Представленные 
материалы обобщают результаты исследований и преобразования 
симметрических групп подстановок как операций над элементами 
факториальных множеств. 

Глава 1. Множества с операциями  
и симметрические группы преобразований 
 
1. Множества с операциями и их аксиомы.  
Классификация алгебраических структур 
 
Примерно два столетия назад алгебра из науки о буквенном 
вычислении уравнений превратилась в общую науку об операциях 
и их свойствах на множествах, состоящих из отдельных элементов, 
обладающих определенными свойствами. Выражение a∈A означает, 
что элемент a принадлежит множеству A. Множество A является 
подмножеством множества B, если каждый элемент, принадлежащий множеству A, принадлежит множеству B(A⊆B). Выражение 
A⊂B означает, что A⊆B, но A≠B. Если ξ – некоторое свойство, которым обладают элементы множества A, то выражение  
{a|a∈A, a обладает свойством ξ} 
означает подмножество множества A, состоящее из всех его элементов, обладающих свойством ξ. Если a1, a2, …, an – элементы 
множества A, то пишут A = {a1, a2, …, an}. 
В алгебре также рассматриваются операции объединения, пересечения, вложения, наложения и отображения множеств. Оказалось, что операции над высказываниями и множествами, обладают 
свойствами коммутативности, ассоциативности, дистрибутивности, 
но некоторые их свойства были не похожи на свойства операций 
над числами. Все вышеизложенное привело к созданию абстрактного понятия композиции, т. е. операции, которая каждой паре (α, β) 
элементов некоторого множества сопоставляет третий элемент γ 
того же или другого множества. Композициями являются сложение 
и умножение как натуральных, так и любых целых, а также рациональных и комплексных чисел, умножение матриц, пересечение 
и объединение подмножеств некоторого множества и т. д. [1, 2]. 
Изучение свойств композиций привело к мысли, что основная 
задача алгебры – изучение свойств операций, рассматриваемых не

зависимо от объектов, к которым они применяются. Иными словами, 
алгебра стала рассматриваться как общая наука о свойствах законов композиции и свойствах операций. При этом два множества, 
в каждом из которых заданы композиции, стали считаться тождественными с точки зрения алгебры («изоморфными»), если между 
этими множествами можно установить взаимно-однозначное соответствие, переводящее один закон композиции в другой. Изучая 
одно из них, можно узнать алгебраические свойства другого. Оказалось, что свойства математических операций во многом похожи. 
Свойства сложения действительных чисел можно представить 
как: 
1) а + (b + c) = (а + b) + c для любых а, b, c (ассоциативность); 
2) а + b = b + а для любых а, b (коммутативность); 
3) существует такое число 0, что а + 0 = а (существование нуля); 
4) для любого числа а существует такое обратное число –a, что 
а + (–а) = 0 (существование противоположного элемента); 
Точно такими же свойствами обладают операции сложения векторов: 
1) 
(
)
(
)
;
a
b
c
a
b
c
+
+
=
+
+
 
2) 
;
a
b
b
a
+
=
+
 
3) 
0
;
a
a
+
=
 
4) 
(
)
0.
a
a
+ −
=
 
Операция умножения, если ее рассматривать на множестве 
всех отличных от нуля действительных чисел, также имеет аналогичные свойства: 
1) a(bc) = (ab)c (ассоциативность); 
2) ab = ba  (коммутативность); 
3) существует такое число 1, что a · 1 = a для любого а; 
4) для любого a(a ≠ 0) существует такое число a–1, что aa–1 = 1. 
Операция композиции движения обладает лишь тремя из этих 
свойств: 
1) h(gf ) = (hg)f для любых движений h, g, f; 
2) коммутативность (соотношение (gf ) = (fg) для движений места не имеет); 
3) существует такое движение е (тождественное преобразование), что (fe) = f,(ef ) = f для любого движения f.