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

• Заец, Мирослав Владимирович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Заец, Мирослав Владимирович

Оглавление

Введение

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

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

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

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

$ 1.4. Мощность класса (п)

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

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

Глава 2. Функции с вариационно-координатной полиномиальностью над кольцом вычетов

£ 2.1. Определение и общие свойства функций с вариационно-координатной полиномиальностью над кольцом вычетов

£ 2.2. Оценка числа ВКП функций от п переменных над примарным кольцом вычетов

$ 2.3. Соотношение между классами полиномиальных и ВКП-функций

$ 2.4. Алгоритм решения систем ВКП-уравнений над примарным кольцом вычетов

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

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

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

$ 3.2. Класс функций с координатной С-линейнойразрешимостью

$ 3.3. Изучение периодических свойств одного ВКП-генератора

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

Заключение

Список сокращений и условных обозначений

Литература

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

Введение

К анализу решений систем дискретных уравнений вида

А(.х1> — >хп) = У\>

\ (1) ■■■' хп) = Уь>

где /¿:Х->У, ¿ = 1, - дискретные функции (X, У - конечные множества, 6 У, I — 1, £■), сводятся различные задачи обеспечения информационной безопасности. В частности, функционирование узлов переработки информации приводит к естественному формированию систем дискретных уравнений, характеризующих свойства узлов и структуру порождаемых ими преобразований. Это обстоятельство делает данную проблематику актуальной, а разработку эффективных методов решения таких систем - практически значимой. Наибольшее внимание в работах многих авторов было уделено рассмотрению этой задачи в булевом случае (например, [25, 26] и др. в библиографии там же). Вместе с тем, увеличение объемов передаваемой информации и быстродействия каналов связи приводит к необходимости рассмотрения систем вида (1) для случая преобразований в ^-значной области, прежде всего при к = 2т, т е N. Такой переход приводит к расширению и усложнению рассматриваемых задач.

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

Проблема анализа и решения систем полиномиальных уравнений над коммутативными кольцами с единицей рассматривалась во многих работах. Так, например, В.П. Елизаровым в [27, 28, 29, 30] представлен один из методов последовательного решения систем линейных уравнений над кольцами вычетов Жк, к > 1. В работе [23] М.М. Глуховым рассматривались вопросы сложности решения систем линейных уравнений над конечными коммутативными цепными кольцами. В [17] описан «покоординатный» метод решения систем линейных

уравнений над примарным кольцом вычетов TLpm, т > 1. Этот метод применяется и для решения полиномиальных уравнений вида f(x) = 0 от одной переменной над примарным кольцом TLp™ (см. [20, 22]). Обобщение данного метода на случай колец Галуа-Эйзенштейна (т.е. конечных коммутативных цепных колец) было дано в работах [39, 41, 63] A.A. Нечаева и Д.А. Михайлова, в которых он получил название «метода покоординатной линеаризации». Метод покоординатной линеаризации (в случае примарного кольца вычетов 7Lpm) основывается на представлении каждой переменной в виде /»-ичного разложения xi = x*>°:> + - + pm-1'xlm~1\ х^ЕЪ, i= ТТтг, j = 0,т — 1,

® = {0, ...,р — 1}.

Этот метод заключается в последовательном нахождении координат х^

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

модулю р, над полем. Затем находятся последующих координаты i — 1,п,

(о) 0-1) ■ я—

при условии, что известны координаты меньшего порядка х> , ...,хУ , i = 1, п.

Как следствие, поиск i — 1,п сводится к решению системы линейных

уравнений над полем. Отметим, что в указанных работах ([39, 41, 63]) описание метода приводилось для случая так называемого /?-адического координатного множества Ъ. В настоящей диссертации будет рассматриваться р-ичное координатное множество Ъ = {0, — 1}, которое в общем случае не совпадает с /7-адическим.

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

