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

• Автор: Заец, Мирослав Владимирович
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 145 с. : ил.

Оглавление
Введение

Глава 1. Свойства полиномиальных функций над примарным кольцом

вычетов

$ 1.1. Отношение сравнимости и Т-функции

$ 1.2. Формальные производные многочленов над примарным кольцом вычетов

$ 1.3. Полиномиальные функции над примарным кольцом вычетов и п-квазигруппы

$ 1.4. Мощность класса Тр2 (те)

§ 1.5. Алгоритм решения систем полиномиальных уравнений над примарным кольцом вычетов

Выводы по главе

Глава 2. Функции с вариационно-координатной полиномиальностью над кольцом вычетов
£ 2.1. Определение и общие свойства функций с вариационно-координатной полиномиальностью над кольцом вычетов
$ 2.2. Оценка числа ВКП функций от п переменных над примарным кольцом вычетов
£ 2.3. Соотношение между классами полиномиальных и ВКП-функций
£ 2.4. Алгоритм решения систем ВКП-уравнений над примарным кольцом вычетов
Выводы по главе
Глава 3. Приложения класса ВКП-функций над примарным кольцом вычетов и его обобщения
§ 3.1. ВКП-функции над примарным кольцом вычетов и п-квазигруппы
$ 3.2. Класс функций с координатной С-линейнойразрешимостью
^ 3.3. Изучение периодических свойств одного ВКП-генератора
Выводы по главе
Заключение
Список сокращений и условных обозначений
Литература
Введение
К анализу решений систем дискретных уравнений вида
(ДСП, ...,ХП) = у1(
I (1)
= У(,
где /]: А' -> Г, 1-1,Ь, - дискретные функции (X, У - конечные множества, уг е У, £ = 1, С), сводятся различные задачи обеспечения информационной безопасности. В частности, функционирование узлов переработки информации приводит к естественному формированию систем дискретных уравнений, характеризующих свойства узлов и структуру порождаемых ими преобразований. Это обстоятельство делает данную проблематику актуальной, а разработку эффективных методов решения таких систем - практически значимой. Наибольшее внимание в работах многих авторов было уделено рассмотрению этой задачи в булевом случае (например, [25, 26] и др. в библиографии там же). Вместе с тем, увеличение объемов передаваемой информации и быстродействия каналов связи приводит к необходимости рассмотрения систем вида (1) для случая преобразований в Л-значной области, прежде всего при к = 2т, т £ М. Такой переход приводит к расширению и усложнению рассматриваемых задач.
Для систем /с-значных уравнений значительную сложность представляет задание функций ^(х1, ...,хп), £ = 1,С, их формирующих. В этой связи, важным частным случаем становятся функции над коммутативными кольцами с единицей, имеющие полиномиальное представление, т.е. представление в виде некоторого многочлена. Системы таких уравнений называются полиномиальными.
Проблема анализа и решения систем полиномиальных уравнений над коммутативными кольцами с единицей рассматривалась во многих работах. Так, например, В.П. Елизаровым в [27, 28, 29, 30] представлен один из методов последовательного решения систем линейных уравнений над кольцами вычетов к > 1. В работе [23] М.М. Глуховым рассматривались вопросы сложности решения систем линейных уравнений над конечными коммутативными цепными кольцами. В [17] описан «покоординатный» метод решения систем линейных
уравнений над примарным кольцом вычетов TLpm, т> 1. Этот метод применяется и для решения полиномиальных уравнений вида /(х) = 0 от одной переменной над примарным кольцом TLpm (см. [20, 22]). Обобщение данного метода на случай колец Галуа-Эйзенштейна (т.е. конечных коммутативных цепных колец) было дано в работах [39, 41, 63] A.A. Нечаева и Д.А. Михайлова, в которых он получил название «метода покоординатной линеаризации». Метод покоординатной линеаризации (в случае примарного кольца вычетов Ърт) основывается на представлении каждой переменной в виде р-ичного разложения Xi = х[-°-) Н 1- рт~г ■ х?-*. хР е Ъ, i = 1,п, j = 0,m — 1,
ъ = { 0....р-1].
Этот метод заключается в последовательном нахождении координат хР неизвестных переменных. Сначала определяются младшие координаты хр* неизвестных переменных путем решения исходной системы, приведенной по модулю р, над полем. Затем находятся последующих координаты хР» i = 1, п, при условии, что известны координаты меньшего порядка х-° ...,хр-1 i = 1,п.
Как следствие, ПОИСК хР, i = 1, п сводится к решению системы линейных уравнений над полем. Отметим, что в указанных работах ([39, 41, 63]) описание метода приводилось для случая так называемого /?-адического координатного множества S. В настоящей диссертации будет рассматриваться /7-ичное координатное множество Ъ = (0, ...,р — 1), которое в общем случае не совпадает с /;-адическим.
В представленной диссертации идея метода покоординатной линеаризации получает обобщение и развитие. С одной стороны, конструктивно строится класс функций над примарным кольцом вычетов Ърт, расширяющий класс полиномиальных функций Трт{п). Данный класс получил название класса функций с вариационно-координатной полиномиальностью (ВКП-функций) -СРрт(п). Отметим, что для систем вида (1), у которых /i(x1, ...,хп) е СТрт (п), i = 1, t, также применим метод покоординатной линеаризации, и такие системы

для примарных колец вычетов, которая может применяться и для полиномиальных функций от нескольких переменных. В работе [40] A.A. Нечаев обобщил формулу для числа полиномиальных функций от одной переменной над конечными коммутативными локальными кольцами главных идеалов. В [52] была доказана подобная формула для колец Галуа и также приведена формула для числа полиномиальных функций от нескольких переменных. В работе [54] была обобщена функция Смарандаша ([70]) на случай нескольких переменных и с ее использованием получена формула числа полиномиальных функций от нескольких переменных над примарным кольцом вычетов. Кроме перечисленных выше источников подходы к решению вопроса о числе полиномиальных функций над различными конечными кольцами можно найти, например, в работах [51, 55, 56, 66].
Для представления следующих далее результатов исследований понадобится явная формула числа полиномиальных функций от нескольких переменных над примарным кольцом вычетов Ърг. При вычислении указанной величины будем использовать результаты, полученные в [54].
Следуя работе [54], введем следующие далее величины. Пусть к = (кх,..., кп) е Mg. Обозначим к! = ПГ=1^! и Sn(pm) = (к е М]]: рт [ к!} — множество с мощностью sn(pm) = |Sn(pm)|. При n = 1 функцию 5n(pm) называют функцией Смарандаша. Она равна наименьшему такому к EN0, при котором рт | к, и при этом ее также обозначают ß(pm). Известно (например, [40]), что число полиномиальных функций одной переменной над кольцом вычетов Zpm равно |^Ррт(1)| = p££i^(pl). Обобщение функции Смарандаша sn(Pm) позволяет вывести формулу для количества полиномиальных функций над Zpm от любого числа переменных. Сформулируем этот результат в виде следующей теоремы, полученной в той же работе.
Теорема 1.17. ([54]) Для любых т >1, п£М верно равенство:
|Ppm(n)| = p£iiisn(p‘). (1.4.1)