Аксиоматические основы функций подстановки в системе счисления ряда факториальных множеств и их характеристики

 
 
 
ФГУП «Российский федеральный ядерный центр −  
Всероссийский научно-исследовательский институт  
экспериментальной физики» 
 
 
 
 
 
А. П. Мартынов, И. А. Мартынова,  
В. Н. Фомченко 
 
 
 
Аксиоматические основы функций подстановки  
в системе счисления ряда факториальных  
множеств и их характеристики 
 
 
 
Монография 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Саров 
2019 

 
 
 
М29 
УДК 004.056 
ББК 32.81 
 М29 
 
Одобрено научно-методическим советом Саровского  
физико-технического института Национального исследовательского  
ядерного университета «МИФИ» и ученым советом ФГБУ «Институт 
управления образования» Российской академии образования 
 
Рецензенты: ведущий научный сотрудник ФГБУ «27 Центрального научно-исследовательского института» Министерства обороны РФ, доктор 
технических наук А. В. Седаков, старший научный сотрудник ФГКВОУ 
«Военная академия РВСН имени Петра Великого», заслуженный деятель 
науки РФ, лауреат премии Правительства РФ в области образования, доктор технических наук, профессор Ю. А. Романенко. 
 
Мартынов А. П., Мартынова И. А., Фомченко В. Н. 
Аксиоматические основы функций подстановки в системе 
счисления ряда факториальных множеств и их характеристики: Монография. – Саров: ФГУП «РФЯЦ-ВНИИЭФ», 
2019. – 210 с.: ил. 
 
ISBN  978-5-9515-0447-0  
 
 
В учебном пособии рассмотрены аксиоматические основы функций 
подстановки в системе счисления ряда факториальных множеств. Основное внимание уделено позиционным системам счисления и основным понятиям теории множеств. Введены понятия ряда факториальных множеств, рассмотрены его аксиоматические основы. Приведена новая позиционная система счисления – система счисления ряда факториальных 
множеств. Рассмотрены характеристики функций подстановки в системе 
счисления ряда факториальных множеств и их статистические данные. 
Представленные материалы могут быть использованы студентами 
и аспирантами технических специальностей, а также предназначены для 
широкого круга инженерно-технических работников, занимающихся разработкой информационных технологий и защитой информации. 
 
УДК 004.056 
ББК 32.81 
 
ISBN  978-5-9515-0447-0                       ©   ФГУП «РФЯЦ-ВНИИЭФ», 2019 

Содержание 
 
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
7 
Часть 1. Аксиоматические основы функций подстановки  
в системе счисления ряда факториальных множеств . . . . . . . 
 
13 
1. Непозиционные и позиционные системы счисления . . . . . . . 
13 
2. Перевод целых чисел из одной позиционной системы 
счисления в другую . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
17 
3. Системы счисления и теория множеств . . . . . . . . . . . . . . . . . 
21 
 
3.1. Множества и десятичная система счисления . . . . . . . . . 
22 
 
3.2. Позиционный метод формирования множеств . . . . . . . . 
24 
 
3.3. Теоремы о числе элементов позиционных множеств . . . . . 
27 
 
3.4. Основные характеристики позиционных систем  
       счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
28 
4. Аксиоматические основы подстановок ряда факториальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
30 
 
4.1. Подстановки (перестановки), факториал, ряд факто- 
       риальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
30 
 
4.2. Система определений ряда факториальных множеств . . . 
36 
 
4.3. Проблема нумерации элементов ряда факториальных  
       множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
37 
 
4.4. Структура, определения и теоремы ряда факториальных  
       множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
41 
 
4.5. Распределение теорем по факториальным множествам  
и их структурные характеристики . . . . . . . . . . . . . . . . . . 
 
44 
5. Система счисления ряда факториальных множеств . . . . . . . 
47 
 
5.1. Принципы и этапы формирования системы счисления  
       ряда факториальных множеств . . . . . . . . . . . . . . . . . . . . . 
 
47 
 
5.2. Правила построения системы счисления ряда факто- 
       риальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
51 
6. Алгоритмы преобразования элементов множества из десятичной системы счисления в систему счисления ряда факториальных множеств и обратно . . . . . . . . . . . . . . . . . . . . . . . 
 
 
52 
 

6.1. Преобразования элементов множества из десятичной 
системы счисления в систему счисления ряда факториальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
 
53 
 
6.2. Преобразования элементов множества из системы 
счисления ряда факториальных множеств в десятичную 
систему счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
 
57 
 
6.3. Теоремы преобразования чисел . . . . . . . . . . . . . . . . . . . . 
59 
7. Система счисления ряда факториальных множеств и реализация подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
61 
 