полиномиальных функций Тргп(п). Данный класс получил название класса функций с вариационно-координатной полиномиальностыо (ВКП-функций) -СТрт(п). Отметим, что для систем вида (1), у которых /¿(х1( ...,хп) е СТрт(п), i = 1, t, также применим метод покоординатной линеаризации, и такие системы

названы системами ВКП-уравнений. С другой стороны, предложен «аксиоматический» подход описания систем, для которых характеризующим признаком является возможность их решения методом покоординатной линеаризации. Это обстоятельство привело к появлению класса функций с координатной £-линейной разрешимостью (Х-КЛР-функций) - С£$рт(п). По своему определению эти классы имеют различную природу. Изучение данных классов в диссертации приводит к появлению новой классификации множества функций над примарным кольцом вычетов с алгоритмической точки зрения. В развитии метода покоординатной линеаризации и построении теории ВКП- и КЛР-функций заключается теоретическая значимость настоящей диссертации.

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

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

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

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

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

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

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

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

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

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

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

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

Структурно диссертация состоит из введения, трех глав и заключения. В первой главе доказываются основные результаты о полиномиальных функциях над примарным кольцом вычетов, которые будут необходимы в последующих главах диссертации. В § 1.1 вводится понятие треугольной, или Т-функции, над примарным кольцом вычетов, аналогичное одноименному понятию в работах B.C. Анашина [48, 49, 50]. Устанавливается, что класс Т-функций над примарным кольцом вычетов совпадает с классом Т)рт(п) - всех функций, сохраняющих отношение сравнимости по любому делителю рт (теорема 1.3). В § 1.2 доказываются некоторые свойства формальных частных производных и координатных отображений полиномиальных функций. В § 1.3 приводится обзор известных результатов о биективных полиномиальных вектор-функциях, полиномиальных и-квазигруппах и равновероятных (сбалансированных) полиномиальных функциях (см. работы [40, 50, 60, 61, 64, 67]). В § 1.4 доказывается утверждение о мощности класса полиномиальных функций "Ррг (п) от п переменных над примарным кольцом вычетов Жрг (утверждение 1.18). В § 1.5 приводится изложение алгоритма решения систем полиномиальных уравнений, основанного на методе покоординатной линеаризации, для случая примарного кольца вычетов Жрт и р-ичного координатного множества Ъ = {0, ...,р —1}. В данном параграфе рассматриваются также оценки сложности приведенного алгоритма в некоторых частных случаях.

Во второй главе диссертации вводится основное и важное понятие исследования - функции с вариационно-координатной полиномиальностыо (определение 2.1). В § 2.1 доказываются важные свойства таких функций: включение полиномиальных функций во введенный класс (теорема 2.1), принадлежность классу Т)рт{п) (теорема 2.2), теорема о строении координатных функций (теорема 2.3), формула Тейлора (теорема 2.4), обобщающая формулу

Тейлора для полиномиальных функций (утверждение 1.6, [41]). В первом параграфе вводится также понятие функции с вариационно-координатной полиномиальностыо над произвольным кольцом вычетов Жк, к > 1 (определение 2.2). В § 2.2 выводится оценка мощности класса ВКП-функций (утверждение 2.8). Далее, в § 2.3 изучаются соотношения между классами ВЕН- и полиномиальных функций: в теореме 2.9 доказывается, что классы полиномиальных Трг (п) и ВКП-функций СТр2 (п) совпадают в случае примарного кольца Ърг. В теореме 2.10 доказывается достаточное условие отсутствия полиномиального представления для ВКП-функции, в теореме 2.14 показывается, что классы ВКП-и полиномиальных функций над примарным кольцом вычетов Ърш не совпадают при 771 > 3. В § 2.4 второй главы обосновывается и излагается алгоритм решения систем ВКП-уравнений, основанный на методе покоординатной линеаризации и являющийся обобщением алгоритма из первой главы (§ 1.5). Доказывается корректность алгоритма (теорема 2.15) и выводятся оценки его сложности (теорема 2.16 и ее следствия).

