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

ФГБОУ ВО «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА»

Заец Мирослав Владимирович

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

05.13.19 - Методы и системы защиты информации, информационная

безопасность

На правах рукописи

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

11 авг т

Москва-2015

005561445

005561445

Работа выполнена в войсковой части № 33965

Научный руководитель: Никонов Владимир Глебович

доктор технических наук, доцент

Официальные оппоненты: Горшков Сергей Павлович;

доктор физико-математических наук, сотрудник в/ч № 71330

Логачев Олег Алексеевич

кандидат физико-математических наук, заведующий отделом Института проблем информационной безопасности ФГБОУ ВО МГУ имени М.В. Ломоносова

Ведущая организация: ФГУП «Научно-исследовательский институт

«КВАНТ», г. Москва

Защита диссертации состоится 23 сентября 2015 года в 1645 на заседании диссертационного совета Д. 501.002.16 на базе ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова», по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Главное здание, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО МГУ имени М.В. Ломоносова по адресу: г. Москва, Ломоносовский проспект, д.27, сектор А, http://istina.msu.ru/dissertations/9443660/

Автореферат разослан 23 августа 2015 г.

Ученый секретарь диссертационного совета

Д.501.002.16 на базе ФГБОУ ВО МГУ имени М.В. Ломоносова,

доктор физико-математических наук, ^

профессор /- Андрей Алексеевич Корнев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. К анализу и решению систем дискретных

где -» У, I = Тд, - дискретные функции (X, У - некоторые конечные множества, у( Е 7, 1 = 1, £), сводятся различные задачи обеспечения информационной безопасности. В частности, функционирование узлов переработки информации приводит к естественному формированию систем дискретных уравнений, характеризующих свойства узлов и структуру порождаемых ими преобразований. Это обстоятельство делает данную проблематику актуальной, а разработку эффективных методов решения таких систем - практически значимой. Наибольшее внимание в работах многих авторов было уделено рассмотрению этой задачи в булевом случае1'2. Вместе с тем, увеличение объемов передаваемой информации и быстродействия каналов связи приводит к необходимости рассмотрения систем вида (1) для случая преобразований в £-значной области, прежде всего при к = 2т, т € N. Такой переход приводит к расширению и усложнению рассматриваемых задач.

Степень разработанности темы. Для систем £-значных уравнений значительную сложность представляет задание функций /¿(х1,..., хп), £ = 1Д, их формирующих. В этой связи, важным частным случаем становятся функции над коммутативными кольцами с единицей, имеющие полиномиальное представление, т.е. представление в виде некоторого многочлена. Системы таких уравнений называются полиномиальными.

1 Горшков, С.П. Применение теории >1Р-полных задач для оценки сложности решения систем булевых уравнений / С.П. Горшков //Обозрение прикладной и промышленной математики. - 1995. - т. № 2, вып. 3. - С. 325-398. (см. и библиографию там же)

2 Глухое, М.М. Математическая логика. Дискретные функции. Теория алгоритмов / М.М. Глухов, А.Б. Шишков. -М.: Лань, 2012.-300 с.

уравнений вида

(1)

Проблема анализа и решения систем полиномиальных уравнений над коммутативными кольцами с единицей рассматривалась во многих работах. Так, например, В.П. Елизаровым3 представлен один из методов последовательного решения систем линейных уравнений над кольцами вычетов Жк, к > 1. М.М. Глуховым4 рассматривались вопросы сложности решения систем линейных уравнений над конечными коммутативными цепными кольцами. Известен также5 «покоординатный» метод решения систем линейных уравнений над примарным кольцом вычетов Zpm, m > 1. Этот метод применяется и для решения полиномиальных уравнений6 вида /Ос) = 0 от одной переменной над примарным кольцом Жрт. Обобщение данного метода на случай колец Галуа-Эйзенштейна (т.е. конечных коммутативных цепных колец) было дано в работах A.A. Нечаева и Д.А. Михайлова7, в которых он получил название «метода покоординатной линеаризации». Метод покоординатной линеаризации (в случае примарного кольца вычетов Жрт) основывается на представлении каждой переменной в виде р-ичного разложения