7.1. Метод последовательного циклического сдвига элементов факториальных множеств . . . . . . . . . . . . . . . . . . 
 
61 
 
7.2. Алгоритм формирования множества числовых значений циклических сдвигов . . . . . . . . . . . . . . . . . . . . . . . . . 
 
63 
8. Системы счисления рядов упорядоченных множеств . . . . . 
71 
Часть 2. Характеристики функций подстановки в системе 
счисления ряда факториальных множеств . . . . . . . . . . . . . .  
 
75 
9. Общие характеристики подстановок ряда факториальных 
множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
75 
 
9.1. Независимые циклы и их количество . . . . . . . . . . . . . . . 
76 
 
9.2. Декремент подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . 
80 
 
9.3. Инверсия подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . 
82 
 
9.4. Четность подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
85 
 
9.5. Знак подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
86 
 
9.6. Постановка задачи исследования для одиночных подстановок с наилучшими характеристиками . . . . . . . . . . 
 
86 
10. Состав и характеристики подстановок факториальных 
множеств Ф1 и Ф2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
87 
11. Состав и характеристики подстановок факториального 
множества Ф3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
88 
 
11.1. Количество независимых циклов подстановок множества Ф3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
89 
 
11.2. Декремент подстановок множества Ф3 . . . . . . . . . . . . . 
90 
 
11.3. Инверсия подстановок множества Ф3 . . . . . . . . . . . . . . 
92 
 
11.4. Количество независимых циклов и декремент подстановок множества Ф3 . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
93 
 
11.5. Декремент и инверсия подстановок множества Ф3 . . . 
94 

11.6. Количество независимых циклов, декремент и инверсия множества Ф3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
95 
12. Состав и характеристики подстановок множества Ф4 . . . . . 97 
 
12.1. Количество независимых циклов множества Ф4 . . . . . 99 
 
12.2. Декремент подстановки множества Ф4 . . . . . . . . . . . . . 101 
 
12.3. Инверсия подстановок множества Ф4 . . . . . . . . . . . . . . 103 
 
12.4. Количество независимых циклов и декремент подстановок множества Ф4 . . . . . . . . . . . . . . . . . . . . . . . . . 
 
106 
 
12.5. Декремент и инверсия подстановок множества Ф4 . . . 107 
 
12.6. Количество независимых циклов, декремент и инверсия множества Ф4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
109 
13. Состав и характеристики подстановок множества Ф5 . . . . . 111 
 
13.1. Количество независимых циклов множества Ф5 . . . . . 117 
 
13.2. Декремент подстановок  множества Ф5 . . . . . . . . . . . .  123 
 
13.3. Инверсия подстановок множества Ф5 . . . . . . . . . . . . . . 126 
 
13.4. Количество независимых циклов и декремент подстановок множества Ф5 . . . . . . . . . . . . . . . . . . . . . . . . . 
 
132 
 
13.5. Декремент и инверсия подстановок множества Ф5 . . . 140 
 
13.6. Количество независимых циклов, декремент и инверсия подстановок множества Ф5  . . . . . . . . . . . . . . . . 
 
146 
14. Характеристики подстановок произвольного факториального множества. Критерии выбора одиночных подстановок 
с наилучшими характеристиками . . . . . . . . . . . . . . . . . . . . . . 
 
 
162 
 
 
153 
 
14.1. Количество независимых циклов подстановок . . . . . . 153 
 
14.2. Декремент подстановок . . . . . . . . . . . . . . . . . . . . . . . . .  154 
 
14.3. Количество независимых циклов и декремент подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
155 
 
14.4. Инверсия подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . 156 
 
14.5. Критерии выбора одиночных подстановок с наилучшими характеристиками . . . . . . . . . . . . . . . . . . . . . . . . . 
 
156 
15. Статистические данные количества независимых циклов 
подстановок и их анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
161 
 
15.1. Статистические данные количества независимых 
циклов подстановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
161 
 
15.2. Последовательный алгоритм формирования значений 
количества независимых циклов и их числа в целом 
и по диапазонам факториального множества Ф5 . . . . . 

15.3. Результаты анализа статистических данных количества независимых циклов . . . . . . . . . . . . . . . . . . . . . . . . 
 
165 
16. Статистические данные декремента подстановок и их 
анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
169 
 
16.1. Статистические данные декремента подстановок . . . . 169 
 
16.2. Последовательный алгоритм формирования значений декремента и их числа в целом и по диапазонам 
множества Ф5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
 
170 
 
16.3. Результаты анализа статистических данных декремента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
172 
17. Статистические данные инверсии подстановок и их 
анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
176 
 