Третья глава диссертации посвящена различным приложениям ВКП-функций в задачах анализа и синтеза узлов переработки дискретной информации. В § 3.1 приводятся результаты о биективных ВКП-функциях. В том числе, доказывается критерий биективности ВКП вектор-функции (теорема 3.1), обобщающий критерий биективности полиномиальной вектор-функции (теорема 1.14, [60]). Как следствие доказывается критерий подстановочности ВКП-функции от одной переменной (обобщение теоремы 1.10, [40]). В теореме 3.2 доказывается критерий для ВКП-функции, позволяющий задавать «-квазигруппу. Такие «-квазигруппы названы ВКП »-квазигруппами. В § 3.1 вводится также понятие класса квази-ВКП-функций - QCTpm(ri), являющегося обобщением класса ВКП-функций (определение 3.3). Здесь же доказывается, что любой парастроф ВКП «-квазигруппы является квази-ВКП-функцией (теоремы 3.6, 3.7). В теореме 3.9 приводится достаточное условие для ВКП-функции быть равновероятной (обобщение утверждения 1.15, [50]). В § 3.2 вводится

определение функции с координатной ¿-линейной разрешимостью, £ £ 0, т — 1, (определение 3.4). Приводятся простейшие свойства введенного класса функций С£5рт (п) и изучаются соотношения с введенными ранее классами -полиномиальными, ВКП- и квази-ВКП-функциями. А именно, показывается (утверждение 3.11), что при £ Е 1, т — 1 справедлива цепочка включений: Трт(п) С СТрт(п) С дСРрт(п) С С£5рт(п).

В теореме 3.15 при £ = 1,т — 1 уточняется вопрос о строгости включений данной цепочки. В частности, удается показать, что в случае кольца Жр2 все четыре рассматриваемые классы совпадают. Далее, во втором параграфе доказываются теоремы о вычислении мощности классов £-КЛР- и квази-ВКП-функций (теоремы 3.13, 3.14). Показывается, что класс £-КЛР-функций {£ = 1, т — 1) совпадает с классом Ърт (п) тогда и только тогда, когда одновременно р = 2, п = 1 (утверждение 3.16). Также во втором параграфе устанавливается замкнутость классов £-КЛР- и квази-ВКП-функций (теорема 3.17, утверждение 3.18). В заключение параграфа обосновывается (утверждение 3.19) и приводится алгоритм решения систем £-КЛР-уравнений при £ = 1, т — 1, основанный на методе покоординатной линеаризации и обобщающий алгоритм из второй главы (§ 2.4). В заключительном § 3.3 рассматривается один генератор над кольцом вычетов Ж2т, в котором используется ВКП-функция, изучаются вопросы строения ЛРП-семейств координатных последовательностей (теорема 3.22, утверждение 3.23), вырабатываемых таким генератором. Доказывается теорема о верхней оценке периода вырабатываемой генератором последовательности (теорема 3.25), а также приводится достаточное условие достижимости указанной верхней границы (следствие к теореме 3.28).

В заключение диссертации приводятся основные выводы исследования.

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

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

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

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

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

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

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

81ВЕСЮТТ'13» (2013 г.);

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

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

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

81ВЕСКУРТ'14» (2014 г.)

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

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

Далее при изложении результатов диссертации будем придерживаться следующего порядка. Все утверждения, которые были доказаны не автором, будут содержать ссылки на оригинальные работы. Формулы будем нумеровать с помощью трех позиций: (х.у.г), где х - номер главы, у — номер параграфа, г -порядковый номер формулы в параграфе.

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

В данной главе представлены полученные автором необходимые для дальнейших исследований свойства полиномиальных функций над примарным кольцом вычетов. Автором рассматривается важное понятие - треугольной, или Т-функции, над примарным кольцом вычетов. Доказаны некоторые свойства координатных функций полиномиальных функций и формальных частных производных многочленов, которые понадобятся во второй главе. В § 1.3 дан краткий обзор известных результатов о биективных полиномиальных функциях, которые в третьей главе будут обобщены автором на класс ВКП-функций, а также получен критерий того, что полиномиальная функция задает «-квазигруппу. В последнем параграфе приведено авторское изложение алгоритма решения систем полиномиальных уравнений над примарным кольцом вычетов. Этот алгоритм основан на методе покоординатной линеаризации, в случае />-ичного координатного множества. В последующих главах этот метод будет обобщен на другие классы функций. Результаты настоящей главы опубликованы в работах [3, 7].

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