xt = xt(0) + - + pm-l-*((m~l). х\п е Ъ, i = ГЯ / = 0, тп — 1,

® = {0.....р-1).

Этот метод заключается в последовательном нахождении координат х^ неизвестных переменных. Сначала определяются младшие координаты х неизвестных переменных путем решения исходной системы, приведенной по

3 Елизаров, В.П. Об алгоритме последовательного решения системы линейных уравнений над кольцом вычетов/В.П. Елизаров//Труды по дискретной математике.-2008.-т. 11. - С.31-42.

4 Глухое, М.М. О сложности решения систем линейных уравнений над конечными коммутативными цепными кольцами / М.М. Глухов //Труды по дискретной математике. - 2002. — т.б.-С. 31-47.

5 Василенко, О.Н. Теоретико-числовые алгоритмы в криптографии / О.Н. Василенко. - М.: МЦНМО, 2004.-328 с.

6 Виноградов, И. М. Основы теории чисел. 8-е изд. / И.М. Виноградов. - М.: Наука, 1972.

7 Михайлов, Д.А. Решение системы полиномиальных уравнений над кольцом Галуа-Эйзенштейна с помощью канонической системы образующих полиномиального идеала / Д.А. Михайлов, A.A. Нечаев //Дискретная математика. - 2004. - т. № 1, выпуск 1. - С. 21-51.

модулю р, над полем. Затем находятся последующие координаты I = 1,п, при условии, что известны координаты меньшего порядка Х[°\ £ = 1,п. Как следствие, поиск £ = 1 ,п сводится к решению системы линейных уравнений над полем. Отметим, что в указанных работах описание метода приводилось для случая, так называемого /т-адического координатного множества В. В настоящей диссертации рассматривается р-ичное координатное множество Ъ = {0,... ,р — 1}, которое в общем случае не совпадает с /»-адическим.

Теоретическая значимость. В представленной диссертации идея метода покоординатной линеаризации получает обобщение и развитие. С одной стороны, конструктивно строится класс функций над примарным кольцом вычетов Жрт, расширяющий класс полиномиальных функций Ррт(п). Данный класс получил название класса функций с вариационно-координатной полиномиальностью (ВКП-функций) - С7>рт(п). Отметим, что для систем вида (1), у которых /¡(х1( ...,хп) е СРрт(п), I = также применим метод покоординатной линеаризации, и такие системы названы системами ВКП-уравнений. С другой стороны, предложен «аксиоматический» подход описания систем, для которых характеризующим признаком является возможность их решения методом покоординатной линеаризации. Это обстоятельство привело к появлению класса функций с координатной £-линейной разрешимостью (£-КЛР-функций) - С£Зрт(п). По своему определению эти классы имеют различную природу. Изучение данных классов в диссертации приводит к появлению новой классификации множества функций над примарным кольцом вычетов с алгоритмической точки зрения. В развитии метода покоординатной линеаризации и построении теории ВКП- и КЛР-функций заключается теоретическая значимость настоящей диссертации.

Практическая значимость. Применительно к задаче анализа и синтеза систем защиты информации, исследование систем вида (1) имеет

прикладное значение. С точки зрения анализа к исследованию систем вида (1) сводится изучение процессов функционирования широкого класса узлов переработки дискретной информации. Трудоемкость, связанная с решением таких систем, обуславливает сложность нахождения параметров узлов и блоков защиты информации. Это обстоятельство определяет актуальность построения эффективных алгоритмов решения систем вида (1) и оценки их сложности. С точки зрения синтеза, предложенный в диссертации класс ВКП-функций СРрт (п) допускает сравнительно простую алгоритмическую реализацию с помощью т полиномиальных функций, каждая из которых определяет значение соответствующей р-ичной координаты функции. Такая возможность вместе с рядом важных структурных свойств является предпосылкой для применения этих функций непосредственно в узлах и блоках аппаратуры защиты информации. В диссертации рассмотрено применение ВКП-функций для построения генераторов 2т-значных последовательностей, для которых удалось оценить период и длину подхода. Другим важным приложением в области синтеза является возможность построения с помощью функций из этого класса биективных отображений. Необходимо подчеркнуть, что датчики рекуррент и биективные отображения, имеющие сравнительно простую техническую реализацию, с аналитической точки зрения задают сложные преобразования, в общем случае не сводящиеся к полиномиальным. Аналитическая сложность вместе с возможностью компактной реализации определяет практическую значимость применения ВКП-функций при создании новых способов построения узлов переработки дискретной информации.

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

зрения узлов для систем защиты информации. К задачам исследования относятся следующие.

1. Обобщение метода покоординатной линеаризации для решения систем полиномиальных уравнений над примарным кольцом вычетов на более широкие классы функций.

2. Разработка алгоритмов решения систем ВКП- и КЛР-уравнений методом покоординатной линеаризации.

3. Изучение свойств классов ВКП- и Х-КЛР-функций.

4. Построение биективных отображений на основе ВКП-функций и обобщение соответствующих критериев биективное™ полиномиальных отображений.

5. Изучение периодических свойств некоторых семейств генераторов последовательностей над кольцом вычетов %гт< построенных с использованием ВКП-функций.

Объектом исследований в диссертации являются системы уравнений над примарным кольцом вычетов. Предмет исследований составляют классы ВКП-функций, КЛР-функций и порождаемые функциями этих классов системы уравнений над примарным кольцом вычетов.

Научная новизна диссертации определяется тем фактом, что классы ВКП- и £-КЛР-функций впервые введены автором и ранее не изучались. Вследствие этого все теоретические результаты и практические приложения являются новыми, как по исходной теоретической постановке задач, так и по методам их решения. В частности, новым является предложенный подход к классификации функций над примарным кольцом вычетов Жрт. Другим важным новым результатом являются разработанные автором алгоритмы решения систем вида (1) методом покоординатной линеаризации. В диссертации расширен класс биективных отображений, обобщающий класс полиномиальных биекций. Рассмотрен и изучен один из генераторов 2т-значных последовательностей, построенный с использованием функций из введенного класса.

Соответствие диссертации паспорту специальности. Диссертация посвящена расширению арсенала математических методов в задачах анализа и синтеза узлов защиты информации и соответствует паспорту специальности 05.13.19 (физико-математические науки). А именно, в п. 1 в качестве области исследований указана «Теория и методология обеспечения информационной безопасности и защиты информации», что соответствует развитию в диссертации теории так называемых ВКП-функций и их применения в узлах защиты информации. Далее, в п. 9 указаны «Модели и методы оценки защищенности информации и информационной безопасности объекта», что в полной мере отвечает разработанным методам анализа и решения систем ВКП-уравнений - новой модели, актуальной в задачах информационной безопасности. И, наконец, в п. 13 отмечены «Принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности». Данному пункту соответствуют результаты третьей главы диссертации, в которой предложены новые решения по синтезу биективных отображений и по построению генераторов дискретных последовательностей с использованием ВКП-функций.

Методология и методы исследования. Диссертационное исследование проводилось алгебраическими, комбинаторными и теоретико-автоматными методами, включая использование теории А>значных функций.

Положения, выносимые на защиту.

1. Разработан метод покоординатной линеаризации решения систем уравнений над примарным кольцом вычетов для классов ВКП-функций и КЛР-функций ([1,2, 3, 4]);

2. Проведены классификационные исследования функций над примарным кольцом вычетов, основанные на применении метода покоординатной линеаризации ([1,2, 5,7, 8,10]);

3. Разработаны новые способы построения биективных отображений на основе ВКП-функций, представляющие интерес для синтеза блоков защиты информации ([6,9]);

4. Предложены схемы датчиков последовательностей на основе ВКП-функций ([11]).

Апробация работы. Результаты диссертационного исследования докладывались на следующих семинарах и конференциях:

• на семинаре «Математические методы криптографического анализа» кафедры Информационной безопасности факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова (в 2014,2015 гг.);

• на Всероссийской конференции «Сибирская научная школа-семинар с международным участием 'Компьютерная безопасность и криптография' - ЗЮЕСЯУРПЗ» (2-7 сентября 2013 г., г. Томск);

• на XX Всероссийской Школе-коллоквиуме по стохастическим методам и XIV Всероссийском Симпозиуме по прикладной и промышленной математике (12-18 мая 2013 г., г. Йошкар-Ола);

• на ХЫ Международной конференции, XI Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе '1Т+5Е13'» (25 мая - 4 июня 2013 г., г. Ялта, Р. Крым)

• на Всероссийской конференции «Сибирская научная школа-семинар с международным участием 'Компьютерная безопасность и криптография' - ЗШЕСЯУРГМ» (8-12 сентября 2014 г., г. Екатеринбург)

Достоверность всех полученных результатов обосновывается корректностью постановок задач и строгими математическими доказательствами теоретических утверждений. Проверка корректности результатов осуществлялась также с использованием вычислительных экспериментов.

Публикации по теме диссертации. Основное содержание диссертации опубликовано в 11 работах [1-11]. Из них шесть статей в рецензируемых журналах [1-6], из которых [1-4] - статьи в журналах, включенных в перечень ВАК РФ, рекомендованных для публикации основных научных результатов диссертаций. Пять публикаций [7-11] - в материалах международных и всероссийских конференций.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка сокращений и условных обозначений, и списка литературы, включающего 72 наименования. Общий объем диссертации составляет 145 страниц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе доказываются основные результаты о полиномиальных функциях над примарным кольцом вычетов, которые будут необходимы в последующих главах диссертации. В § 1.1 определяются координатные функции элементов примарного кольца вычетов уу: Жрт -> Ъ,

) = 0,т - 1, 3 = {0,..., р — 1}, по правилу:

т-1

X = ^ р/. хО), уДх) = хи). 1=0