17.1. Статистические данные инверсии подстановок . . . . .  176 
 
17.2. Последовательный алгоритм формирования значений инверсии и их числа в целом и по диапазонам 
множества Ф5  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
 
177 
 
17.3. Результаты анализа статистических данных инверсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
179 
18. Аксиоматическое построение подстановок ряда факториальных множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
183 
 
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 
Приложение 1. История возникновения и преобразования 
чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 
190 
 
П1.1. Числа в математике и нашей жизни . . . . . . . . . . . . . . . 190 
 
П1.2. Устный счет . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 
 
П1.3. Римская система записи чисел . . . . . . . . . . . . . . . . . . . 192 
 
П1.4. Счет у первобытных народов . . . . . . . . . . . . . . . . . . . . 194 
 
П1.5. Числа ацтеков в Мексике в XI–XVI вв. . . . . . . . . . . . . 197 
 
П1.6. Египетская нумерация . . . . . . . . . . . . . . . . . . . . . . . . . . 198 
 
П1.7. Алфавитные нумерации . . . . . . . . . . . . . . . . . . . . . . . .  200 
 
П.1.7.1. Греческое алфавитное изображение чисел . . . . . . . 200 
 
П.1.7.2. Алфавитная нумерация Древней Руси . . . . . . . . . . . 201 
 
П1.8. Позиционные системы . . . . . . . . . . . . . . . . . . . . . . . . .  202 
 
П1.8.1. Клинописная запись чисел Древнего Вавилона . . . . 202 
 
П1.8.2. Цифры индейцев племени майя . . . . . . . . . . . . . . . . . 203 
 
Список литературы к приложению 1 . . . . . . . . . . . . . . . . . . . 204 
Приложение 2. Общие аксиоматические понятия, определения и построения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  
 
205 
 

Введение 
 
Цели долгосрочного развития России заключаются в обеспечении и закреплении геополитической роли страны как одного из лидеров, определяющих мировую политическую и экономическую 
повестку дня. Единственным возможным способом достижения 
этих целей, кроме повышения обороноспособности, является переход экономики на инновационную модель развития. Для России 
в современных условиях оптимальным является вариант развития 
тех сегментов экономики, в которых имеются конкурентные преимущества или в которых они могут быть созданы за сравнительно 
короткий промежуток времени. 
Стремительное увеличение объемов информации и переход 
к цифровой экономике как средству достижения поставленной цели 
привели к бурному развитию информационных технологий и необходимости значительной перестройки информационной среды. Это 
не только новая возможность осуществить научно-технический 
и технологический прогресс, но и новая угроза, связанная с глобализацией информации и необходимостью ее защиты, которая в основном обеспечивается криптографическими методами. Все это 
повышает актуальность более глубокого анализа и изучения существующих криптографических функций, алгоритмов, протоколов 
и систем, и делает актуальным поиск и создание новых методов, 
функций и алгоритмов криптографической защиты информации 
[1–7]. 
Криптографическая система в общем случае определяется как 
некоторое множество отображений одного пространства возможных сообщений в другое пространство возможных криптограмм 
и обратно. Каждое отображение соответствует способу преобразования при помощи конкретного ключа [1–5]. В основе функций 
преобразования данной модели лежит теория множеств, алгебраические и криптографические структуры и группы преобразований, 
включающие понятия теории групп, колец и полей [6, 7]. 
Весь исторический опыт развития криптографии [1–3] показывает, что основными ее функциями преобразования являются 

функции подстановки и перестановки, которые обеспечивают преобразование информации путем ее рассеивания и перемешивания. 
Изучение и анализ этих функций занимает важное место в теории 
защиты информации. Они настолько тесно связаны между собой, 
что порой их трудно разделить.  
В процессе криптографического анализа функций подстановок 
и перестановок возникла необходимость их однозначной идентификации [3–5], классификации, нумерации, анализа принципов распределения характеристик и свойств, а также их произвольного 
и упорядоченного автоматизированного выбора, перебора, сравнения, 
преобразования и практической их реализации. На этом этапе была 
выдвинута гипотеза, что между множеством чисел и любым упорядоченным или произвольно взятым множеством подстановок (перестановок) существует взаимно однозначное соответствие, при котором преобразования элементов множеств являются биективными. 
Объектом исследования стали не только криптографические 
алгоритмы, протоколы, методы и функции преобразования информации, но и подстановки и перестановки как группы преобразований. 
Подстановки являются наиболее изученными функциями из этой 
пары. Варианты описания, преобразования и применения подстановок опубликованы довольно широко в научной литературе [3–12]. 
В частности, в работах [6, 7] представлена довольно интересная 
и полная классификация алгебраических структур и групп преобразований. 
Перестановки являются менее изученными функциями, но по 
своей значимости они являются не менее важными для теории защиты информации. Обратим внимание на еще одно очень важное 
обстоятельство. Проведенный анализ как перестановок, так и подстановок затруднен тем, что в открытых источниках они исследованы и описаны как отдельные объекты, структуры и элементы и 
не рассмотрены в комплексе, когда одновременному анализу подвергаются все возможные перестановки отдельного множества или 
даже ряда множеств.  
Для того чтобы провести полный и всесторонний анализ всех 
возможных подстановок отдельного множества или ряда множеств, 
необходимо иметь возможность их структурирования и однозначной нумерации. Это позволит решить задачу выбора конкретных 
подстановок, которые являются неоднородными объектами мно