Сначала приведем краткий обзор свойств функций, сохраняющих отношение сравнимости. Эти свойства в дальнейшем понадобятся для описания свойств изучаемого в настоящей работе класса функций. Ниже для функции /(*!,...,хп) от переменных х1,...,хп, будем использовать краткую запись /(х). Класс всех функций от п переменных над кольцом вычетов TLk обозначим Тк(п). При этом равенства /(х) = д(х) или сравнения вида /(х) = д(х) (mod pJ) будем понимать соответственно как равенство и сравнение, справедливые для любого X. Всюду далее считаем (если не оговорено иное) что т,п - произвольные натуральные числа, т > 1 и р - простое.

Напомним сначала некоторые определения ([25, 49]).

Определение 1.1. Наборы целых чисел а = (а1#..., ап) и /? = (Ь1#..., bn) сравнимы по модулю d (или а = р (mod d)), если щ = bi (mod d) для всех i £ 1, п.

Определение 1.1 позволяет задать на множестве целочисленных наборов отношение сравнимости по модулю d, которое будет при этом являться отношением эквивалентности.

Определение 1.2. Функция /(х) 6 Трт(п) сохраняет отношение сравнимости по модулю d | рт, если на сравнимых по модулю d наборах она принимает сравнимые значения по модулю d.

Определение 1.3. Будем считать, что класс функций сохраняет отношение сравнимости по модулю d | рт, если любая функция из заданного класса сохраняет это отношение.

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

Приведем в этой связи некоторые сведения и результаты, описанные в работах B.C. Анашина (см., например, [48, 49, 50]). В этих работах рассматривались функции, определенные на кольце целых р-адических чисел и сохраняющие отношение сравнимости.

Пусть р - произвольное простое число. Согласно основной теореме арифметики любое ненулевое число п Е 7L может быть единственным образом представлено в виде:

п = pordPn -fi,

где п ЕЖ \{0}, р \ п и ordp п е Если а,Ь ЕЖ \{0}, то определим значение:

а

ordp — = ordp а — ordp b.

Определение 1.4. р-адическим абсолютным значение числа х G Q\{0} называется величина, определяемая равенством:

\х\р=р-°г*гх. При этом полагают, что |0|р = 0.

Известно, что />-адическое абсолютное значение является нормой и задает на <Q> следующую р-адическую метрику

dv(x,y) = \х-у\р.

Пара (Q, dp) образует метрическое пространство, при этом метрика dp является неархимедовой (ультраметрикой, т.е. для нее выполняется усиленное неравенство треугольника). Отметим, что по теореме Островского ([49]), любая нетривиальная норма в поле (Q) эквивалентна (т.е. задает одну и ту же топологию) либо действительному модулю, либо /?-адическому абсолютному значению.

Метрическое пространство ((Q>, <2р) не является полным, т.е. не всякая фундаментальная последовательность (последовательность Коши) сходится по метрике dp к элементу из Q. Пополнение (Q>p данного пространства является полем и называется полемр-адических чисел. Множество

Z&) ={хЕ qp: \х\р < 1}

является подкольцом поля Ц_р и называется кольцом целых р-адических чисел. В работах [48, 49, 50] оно обозначается Жр, однако, чтобы не путать его с полем вычетов по модулю р, в настоящей работе будем использовать указанное обозначение. Например, любое целое число х G Ж является целым р-адическим числом.

Любая конгруэнция такого кольца эквивалентна отношению сравнимости по некоторому его идеалу ртЖ(ру Если элементы a,b G Ж^ сравнимы по идеалу pmZ(P), то пишут а = b (mod pm) и говорят о сравнимости по модулю рт. Известно ([49]), что верен следующий критерий сравнимости для целых р-адических чисел: а = b (mod pm) тогда и только тогда, когда \а — Ь\р < р~т. Кроме того, имеет место изоморфизм факторкольца TL^/p711!,^ = Жрт кольцу вычетов по модулю рт.

Справедливо следующее утверждение о представлении чисел кольца Z(p) (известное, например, из работы B.C. Анашина [49]).

Утверждение 1.1. ([49]) Любой элемент х Е Ж^ может быть представлен в виде суммы ряда:

00

х = ^ • , у, 00 = б Ъ = {0,..., р - 1} у=о

где сходимость ряда понимается относительно р-адической метрики йр. Пример 1.1. Для любого простого р верно разложение для -1: -1 = (р - 1) + (р - 1) • р + (р - 1) • р2 + поскольку очевидным образом

1 + (р - 1) + (р - 1) • р + (р - 1) • р2 + ••• = 0. Заметим, что в условиях утверждения 1.1: огс(р х = гтип{/ 6 х^ 0). Определение 1.5. Отображения

Уу: -» 3, уу(а) = ) £

будем называть координатными функциями в координатном множестве Ъ, а элементы а^ — у ¡(о) £ ® координатами элемента а в координатном множестве Ъ.

Координатные функции уу: Жрт Ъ, ] = 0,т — 1, аналогичным образом можно определить для элементов любого примарного кольца вычетов Жрт (см., например, работы [28, 34]). Также, аналогично утверждению 1.1, любой элемент х £ Жрт однозначно представим в виде суммы конечного ряда (р-ичного разложения целого числа):

т-1

X = ^Г р; • 1=0

где х^ ЕЪ = {0, ...,р — 1} а Жрт, называемом разложением элемента х в р-ичном координатном множестве Ъ. Если при этом ввести на Ъ операции сложения «0» и умножения «0» по правилу:

а 0 Ь = у о (а + Ь), а <8> Ъ = у0(а • Ь), а, Ь Е Ъ, то алгебра (Ъ, 0, 0) = Жрт/рЖрт = Жр будет являться полем из р элементов.

Если вектор х = (х1(..., хп) Е Щру то из утверждения 1.1 также следует,

что он представим в виде суммы ряда:

00

X = ^Г pj • Х-' , Х^ = (я^, ..., Х^3) G ®п. о

Любой вектор х = (х1, ...,хп) Е однозначно представляется в виде конечной суммы:

х = х^ + р • + - + рт-г • х^"1). Определение 1.6. Для функции /(х): и j G отображение

Yjf: Zqj) Ъ, определяемое по правилу

для всех а Е Щру будем называть ее j-ii координатной функцией, или j-м координатным отображением.

Другими словами, любая функция /(х): ll^ представима

следующим образом через свои координатные функции:

00

/(X) = • У;/(Х).

;'=О

Аналогично, любая функция /(х) G Трт(п) представима в виде конечной суммы:

m-l

/(X) = £ • 7;/(х).

j=0

При этом любую координатную функцию yjf, j = 0, т — 1, можно рассматривать как функцию Snm Ъ от nm переменных над полем Ъ, в роли которых выступают координаты ...д^'Ч В таком случае будем предполагать, что координаты переменных расположены в указанном порядке, т.е. yjf =

Yjf(x^°\...,x('m~1^. Следовательно, любая такая координатная функция может быть представлена многочленом над полем Ъ от указанных переменных ([25]).

Введенное /?-адическое абсолютное значение |-|р легко продолжается на

Щру ПОЛОЖИВ ДЛЯ X Е Щру

|х|р = max{\xi\p,i = l~n}. Используя введенные величины, сформулируем следующие определения (см. [49]).

Список литературы диссертационного исследования кандидат наук Заец, Мирослав Владимирович, 2015 год

Литература

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

2. Заец, М.В. Класс функций с вариационно-координатной полиномиальностью над кольцом Ъ2т и его обобщение / М.В. Заец, В.Г. Никонов, А.Б. Шишков //Мат. вопросы криптографии. -2013. -т.4 № 3. -С. 19-45.

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

4. Заец, М.В. Построение подстановок с использованием вариационно-координатно полиномиальных функций над примарным кольцом вычетов / М.В. Заец //Мат. вопросы криптографии - 2015. - т. 6 №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. Заец, М.В. Решение систем ВКП-уравнений методом покоординатной линеаризации над примарным кольцом вычетов / М.В. Заец //Материалы XLI Международной конференции, XI Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе 'IT+SE13'». - Вестник Московского университета имени С.Ю. Витте. - 2013. - серия 1 (приложение) - С. 155

- 157.

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

- 2013. - № 6 (Приложение). - С. 13-15.

Ю.Заец, М.В. Некоторые свойства функций с вариационно-координатной полиномиальностыо над примарным кольцом вычетов [Электронный ресурс] / М.В. Заец //Материалы XX Всероссийской Школы-коллоквиума по стохастическим методам и XIV Всероссийского Симпозиума по прикладной и промышленной математике, 2013 г. Режим доступа: http://www.tvp.ru/conferen/vsppm 14/novio051 .pdf. 11 Заец, М.В. Классификация функций над примарным кольцом вычетов в связи с методом покоординатной линеаризации / М.В. Заец//Материалы Всероссийской конференции «Сибирская научная школа-семинар с международным участием 'Компьютерная безопасность и криптография' - SIBECRYPT'14». - Прикладная дискретная математика.

- 2014. - № 7 (Приложение). - С. 16-Л9.

12.Амбросгшов, A.C. Свойства бент-функций g-значной логики над конечными полями / A.C. Амбросимов //Дискретная математика. - 1994. -т.6,№3.-С. 50-60.

13.Анашин, B.C. О группах и кольцах, обладающих транзитивными полиномами / B.C. Анашин //XVI Всесоюзная алгебраическая конференция. Тезисы. - 1981. - Часть II. - С. 4-5.

14. Белоусов, В. Д. Основы теории квазигрупп / В.Д. Белоусов. - М.: Наука, 1967.-230 с.

15. Белоусов, В Д. п-арные квазигруппы / В.Д. Белоусов. - Кишинев: Штиинца, 1972. - 225 с.

16. Былков, Д. Н. Алгоритм восстановления последовательностей, полученных линейным усложнением координатных последовательностей ЛРП над кольцом R = Zpn / Д.Н. Былков, A.A. Нечаев // Дискретная математика — 2010. — Т. 22. № 4. — С. 104-120.

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

18. Викторенков, В.Е. Орграф полиномиального преобразования над коммутативным локальным кольцом / В.Е. Викторенков //Обозрение прикл. и промышл. матем. - 2000.- т. 7, в. 2. - С. 327.

19.Викторенков, В.Е. О некоторых характеристиках цикловой структуры случайных равновероятных подстановок с помеченными циклами и их применение для исследования полиномиальных преобразований колец / В.Е. Викторенков //Обозрение прикл. и промышл. матем. - 2003. - т. 10, в.З.-С. 621.

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

21 .Глухое, М.М. Алгебра, в 2-х т. / М.М. Глухов, В.П. Елизаров, A.A. Нечаев. - М.: Гелиос-АРВ, 2003. - 749 с.

22. Глухов, М.М. Введение в теоретико-числовые методы криптографии / М.М. Глухов, И.А. Круглов, А.Б. Пичкур, A.B. Черемушкин. - М.: Лань, 2011.-330 с.

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

24. Глухое, М.М. О применениях квазигрупп в криптографии / М.М. Глухов //Прикладная дискретная математика. - 2008. - № 2 (2). - С. 28-32.

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

26. Горшков, СЛ. Применение теории NP-полных задач для оценки сложности решения систем булевых уравнений / С.П. Горшков //Обозрение прикладной и промышленной математики. - 1995. - т. № 2, вып. З.-С. 325-398.

27. Елизаров, В.П. Системы линейных уравнений над конечными кольцами / В.П. Елизаров //Труды по дискретной математике. - 2002. - т.6. - С. 3147.

28. Елизаров, В. П. Конечные кольца / В.П. Елизаров. - М.: Гелиос-АРВ, 2006.-250 с.

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

30. Елизаров, В. П. Системы линейных уравнений над коммутативным кольцом / В.П. Елизаров //Успехи мат. наук. - 1993. - № 2, С. 181-182.

31. Ермилов, Д.М. Цикловая структура полиномиального генератора над кольцом Галуа / Д.М. Ермилов, O.A. Козлитин //Матем. вопр. криптографии - 2013. - т. 4 № 1. - С. 27-57

32. Кормен, Т. Алгоритмы: построение и анализ, 2-е изд. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. -М.: Вильяме, 2005. - 1296 с.

33. Кузьмин, A.C. Бент-функции и гипербент-функции над полем из 21 элементов / A.C. Кузьмин, В.Т. Марков, A.A. Нечаев, В.А. Шишкин, А.Б. Шишков //Проблемы передачи информации. - 2008. - т. 44, вып. 1. - С. 15-37.

34.Кузьмин, A.C. Восстановление линейной рекурренты максимального периода над кольцом Галуа по ее старшей координатной последовательности / A.C. Кузьмин, A.A. Нечаев // Дискретн. матем. — 2011. —Т. 23. №2. —С. 3-31.

35.Кузьмин, A.C. Восстановление линейной рекурренты над примарным кольцом вычетов по ее усложнению / A.C. Кузьмин, Г.Б. Маршалко, A.A. Нечаев // Матем. вопросы криптографии. — 2010. — Т. 1. № 2. — С. 3156.

36. Козлитин, O.A. Полиномиальные преобразования GEO-кольца простой характеристики / O.A. Козлитин //Дискретная математика. — 2004. — т. 16. Вып. 3. — С. 105-117.

37. Ларин, М.В. Транзитивные полиномиальные преобразования колец вычетов / М.В. Ларин //Дискретная математика. - 2002. - т. №2, вып. 2. -С. 20-32.

38. Ленг, С. Алгебра / С. Ленг. — М.: Мир, 1968. - 560 с.

39. Михайлов, Д.А. Решение некоторых классов систем полиномиальных уравнений над конечными полями и кольцами / Д.А. Михайлов //Труды по дискретной математике. - 2008. - т. 11. - С. 125-146

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

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

42. Словарь криптографических терминов под ред. Погорелова Б.А, Сачкова В.Н. - М.: МЦНМО, 2006. - 92 с.

43. Сачков, В.Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. - М.: МЦНМО, 2004.

44. Солодовников, В.И. О совпадении класса бент-функций с классом функций, минимиально близких к линейным / В.И. Солодовников // Прикладная дискретная математика. - 2012. - № 3. - С. 25-33.

45. Тужилин, М.Э. Латинские квадраты и их применение в криптографии / М.Э. Тужилин //Прикладная дискретная математика. - 2012. - № 3 (17). -С. 47-52.

46. Черемушкин, А.В. Аддитивный подход к определению степени нелинейности дискретной функции / А.В. Черемушкин //ПДМ. - 2010.-№2.-С. 22-33.

47. Черемушкин, А.В. Аддитивный подход к определению степени нелинейности дискретной функции на циклической группе примарного порядка / А.В. Черемушкин //ПДМ. - 2013. - № 2. - С. 26-38.

48.Anashin, V.S. Uniformly distributed sequences of p-adic integers II / V.S. Anashin //Diskret.Mat. - 2002. - vol. 14, no. 4. - pp. 3-64 (Russian); Discrete Math. Appl. - 2002. - vol. 12, no. 6. - pp. 527-590 (English translation)

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

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

51. Bhargava, M. P-orderings and polynomial functions on arbitrary subsets of Dedekind rings / M. Bhargava //J. Reine Angew. Math. - 1997 - v. 490 - pp. 101-127.

52. Brawley, J. Functions and polynomials over Galois rings / J. Brawley, G. Mullen //Journal of Number Theory. - 1992 - v. 41(2) - p. 156-166.

53. Carlitz L. Functions and polynomials mod p" / L. Carlitz //Arithmetica. -1964.-IX-p. 67-78.

54. Hungerbiihler, N. A generalization of the Smarandache function to several variables [Электронный ресурс] / N. Hungerbiihler, E. Specker //Integers. -№ 6. - 2006. Режим доступа: http://eudml.org/doc/127575.

55. Jiang, J. A note on polynomial functions over finite commutative rings/ J. Jiang //Adv. Math. (China). - 2010 - v. 39 - pp. 555-560.

56. Jiang, J.J. On polynomial functions over finite commutative rings / J.J. Jiang, G.H. Peng, Q. Sun, Q. Zhang //Acta Math. Sin. (Engl. Ser.). - 2006 - v. 22 -pp. 1047-1050.

57. Keller, G. Counting polynomial functions (mod pn) I G. Keller, F.R. Olson //Duke Math. J. - 1968. - vol. 35 - p. 835-838.

58. Kempner, A.J. Polynomials and their residual systems / A.J. Kempner //Trans. Amer. Math. Soc. - 1921. - vol. 22. - p. 240-288.

59. Kempner, A.J. Polynomials of several variables and their residue systems / A.J. Kempner //Trans. Amer. Math. Soc. - 1925. - vol. 25. - p. 287-298.

60. Lausch, H. Algebra of polynomials / H. Lausch, W. Nobauer. - Amsterdam: North-Holl. Publ. Co. - 1973. - 356 p.

61. McDonald, B.R. Finite Rings with Identity / B.R. McDonald. - New York: Marcel Dekker. - 1974. - 155 p.

62. Mullen, G. Polynomial functions (mod m) / G. Mullen, H. Stevens //Acta Mathematica Hungarica. - 1984. - v. 44(3) - p. 237-241.

63. Nechaev, A.A. Finite rings with applications / A.A. Nechaev //Handbook of Algebra. - 2008. - Vol. 5. - p. 213-320.

64. Nobauer, W. Zur Theorie der Polynomtransformationen und Permutationspolynome / W. Nobauer //Math. Ann. - 1964. - vol. 157 - p.332-342.

65. Rivest, R. Permutation polynomials modulo 2W / R. Rivest //Finite Fields and Their Applications. - 2001. - vol. 7 - p. 287-292.

66. Rosenberg, I. G. Polynomial functions over finite rings / I.G. Rosenberg //Glas. Mat. - 1975 - v. 10 - pp. 25-33.

\Q(f

67. Samardziska, S. Polynomial я-агу quasigroups / S. Samardziska, S. Markovski //Math. Maced. - 2007. - Vol. 5 - p. 77-81.

68. Singh, R. P. Permutation polynomials modulo pn [Электронный ресурс] / R.P. Singh, S. Maity. - Режим доступа: eprint.iacr.org/2009/

69. Singmaster, D. On polynomial functions (mod m) / D. Singmaster //J. Number Theory. - 1974. - vol. 6. - p. 345-352.

70. Smarandache, F. A Function in the Number Theory / F. Smarandache //Analele Univ. Timisoara. - 1974. - Fascicle 1, Vol. XVIII. - p. 79-88.

71. Wiesenbauer, J. On polynomial functions over residue class rings of Z. Proc. Klagenfiirt Conf. Contrib / J. Wiesenbauer //Gen. Algebra - 1983. - № 2. -p. 395-398.

72. Zhang, Q. Polynomial functions and permutation polynomials over some finite commutative rings / Q. Zhang //J. Number Theory. - 2004. - vol. 105. -p. 192-202.