Аналогично, определяются координатные функции Yjf^• %рт -* В, / = О,т -1, функций /(х) е Трт(п), где Трт(п) - класс всех функций от п переменных над кольцом вычетов Жрт, по правилу:

(/;•/)(«) = К/(ЯяО)- Я 6 ж;т.

Далее в § 1.1 вводится понятие треугольной, или Т-функции, над примарным кольцом вычетов, аналогичное одноименному понятию в работах

B.C. Анашина8 (определение 1.10). Устанавливается, что класс Т-функций над примарным кольцом вычетов совпадает с классом 2>рт(л) - всех функций, сохраняющих отношение сравнимости по любому делителю рт (теорема 1.3). В § 1.2 доказываются некоторые свойства формальных частных производных и координатных отображений полиномиальных функций. В § 1.3 приводится обзор известных результатов о биективных полиномиальных вектор-функциях, полиномиальных и-квазигруппах и равновероятных (сбалансированных) полиномиальных функциях9. В § 1.4 автором доказывается утверждение о мощности класса полиномиальных функций !Ррг(п) от п переменных над примарным кольцом вычетов Zpz (утверждение 1.18):

|Ур2(п)| = рР"С"+« В § 1.5 приводится авторское изложение алгоритма решения систем полиномиальных уравнений, основанного на методе покоординатной линеаризации, для случая примарного кольца вычетов Zpm и р-ичного координатного множества В = {0, ..,,р — 1]. В данном параграфе рассматриваются также оценки сложности приведенного алгоритма в некоторых частных случаях.