жеств, и количества подстановок, обладающих  определенными 
свойствами и характеристиками, а также позволит определить их 
взаимное влияние при проведении операций с группами перестановок. Все вышеупомянутое значительно повышает актуальность 
подтверждения или опровержения выдвинутой ранее гипотезы 
о взаимно однозначном соответствии. 
В части подстановок, которым посвящена данная работа, 
предметом исследования являются позиционные системы счисления, методы, способы и алгоритмы преобразования элементов 
множеств, формы представления и нумерации подстановок и в некоторой степени перестановок, их качественные и количественные 
характеристики и аксиоматические основы построения.  
К первым работам в процессе решения этой задачи по направлениям исследования относятся  работы, связанные с разработкой 
и реализацией во ВНИИЭФ метода факториального сжатия, обеспечивающего максимально возможное сжатие информации конкретных перестановок, представленных в табличном виде, при реализации их на ЭВМ. Результаты этих исследований отражены 
в работе [13]. При этом задача установления взаимно однозначного 
соответствия множеств и нумерации перестановок не решена. 
В монографии [6] рассмотрены аксиоматический метод познания и основные понятия теории множеств. Приведены определения 
алгебраических и криптографических структур, групп, колец, полей. Рассмотрены многочлены над полем, вычисления и преобразования в поле Галуа, цифровые устройства, их модель и возможные 
варианты применения. 
Настоящим прорывом в данном направлении стала работа [14], 
подтверждающая на практике ранее выдвинутую гипотезу и делающая из нее научный факт. В ней впервые предложена и рассмотрена система счисления ряда факториальных множеств, имеющая (в отличие от известных позиционных систем счисления) переменное основание и переменные позиционные коэффициенты. 
Представлены способы преобразования чисел из десятичной системы счисления в систему счисления ряда факториальных множеств и обратно, обеспечивающие обратимое и взаимно однозначное преобразование и нумерацию элементов ряда факториальных 
множеств любой размерности. Предложен способ преобразования 

образов ряда факториальных множеств в конкретные перестановки. 
В работе заявлено, что подобные системы счисления можно строить для любых упорядоченных множеств.  
По результатам анализа математической теории поля и вопросов защиты информации подготовлена и выпущена монография [7], 
где рассмотрены вопросы теории информации, модели криптографических систем и системы связи при наличии шума, условная энтропия как математическая мера неопределенности и помехоустойчивое кодирование информационных сообщений. Уточнена классификация 
алгебраических 
и 
криптографических 
структур. 
Приведены определения алгебраических структур и групп преобразований, к которым относятся подстановки и перестановки.  
Анализу подстановок и их характеристик были посвящены два 
учебных пособия [11, 12]. В них рассмотрены вопросы теории множеств, криптографические системы и алгебраические структуры. 
Основное внимание уделено подстановкам как группам преобразований, циклическим подстановкам и их свойствам (характеристикам) и общим характеристикам подстановок. 
В развитие данного направления опубликован ряд работ, направленных на анализ основных характеристических свойств элементов рядов факториальных множеств в процессе защиты информационных систем [15–19]. 
Накопленные результаты исследований и анализ полученных 
материалов показали, что из-за расширения области исследований 
наметилась некоторая неоднозначность в обозначениях и нечеткость ряда определений при проведении исследований свойств таких характеристик подстановок и перестановок, как декремент, количество независимых циклов, инверсия, четность и знак подстановок и перестановок, что потребовало проведения более 
глубокого их теоретического изучения. Одновременно это потребовало в дополнение к качественным понятиям факториальных 
множеств, ряда факториальных множеств и его системы счисления 
[11, 12, 15–19] разработки аксиоматических основ функций подстановки и перестановки в системе счисления ряда факториальных 
множеств. 
Данная работа продолжает публикацию результатов исследований в данном направлении и устраняет наметившийся пробел. 
Для создания полноценной аксиоматической теории требуется