Во второй главе диссертации автором вводится основное и важное понятие исследования - функции с вариационно-координатной полиномиальностью (определение 2.1).

Определение 2.1. Функцию /(х) Е Трт(п), т ЕМ, назовем вариационно-координатно полиномиальной (или ВКП-фунщией), если для любого j 6 0,7П — 1 существует полиномиальная функция Ру(х) Е Ррт(п), j-я координатная функция которой совпадает с j-й координатной функцией функции /(х), т.е. выполняется равенство:

8 Anashin. V. Applied Algebraic Dynamics / V. Anashin, A. Khrennikov. - de Gruyter Expositions in Mathematics, vol. 49 Walter de Gruyter, Berlin-New York, 2009.

s Lausch, H. Algebra of polynomials / H. Lausch, W. Nöbauer. - Amsterdam; North-Holl. Publ. Co. -1973.-356 p.

YjfOO = Y]Pj(x). j = 0,m~ 1. В § 2.1 доказываются важные свойства таких функций: включение полиномиальных функций во введенный класс (теорема 2.1), принадлежность классу Z)pm(n) (теорема 2.2), теорема о строении координатных функций (теорема 2.3).

Теорема 2.3. Если f 6 С!Ррт(п), то для любого j е l,m - 1 существуют функции gji-."Bn -* Ъ, -* Ъ, i = 1,п, над полем Ъ такие, что

выполнено равенство:

71

У;/(х<°>.....xW) = £fl;t(x(0)) ® я« 0 .....х«"»).

i=1

Доказывается формула Тейлора (теорема 2.4), обобщающая формулу

Тейлора для полиномиальных функций (утверждение 1.610).

Теорема 2.4. Если функция /(х) е СТрт(п) и р0(х), ...,pm_i(x) - ее

координатные многочлены, то для любых у 6 1,т— 1 и h £ справедливо

сравнение:

/(х + р' • h) = /(х) + р]' ■ gradpy(x) • h* (modp^1), 5<3egradp/(x)-h1=5;p=1g(x)-hi.

В § 2.1 вводится также понятие функции с вариационно-координатной полиномиальностью над произвольным кольцом вычетов TLK,k> 1 (определение 2.2). В § 2.2 выводится оценка мощности класса ВКП-функций (утверждение 2.8):

logp|e:Ppm(n)| £рп + (т- 1 )л • рп + -—-.

Далее, в § 2.3 изучаются соотношения между классами ВКП- и полиномиальных функций: в теореме 2.9 доказывается, что классы полиномиальных Ург (п) и ВКП-функций CPpi(n) совпадают в случае

(pn(m-1) _ ^

10 Михайлов, ДА. Решение системы полиномиальных уравнений над кольцом Галуа-Эйзенштейна с помощью канонической системы образующих полиномиального идеала / Д.А. Михайлов , А.А. Нечаев//Дискретная математика. -2004. - т. № 1, выпуск 1. - С. 21-51.

примарного кольца Ърг. В теореме 2.10 доказывается достаточное условие отсутствия полиномиального представления для ВКП-функции, в теореме 2.14 показывается, что классы ВКП- и полиномиальных функций над примарным кольцом вычетов 2рт не совпадают при т > 3. В § 2.4 обосновывается и излагается алгоритм решения систем ВКП-уравнений, основанный на методе покоординатной линеаризации и являющийся обобщением алгоритма из первой главы (§ 1.5). Доказывается корректность алгоритма (теорема 2.15) и выводятся оценки его сложности (теорема 2.16 и ее следствия).

Третья глава диссертации посвящена различным приложениям ВКП-функций в задачах анализа и синтеза узлов переработки дискретной информации. В § 3.1 приводятся результаты о биективных ВКП-функциях. В том числе, доказывается критерий биективности ВКП вектор-функции (теорема 3.1), обобщающий критерий биективности полиномиальной вектор-функции (теорема 1.14й).

Теорема 3.1. ВКП вектор-функция F(x) = (Д(х),..., fn(x)):lpm -> 1рт задает биекцию тогда и только тогда, когда одновременно выполняются следующие условия:

1) F0(x) (mod р) задает биекцию на Ъп;

2) для любого j 6 1, т - 1 якобиан |jF>(a)| (modp) отличен от нуля при всех а е Ъп.

Как следствие доказывается критерий подстановочности ВКП-функции от одной переменной (обобщение теоремы 1.1012). В теореме 3.2 доказывается критерий для ВКП-функции, позволяющий задавать л-квазигруппу. Такие п-квазигруппы названы ВКП и-квазигруппами.

11 Lausch, Н. Algebra of polynomials / Н. Lausch, W. Nöbauer. - Amsterdam: North-Holl. Publ. Co. -1973.-356 p.

12 Нечаев. A.A. Полиномиальные преобразования конечных коммутативных локальных колец главных идеалов / A.A. Нечаев //Мат. заметки. - 1980. - т.27, вып.6. - С. 885-899.

Теорема 3.2. Функция /(х) G СРрт(п), с координатными многочленами р0(х), ....Pm-lix) задает п-квазигруппу на кольце Ърт тогда и только тогда, когда одновременно выполняются следующие условия:

1) ро(х) (modp) задает п-квазигруппу на В;

2) для любого jel.m — 1 gradpy(a) (modp) не содержит нулевых координат при любом а е Вп.

В § 3.1 вводится также понятие класса квази-ВКП-функций - QCPpm(n), являющегося обобщением класса ВКП-функций (определение 3.3). Определение 3.3, Функцию /(х) е Трт(п) назовем квази-вариационно-координатно полиномиальной (или квази-ВКП-функцией), если выполнены условия:

1. Уо/W = Уо/(х(0)) = 5о(х(0)), д0:Ъп -» В;

2. для любого j el, m — 1: К;/(х) = уу/(х(0), ...,ху)) и существуют функции g ¡с- Ъп -» В, g¡: Ъ1п -» В, г = 1,72, wad нолем В такие, что справедливо равенство:

п

Yjf(x{0).....xW) = £ 5;¡(XW) <g> x« © 5;(х<°>.....xü-«).

(=i

Доказывается, что любой парастроф ВКП и-квазигруппы является квази-ВКП-функцией (теоремы 3.6, 3.7). В теореме 3.9 приводится достаточное условие для ВКП-функции быть равновероятной (обобщение утверждения 1.1513):

Теорема 3.9. Если /(х) G С!Ррт(п) имеет координатные многочлены р0(х), ....,рт_1(х) и для них выполнены следующие условия:

1) Ро(х) (mod р) - равновероятная функция над полем В;

2) gradpy(a) г в (modp) при любых а е Bn, j 6 1,тл - 1, где в -нулевой вектор,

13 Anashin, V. S. Uniformly distributed sequences in computer algebra or how to construct random number generators / V.S. Anashin //J. Math. Sei. (Plenum Publishing Corp., New York) - 1998. - vol. 89 №4. -p. 1355- 1390.

то функция /(х) -равновероятная.

В § 3.2 вводится определение функции с координатной ¿-линейной разрешимостью, £ 5 0,m — 1, (определение 3.4).

Определение 3.4. Функцию /(х) 6 Трт(п) назовем координатно L-линейно разрешимой (или L-KJIP-функцией), ££0,m —1, если она является Т-функцией и при любом j 6 £, j Ф 0, существуют такие функции дп,ду.Ъп1 Ъ, i = Гп, что

YjfOO = У//(х(0).....х«) =

п

= £ 5;i(x(0).....хСМ>) ® е .....xO-D),

¡=1

м ирм 0 6 £ существуют такие gol, д0 Е Ъ, i = 1, п, что

п

Уо/(х) = Уо/(х(0)) = ^ Soi ® *f(0) © i=i

Приводятся простейшие свойства введенного класса функций C£Spm(n) и изучаются соотношения с введенными ранее классами -полиномиальными, ВКП- и квази-ВКП-функциями. А именно, показывается (утверждение 3.11), что при £ 5 1,т - 1 справедлива цепочка включений:

Ррт(п) S СРрт(п) £ QCJ>pm(n) S C£Spm(n). В теореме 3.15 при £ = 1 ,т — 1 уточняется вопрос о строгости включений данной цепочки.

Теорема 3.15. Пусть £ = 1,т— 1, тогда справедливы утверждения.

1. При m > 3 верна цепочка включений:

J>pm(n) Ç С!Ррт(п) S QOPpm(n) Ç СЩт(п).

2. Верна цепочка равенств:

г»р»(п) = eyp2(n) = QCTv,(n) = сЩг{п).

Далее, в § 3.2 доказываются теоремы о вычислении мощности классов £-KJIP- и квази-ВКП-функций (теоремы 3.13, 3.14). Показывается, что класс £-КЛР-функций (£ = 1, m - 1) совпадает с классом 2)pm(n) тогда и только

тогда, когда одновременно р = 2, тг = 1 (утверждение 3.16). Также в § 3.2 устанавливается замкнутость классов £-КЛР- и квази-ВКП-функций (теорема 3.17, утверждение 3.18). В заключение параграфа обосновывается (утверждение 3.19) и приводится алгоритм решения систем £-КЛР-уравнений при £ = 1, т. — 1, основанный на методе покоординатной линеаризации и обобщающий алгоритм из второй главы (§ 2.4).

В заключительном § 3.3 рассматривается один генератор над кольцом вычетов Ж2т, в котором используется ВКП-функция. Вводится понятие вариационно-коодинатно линейной функции, т.е. такой ВКП-функции, у которой все координатные многочлены линейны, и соответственно определяется класс С£2т(2). Изучаются вопросы строения ЛРП-семейств координатных последовательностей (теорема 3.22, утверждение 3.23),

вырабатываемых таким генератором.

Теорема 3.22. Пусть f(x, у) е С£2т(2) имеет координатные многочлены Pj У) = ajx+bjy, j = 0, m — 1. Справедливы утверждения:

1. младшая координатная последовательность v0 Е 1Ъ (/оМ)< /о 00 =

© Ь^х © а(00);

2. если aj = 1 (modV), 2^\bj, jel.m-l, то при Ь;а)) = (0,0) или при v0[0,n - 1] = 9 выполняется: Vj 6 L3(хп © 1), во всех остальных случаях Vj 6 LB((xn © 1 )/0(х));

3. если bj = 1 (mod 2J), 2'\ajt j G l,m - 1, mo r/ш (<z}°, by0)) = (0,0) или при u0[0,n —1] = 0 выполняется: G Ls(xn ®x), во всех остальных случаях vj E Ь-в((хп ф x)/0(x)). Доказывается теорема о верхней оценке периода вырабатываемой генератором последовательности (теорема 3.25).

Теорема 3.25. Пусть /(х, у) G С£2™(2) и имеет координатные многочлены Pj(x,y) = CLjX+bjy, j G l,77i - 1, Po(x,y) = x + y, при этом /оM = xn 8 x © 1 является примитивным многочленом над Ъ и r>D[0,n — 1] Ф 9. Тогда справедливы утверждения:

1. если для любого j G l,m - 1 aj = 1 (mod2^), 2!\Ь], mo A(u) = О uT(u)\[n,2n-l\,

2. если для любого j G l,m — 1 bj s 1 (mod 2J), 2^|а/, mo A(u) < 1 и Т(ц) | [тг — 1,2" — 1];

3. если существуют i,j G 1,т — 1 такие, что: й, = 1 (mod 2'), 2'jbt и

b} = 1 (mod 2^), 2; |a;-, то А(и) < 1 и Г (и) | п^г" - 1), где Uj. =

п _ п-1

(П,2п-1) " "2 ~ (п-1,2п-1)'

Приводится достаточное условие достижимости указанной верхней

границы (теорема 3.28 и ее следствие).

Для вектора v = (v0,...,i7n_1) G Ъп обозначим через /v(x) многочлен

из В[х] степени не большей п-1, определяемый следующим образом:

п-1

ш=Y, n~i~i-1=0

Теорема 3.28. Пусть f G e£2m(2), где Pj(x,y) = ajx+b}y, j G 1,тп - 1, Poix,y) = x + y, и при этом /0(х) = хп ® х ф 1 является примитивным многочленом над Ъ и v0[0,n- 1] Ф 9. Тогда справедливы утверждения: 1. если для j G 1, m - 1 такого, что а} = 1 (mod2J), 2^, (a^.b^ = (0,1) верно:

(хп ф 1. /vj©v0w) = 1.

где Vy = уДО.п- 1], v0 = u0[0,n - 1], mo

2. если для j e 1,m - 1 такого, что bj = 1 (mod 2J),2j\aj, =

(1,0) верно:

(x"-1 e /v;©v0M) = i, где V,- = Vy[l,n — 1], v0 = u0[l,n— 1], mo

T(vj) = [n-l,2n-l]. Следствие. Пусть f G C£2m(2) имеет координатные многочлены Pj(x,y) =

djX+bjy, j G l,m - 1, p0(x, у) = x + y, ири э/иам /0(х) = xn ф x ф 1

является примитивным многочленом над Ъ и ио[0, п — 1] Ф 9. Тогда справедливы следующие далее утверждения.

1. Если для любого j Е 1,т— 1 а,- = 1 (mod 2>), 2>\bj, и хотя бы для одной из координатных последовательностей выполняется условие 1 теоремы, то

Т(и)= [п,2»-1].

2. Если для любого ) е 1,тп — 1 Ь] = 1 (mod 2;), 2^|ау, и хотя бы ¿ля одной из координатных последовательностей выполняется условие 2 теоремы, то

Т(и) = [п - 1,2П — 1].

3. Если найдутся две такие координатные последовательности, что для одной из них выполнено условие 1 теоремы, а для другой условие 2, то

Г(и) = щп2{2" - 1),

п п-1

гдеп1=77Т^ип2 =

(п, 2n—1) г- (п-1,2п-1)' В заключение диссертации приводятся основные результаты исследования.

ЗАКЛЮЧЕНИЕ

В диссертации автором были получены следующие основные результаты.

1. Метод покоординатной линеаризации решения систем полиномиальных уравнений над примарным кольцом вычетов обобщен на классы ВКП- и КЛР-функций. Приведены алгоритмы решения систем ВКП- и КЛР-уравнений указанным методом с доказательством их корректности и оценками сложности.

2. Построена классификация функций над примарным кольцом вычетов, основанная на применении метода покоординатной линеаризации. Введены понятия и описаны общие свойства классов ВКП-, квази-ВКП, КЛР-функций, расширяющих в общем случае класс полиномиальных функций.

3. Доказаны критерии биективности преобразований примарного кольца вычетов для ВКП-функций, что дало новые способы построения биекций, не являющихся полиномиальными.

4. Построены неполиномиальные генераторы последовательностей над кольцом вычетов Ъгт с использованием ВКП-функций в качестве функции обратной связи. Для таких генераторов получена верхняя оценка периода выходной последовательности и достаточные условия ее достижимости.

Актуальность, новизна и практическая значимость проведенного исследования подтверждаются тем, что оно включено в тему Академии криптографии РФ, по которой был выполнен принятый и одобренный в 2013 г. отчет.

В качестве перспектив дальнейшей разработки темы диссертации можно предложить изучение различных параметров и характеристик дискретных функций применительно к ВКП- и КЛР-функциям. Например, изучение вопросов близости рассматриваемых функций к гомоморфизмам абелевых групп -» (2рт, +) и поиск минимальных функций в

классе названных функций. Также интерес представляет вычисление степени нелинейности или ее оценки для ВКП-функций. Другим интересным направлением продолжения исследований является обобщение введенных в работе конструкций на более широкие алгебраические структуры. В этом направлении автором исследования были получены первые результаты по обобщению класса ВКП-функций на кольца Галуа GR(qm,pm), т > 1, и произвольные координатные множества 3 (см. работу [9]).

БЛАГОДАРНОСТЬ Автор выражает глубокую благодарность научному руководителю члену-корреспонденту, д.т.н., доценту Владимиру Глебовичу Никонову за постановку задач и постоянное внимание к работе.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Заец, М.В. Функции с вариационно-координатной полиномиальностью и их свойства / М.В. Заец, В.Г. Никонов, А.Б. Шишков //Открытое образование. - 2012. - № 3. - С. 57-61. (Лично Заецу М.В. принадлежит определение понятия класса ВКП-функций, доказательство соотношений его с классом полиномиальных функций в частных случаях, описание алгоритма решение систем ВКП-уравнений)

2. Заец, М.В. Класс функций с вариационно-координатной полиномиальностью над кольцом Ж2™ и его обобщение / М.В. Заец, В.Г. Никонов, А.Б. Шишков //Мат. вопросы криптографии. - 2013. - т.4 № 3. - С. 19-45. (Лично Заецу М.В. принадлежат определения понятий классов ВКП-функций, КЛР-функций, доказательство соотношений данных классов с классом полиномиальных функций, доказательство утверждений о замкнутости и оценке мощности класса КЛР-функций, описание алгоритма решение систем КЛР-уравнений)

3. Заец, М.В. О классе вариационно-координатно полиномиальных функций над примарным кольцом вычетов / М.В. Заец//Прикладная дискретная математика. - 2014.- № 3. - С. 12-28.

4. Заец, М.В. Построение подстановок с использованием вариационно-координатно полиномиальных функций над примарным кольцом вычетов / М.В. Заец //Мат. вопросы криптографии - 2015. - т.б № 1. - С.5-32 .

5. Заец, М.В. Координатно-линейно разрешимые функции над примарным кольцом вычетов и метод покоординатной линеаризации [Электронный ресурс] / М.В. Заец //Сетевой научный журнал «Образовательные ресурсы и технологии» - 2014. - № 2(5). - С. 59-72. Режим доступа: http://www.muiv.ru/vestnik/pdf/pp/ot 2014 2 59-72.pdf.

6. Заец, М.В. О периодических свойствах одного вариационно-координатно линейного генератора над кольцом вычетов [Электронный ресурс] / М.В. Заец //Сетевой научный журнал «Образовательные ресурсы и технологии» - 2014. - № 2(5). - С. 94-102. Режим доступа; http://www.muiv.ru/vestnik/pdf/pp/ot_2014_2_94-102.pdf.

7. Заец, М.В. Решение систем полиномиальных уравнений методом покоординатной линеаризации над примарным кольцом вычетов / М.В. Заец, В.Г. Никонов //Материалы ХЫ Международной конференции, XI Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе». -Вестник Московского университета имени С.Ю. Витте. - 2013. - серия 1 (приложение) - С. 157-159. (Лично Заецу М.В. принадлежит формальное описание метода покоординатной линеаризации для систем полиномиальных уравнений)

8. Заец, М.В. Решение систем ВКП-уравнений методом покоординатной линеаризации над примарным кольцом вычетов / М.В. Заец //Материалы ХЫ Международной конференции, XI Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе '1Т+8Е13'». - Вестник Московского университета имени С.Ю. Витте. - 2013. - серия 1 (приложение) - С. 155157.

9. Заец, M.B. Классы полиномиальных и вариационно-координатно полиномиальных функций над кольцом Галуа / М.В. Заец//Материалы Всероссийской конференции «Сибирская научная школа-семинар с международным участием 'Компьютерная безопасность и криптография'

- SIBECRYPT13». - Прикладная дискретная математика. - 2013. - № 6 (Приложение).- С. 13-15.

10. Заец, М.В. Некоторые свойства функций с вариационно-координатной полиномиальностью над примарным кольцом вычетов [Электронный ресурс] / М.В. Заец //Материалы XX Всероссийской Школы-коллоквиума по стохастическим методам и XTV Всероссийского Симпозиума по прикладной и промышленной математике, 2013 г. Режим доступа: http://www.tvp.ru/conferen/vsppml4/novio051 .pdf.

11. Заец, М.В. Классификация функций над примарным кольцом вычетов в связи с методом покоординатной линеаризации / М.В. Заец //Материалы Всероссийской конференции «Сибирская научная школа-семинар с международным участием 'Компьютерная безопасность и криптография'

- SIBECRYPT14». - Прикладная дискретная математика. - 2014. -№ 7 (Приложение). - С. 16-19.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡00 экз. Заказ Кг32.