Нормальные базисы в конечных полях и их приложения тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Геут, Кристина Леонидовна

• Геут, Кристина Леонидовна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Геут, Кристина Леонидовна

ОГЛАВЛЕНИЕ

Введение

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

конечных полях характеристики два

§1.1. След и вектор следа

§ 1.2. Пример расчета вектора следа

§ 1.3. Полуслед и расширение конечных полей

§ 1.4. Нормальные базисы в конечных полях и решение квадратных

уравнений

§ 1.5. Решение уравнений на эллиптических кривых

Глава 2. Алгоритмы поликвадратичного расширения бинарных полей

§ 2.1. Симметричное квадратичное расширение

§ 2.2. Общий вид многочленов одного цикла

§ 2.3. Операция у4

§ 2.4. Переход к 3 и 5 степеням корня многочлена

§ 2.5. Неприводимые многочлены степени п = р*д. %

Глава 3. Задача построения неприводимых многочленов

§ 3.1. Многочлены вида Чебышёва-Диксона

§ 3.2. Неприводимые симметричные многочлены

§ 3.3. Построение неприводимых многочленов простого порядка

§ 3.4. Построение рекурсий первого порядка

Заключение

Литература

Приложение А

Приложение Б

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

Введение

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

Актуальность темы исследования. Теория конечных полей была построена в работах Ферма, Эйлера, Лежандра, Гаусса, Галуа, Диксона и других выдающих ученых [11, 12], и до последней четверти 20-го века развивалась как область чистой математики, но в связи с потребностями кодирования и криптографии в настоящее время активно развиваются прикладные аспекты теории. Вопросам эффективной реализации арифметики в конечных полях посвящено много работ и специальных книг, отечественных и зарубежных авторов [3, 5-7, 12-13, 15, 20, 22-23, 34, 38-43].

Неприводимые многочлены, корни которых образуют базис для представления элементов конечных полей, аналогичны простым числам [13, 4647]. Они нашли свое применение в различных областях математики, информационной техники и защите информации. Использование свойств неприводимых многочленов [21, 25-26, 44-46] позволяет максимизировать эффективность компьютерной реализации арифметики в конечных полях, что имеет особое значение для криптографии и теории кодирования. Таковы, например, реализация электронной цифровой подписи на эллиптических кривых [9-10, 20, 34-35, 38, 40-43]; коды Рида-Маллера, Рида-Соломона и другие [2, 6, 18, 24]; программирование дискретных устройств [19, 23, 29-30, 36, 39]; современные стандарты шифрования [28]. Для нахождения таких многочленов нет определенного (детерминированного) алгоритма, так что их построение производится подбором, т.е. вероятностными алгоритмами, что требует временных затрат и объемных вычислений. Коэффициенты многочленов, как

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

При организации транспортного производства используется более двух десятков видов связи. Все шире внедряются беспроводные технологии, такие как GSM-R, TETRA, CDMA и др. При этом важно отметить, что именно беспроводные технологии наиболее уязвимы с точки зрения информационной безопасности. Перехват информации в беспроводных системах не требует физического контакта с линией связи, что существенно упрощает задачу несанкционированного доступа к информации [27, 29].

В устройствах связи ОАО «РЖД» предполагается применение системы GSM-R, как основной системы технологической радиосвязи на участках высокоскоростного и скоростного движения, а также на основных транспортных магистралях. В системах GSM, GSM-R в качестве алгоритмов шифрования используются шифры семейства А5 [39]. Стандарт шифрования А5/1, используемый в GSM-R, можно считать примером кодирующего аппарата с обратной связью и без памяти.

Одним из таких кодирующих аппаратов является регистр сдвига с линейной связью (PCJIOC, Linear feedback shift register, LFSR). Он состоит из двух частей: собственно регистра сдвига и функции обратной связи. Регистр состоит из битов, его длина - количество этих бит. Новый крайний слева бит определяется функцией остальных битов. На выходе регистра оказывается один, обычно младший, значащий бит. Период регистра сдвига - длина выходной последовательности до начала её повторения.

Для оптимизации работы конечного автомата в качестве характеристического многочлена используют «малочлены» (идеальный случай -трехчлены), и лучше - примитивные (т.е. максимального порядка). С точки зрения кибернетики минимизация обратных связей существенно повышает работу этих дискретных устройств.

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

Тематика расширения бинарных полей тесно связана с изменением архитектуры в вычислительной технике: переход от битовой архитектуры к байтовой, от 32-х разрядной к 64-х, а в последствии к 1024-х байтовой. Распараллеливание операций, увеличение функционала видеокарт позволяет оптимизировать работу и ускорить работу процессора. Поэтому гибкая аппаратная компоновка видеокарт, благодаря рациональной организации отводов регистров сдвига, может позволить реализовать широкий спектр возможностей, в том числе и связанных с реализацией и анализом шифров.

К примеру, для работы декодера иногда создается ситуация, когда необходимо знать корни многочленаДг) над С¥(рт), лежащие в этом поле. Общим методом решения этой задачи является процедура Ченя, предложенная им в 1964 году [23]. Для больших значений числа рт она требует значительного числа операций. В связи с этим актуальными задачами остаются следующие: построение многочленов простой степени р\ алгоритм построения неприводимых многочленов степени п = где # и р - простые числа; построение многочленов р", где п = 2, 3, 4, ..., построение гарантированно неприводимого многочлена данной большой степени; анализ примитивности многочленов больших степеней; построение многочленов простого порядка р.

Интересное применение в кодировании имеют симметричные1 многочлены

(теорема Мирончикова [25]), их максимально возможный порядок р = 22* +1, где степень многочлена N = 2к+х. Это сближает их с тематикой простых чисел Ферма,

которые рассчитываются по формуле р = 22 +1 [16, 33]. В настоящее время найдены простые числа для к = 0, 1, 2, 3, 4, при больших к простых чисел пока не найдено. Интерес к этим числам возрос после выхода книги К.Ф. Гаусса

1 Симметричные (самовозвратные) многочлены - многочлены, у которых коэффициенты симметричны относительно центрального бита.

«Арифметические исследования», где описано построения правильных п-угольников для нечетных п. Количество вершин такого многоугольника должно быть простым числом Ферма либо произведение нескольких таких различных чисел [16]. В современной трактовке эти числа интересны как пример больших простых чисел, имеющих мало единичных битов в своей двоичной записи (т.н. числа Солинаса). Число Ферма имеет всего два таких битов - старший и младший - минимально возможное количество.

Порядок примитивных многочленов степени п, равный р = 2" - 1, сближает их с простыми числами Мерсенна. В настоящее время найдено 48 таких чисел и поиск их продолжается. Построение алгоритма эквивалентного поиска примитивных многочленов степени п могло бы упростить или хотя бы систематизировать процедуру поиска. В защите информации числа Мерсенна применяются в генераторе псевдослучайных чисел «вихрь Мерсенна».

В книге [9] рассматриваются многочлены Чебышёва-Диксона, играющие фундаментальную роль в теории и практике численных методов и нашедшие широкое применение в различных областях техники. Аналогичная рекурсия возможна для построения последовательности неприводимых многочленов как задачи, эквивалентной проверке простоты чисел [56, 60-61]. За основу взяты исследования в работах [4, 17, 32]. Переход от квадратичной зависимости к линейной - актуальная задача, упрощающая программную реализацию [33,37].

Появление рекуррентных соотношений можно проиллюстрировать коммутирующими функциями - аналогом многочленов Чебышёва-Диксона. Основным источником таких функций, например, являются эллиптические кривые. Так, в работе [33] поставлена и решена задача построения нелинейного рекуррентного соотношения первого порядка для чисел Фибоначчи [15], а также поставлена задача построения нелинейного рекуррентного соотношения первого порядка для общего линейного рекуррентного соотношения с постоянными коэффициентами.

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

значит, и сложность построения логических схем [9]. Потенциально возможны разные представления, но практически используются в основном два, а именно представления в стандартных и нормальных базисах, а также производные от них. Наиболее широко используемым является представление в стандартном базисе -элементы поля в нем представляются многочленами, арифметические операции с которыми выполняются по модулю неприводимого многочлена, определяющего этот базис [9].

В работах [50, 70-71, 73] рассмотрено построение нормальных базисов посредством расширения полей и применения их для решения квадратных уравнений в конечных полях, в том числе и уравнений эллиптических кривых [9, 20, 38, 40-43]. Криптосистемы, построенные на эллиптических кривых, имеют преимущество в криптостойскости перед известными алгоритмами, поэтому решение уравнений кривых и представление этих решений в элементах конечных полей - актуальная задача.

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

Работы [49, 51, 52-58, 72] посвящены алгоритмам поликвадратичного расширения конечных полей и их практической значимости.

Объект исследования - элементы конечных полей характеристики два и три (неприводимые многочлены, базисы) и их свойства.

Предмет исследования - алгоритмы расширения конечных полей характеристики два и характеристики три посредством неприводимых многочленов.

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

Поставленная цель достигнута путем решения следующих задач: - построение нормальных базисов расширений конечных полей

характеристики два и три;

- описание детерминированных алгоритмов построения неприводимых многочленов над конечными полями;

- доказательство эквивалентности построения неприводимых многочленов над конечными полями и поиска простых чисел;

- построение нелинейной рекурсии первого порядка для произвольного линейного рекуррентного соотношения второго порядка с постоянными коэффициентами.

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

Научная новизна. Основные результаты, полученные в работе, являются новыми.

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

Таким образом, совокупность полученных в диссертации результатов можно квалифицировать как новый вклад в развитие и обоснование математических принципов, направленных на развитие теории конечных полей. Основные результаты, выносимые на защиту, состоят в следующем: 1) Доказана теорема о нормальных базисах при симметричном квадратичном расширении конечных полей; сгенерированы все неприводимые многочлены степени 2" над ОР(2), построено полное бинарное дерево таких многочленов и изучены их свойства;

2) Предложены детерминированные алгоритмы расширения конечных полей и построения неприводимых многочленов данного порядка; рекуррентно построены бесконечные серии неприводимых многочленов над СР(2) и СР(3);

3) Доказаны утверждения об эквивалентности задач построения неприводимых многочленов над конечными полями и проверки простоты чисел; построено нелинейное рекуррентное соотношение первого порядка, эквивалентное общему линейному рекуррентному соотношению второго порядка с постоянными коэффициентами.

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

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

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

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

Международной студенческой конференции IT Security For New Generation (Москва, Лаборатория Касперского, 2008);

Международной научно-практической конференции «Связь-Пром» (Екатеринбург, УГТУ-УПИ, 2008, 2009);

Международной научно-практической конференции «Транспорт XXI века: Исследования. Инновации. Инфраструктура» (Екатеринбург, УрГУПС, 2011);

Международной конференции «Герценовские чтения» (Санкт-Петербург, РГПУ им. Герцена, 2012);

Всероссийской молодежной школе-конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, ИММ УрО РАН, 2008, 2010, 2012, 2013,2015);

Всероссийской конференции «Безопасность информационного пространства» (Тюмень, ТГУ, 2012; Екатеринбург, УРФУ, 2013);

Всероссийской конференции Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" -ЗЮЕСЮТТ (Иркутск, ИДСТУ, 2012, Екатеринбург, 2014);

Всероссийской междисциплинарной молодежной научной конференции с международным участием «Информационная школа молодого ученого» (Екатеринбург, ЦНБ УрО РАН, 2013, 2014);

Всероссийской конференции «Транспорт Урала» (Екатеринбург, УрГУПС, 2013);

Всероссийской конференции, посвященной памяти академика А.Ф. Сидорова «Актуальные проблемы прикладной математики и механики» (Абрау-Дюрсо, 2014)

а также на региональных научно-практических конференциях (Екатеринбург, УрГУПС, 2008, 2011, 2013).

Всего сделаны доклады на 21-ой конференции различного уровня.

Публикации. Основные результаты диссертации опубликованы в работах [49-73]. Работы [49-51] опубликованы в изданиях, входящих в перечень утвержденных ВАК РФ. Результаты опубликованы в 34 работах, в диссертацию вошли 25 работ.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из 73 наименований. Объем диссертации составляет 111 страниц, 20 рисунков, 25 таблиц, 2 приложения.

Содержание работы. Диссертационная работа содержит введение, три главы, заключение, список литературы, список публикаций автора, два приложения. В работе принята:

1) двойная нумерация параграфов, первая цифра указывает на номер главы, вторая — на номер параграфа в данной главе. Например, параграф 1.5 — пятый параграф первой главы;

2) двойная нумерация формул, лемм, утверждений и теорем: первая цифра указывает на номер главы, в которой содержится объект, вторая - на номер объекта в данной главе. Например, формула 1.5 - пятая из пронумерованных формул первой главы;

Перейдем к описанию содержания диссертации по главам.

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

В первой главе излагается необходимый теоретический материал для постановки решаемых в работе задач. Рассмотрено понятия следа, его свойства в конечных полях и вектора следа, который упрощает поиск следа элемента поля. Доказаны утверждения, которые дают более четкое представление о быстром и упрощенном нахождении вектора следа неприводимого многочлена. Результаты исследований опубликованы в работах [63-69].

В произвольном поле ОБ(р) формула вычисления следа элемента имеет вид:

д=рп=> = 2 + ^ + 2/>2 + _ + (о ])

и может принимать значения {0, 1, ..., р- 1}.

Если поле ОР(<7т) является расширением поля ОР(#), то вычисляется след элемента поля

Тг.С¥(дт)^0¥(д),д=р".

Trjz) =z + zq + z"2 + ... + zq'

(0.2)

Существует более простой способ вычисления следа. Он заключается в том, что изначально вычисляется, так называемый, вектор следа для данного многочлена. Значение функции следа для элемента а поля ОР(2") равно сумме (по модулю 2) элементов вектора, получаемого как поразрядное произведение (конъюнкция) элементов вектора а и вектора следа.

Утверждение 0.1. Вектор следа при нечетном п будет иметь вид 1000...0, если и только если все показатели степеней членов неприводимого многочлена нечетные, за исключением нулевой.

Утверждение 0.2. Вектор следа при четной степени п будет иметь вид ООО...01, если и только если все показатели степеней членов неприводимого многочлена четные, за исключением первой.

Утверждение 0.3. Для многочленов четной степени п единица вектора следа появится на позициях г = п — к, где к —любая нечетная степень.

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

В конечных полях ОР(2") при нечетном п решение квадратного уравнения х + х = г, где г — данный элемент этого поля, х - искомый корень при Тг(г) = 0 дает формула полуследа:

В книге [10] вычисление решения квадратного уравнения в полях ОР(2"), где п четное, сводится к системе линейных уравнений, вычисление которой довольно громоздко и требует временных затрат. Трудность задачи поиска формулы решения для четной степени иллюстрирует следующее

Базис - способ представления элементов конечных полей. Решение уравнения может быть представлено в стандартном базисе, т.е. базисе вида {1, А.,

Sr(z) = х - z + z4 + z16 + ... + z2""'.

(0.3)

Утверждение 0.5. При четном п не существует многочлена вида 2 ~

2

дающего решение квадратного уравнения z + z = а.

X2, X3, ..., Х"~1}, где X - корень неприводимого многочлена, но в данной работе

использовано и разложение в нормальном базисе, т.е. базисе вида {[3, (З2, (З4, (З8, ..., 1

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

требуется, чтобы 7У(Р) = 1, поэтому для построения базиса {р, р2, р4, р8, ..., р2'7 ' } использована операция симметричного квадратичного расширения (СКР), формула которого имеет вид:

а = (3 + (З-1, (0.4)

где а является элементом поля Р, р является элементом поля К, поле К является расширением поля Р, или, в терминах многочленов,

F=Д/,F(0 = Or('+

где /- многочлен степени т расширяемого поля Р, F - многочлен для расширенного поля К.

Теорема 0.1. Если множество {а, а , ..., а" } является нормальным базисом в поле ОР(2"), след а-1 равен единице и а = р + р-1, то Р С ОР(22"), и

2 2п~^ 2п

множество {Р, Р , ..., Р } также будет нормальным базисом в поле вР(2 ").

После последовательного применения операции СКР получены неприводимые многочлены степени п = 2\ образующие нормальные базисы: В{(х)=х + 1; 02(х) = х2+ х + 1; £>з(х) = х4 + х3 + х2 + л: + 1;

ИаЦх) = х8 + х1 + х6 + / + х2 + х + 1;

£>5(л;) =х16 + х15 +х14 + х13 +х12 + + х8 + х5 + х4 + х3 + х2 + х + 1;

П ( \ — 32 , 31, 30 , 28 , 27 , 26 , 24 , 22 , 17 , 16 , 15 , 10 , 8 , 6 , 06(х) = X + X +Х + X +Х + X + X + X + X +Х +Х + X +Х+Х +

+ х5+х4 + х2+х+ 1.

£>7(х) = х64 + х63 + х62 + х61 + х60 + х56 + х54 + х52 + х51 + х48 + х47 + х44 + х43 + + х41 + х39 + X35 + х34 + х33 + X32 + X31 + х30 + X29 + X25 + х23 + X21 + X20 + X17 + X16 + X13 + + х12 + х10 + х8 + х4 + х3+х2 + х+ 1.

Примеры решения квадратных уравнений в нормальных базисах описаны в работах [50, 55, 70-71, 73].

Вторая глава посвящена алгоритмам расширений бинарных полей. Решение уравнения х + х = г, где 2 - корень неприводимого многочлена /, т.е. Дг) = 0 степени т дает следующие наблюдения: В параграфе 2.1 описана функция

х„ = К{х) = А(Л(Л.. .(А(ВД)))), (0.5)

где /г(х) = (х + х-1) и число итераций к(х) равно п. Эта функция есть аналог функции Жуковского нашедшей применение в аэродинамике, она связана с операцией СКР через операцию А на множестве многочленов. А именно, если /-многочлен данной степени т, то многочлен F = Д / степени 2т вычисляется по формуле Р(Х) = Xй ДХ+Х~1). Выведена формула для вычисления цепочки самовозвратных неприводимых многочленов степени 2": Утверждение 0.6.

ш2

,2, (о.б)

где £>„(х) = ЛД^х) = х2"' (Д,_,(х + х-1)).

Неприводимые многочлены, полученные посредством СКР можно упорядочить в зависимости от их значений следа и антиследа и представить эту зависимость в виде орграфов. Здесь если Тг(х) - след элемента х, то его антислед есть 7У(х-1).

Рисунок 0.1. Орграфы неприводимых многочленов шестой степени

На основании анализа таких орграфов сформулированы и обоснованы свойства операции СКР:

1. Коэффициент при элементе х определяет приводимость многочлена, полученного из данного с помощью операции СКР (если у многочлена /(х) коэффициент при х равен 1, то Д/(х) неприводимый многочлен, если равен 0 -ЛДх) приводимый).

2. Взаимосвязь значений следа и антиследа многочлена определяет вид орграфа, который порождает данный многочлен.

После одноразового применения операции СКР результат при зацикливании А/ делится на /, это значит что корень * многочлена /, является и корнем А/, поэтому операция СКР просто циклически сдвигает корни многочлена /, т.е. корень х этого многочлена преобразуется в корень х^, где 2", п= 1, 2, 3, ...

Утверждение 0.7. Представление операции СКР в виде х, = хм, где 2", п= 1, 2, 3, ..., дает уравнение общего вида многочленов квадратичного расширения вида/{(х) или g(x) ~/р(х).. /д(х), где длина орграфов /,(х) равна п.

1 + х2 + 1 = 0. (0.7)

х**3 + л™ + X4 + X"2 + 1 = 0, (0.8)

n+7 , n+\ 18,6,4, 2,i л /г\ r\\

x +x + x+x+x+x+l=0. (0.9)

Последовательное вычисление многочленов квадратичного расширения в зависимости от значения п позволяет найти все многочлены, длина цикла для которых после применения операции СКР будет равна п.

Результаты исследований симметричного квадратичного расширения полей более подробно рассмотрены в работах [51, 72].

В параграфе 2.3 решение уравнения х + х — z, где z - корень неприводимого многочлена/, т.е. f(z) = 0 степени m дает следующее:

Утверждение 0.8. Если х — корень неприводимого многочлена F{x) - 0 лежит в поле GF(2m), то многочлен, полученный из многочлена f посредством операции А:

F(t)=At2 + t) (0.10)

приводим: F{t) = p(t)q(t), deg р = deg q = m, где элемент x - корень одного из двух неприводимых многочленов той же степени т, связанных соотношением сдвига: p(t + 1) = q(t); q(t + 1) =p(t) и Tr{f) = 0.

Утверждение 0.9. Если x - корень неприводимого многочлена F(x) = 0, полученного из f посредством операции А лежит в расширенном поле GF(22"') и Tr(f) = 1, то многочлен F степени deg F — 2m неприводим и периодичен с периодом, равным единице, т.е. F(t + 1) = F(t).

Поэтапное применение операции А позволяет сгенерировать все неприводимые многочлены степени 2", которые можно представить в виде полного бинарного дерева.

я2+ X + 1 X + 1

I

Рисунок 0.2. Расширение полей ОР(2") посредством операции А

Посредством поликвадратичного расширения можно не только вычислять характеристический многочлен элемента из расширенного поля, но и из расширяемого, т.е. движение по дереву возможно как вверх, так и вниз. Для того чтобы "опуститься" по дереву вниз, необходимо применить операцию А, а чтобы "подняться" по дереву вверх - выполнить обратную операцию Л = А~\

Операция А позволяет сгенерировать все неприводимые многочлены степени 2".

Утверждение 0.10. Если /г(х) - г, ёе§/= п, неприводим, Дг) = 0, g = 2п, g(x) = 0, неприводим то Тг{г) — 7>(х), где Н{г) - (г + г-1) равен следу элемента г из поля ОР(22") в поле С¥(2п).

Утверждение 0.11. Если в поле 0Р(2Ш), т > 1, г — корень симметричного

многочлена /, то однозначно определен периодический многочлен g, гдеу = —— -

2 + 1

его корень. И наоборот, если g - периодический, то / - симметричный, где У

Изучение свойств расширения конечных полей посредством операции А изложено в работах [52-54, 57-58].

В параграфе 2.3. изложен третий рассматриваемый способ генерации неприводимых многочленов - переход к 3 и 5 степеням.

Взяв в поле ОР(25) при 5 = 0 неприводимый многочлен /0(х) = х + 1 степени п = 3° = 1, можно построить неприводимый многочлен третьей степени/\(х) = х3 + + х + 1 при 5=1, решая уравнение X]3 + + 1, где х\ - корень многочлена /0. Далее, решая уравнение х23 + Хг = л:ь получим корень х2 многочлена /2(х) =

3 3 3 3 9 7 5

= /\(х +х) = (х + х) + (х +х)+1=х + х + х + х + I, который также будет неприводимым, согласно таблицам [10, 14].

Положим Т0(х) = 0, Т\(х) = х, Т2(х) - х , 7з(х) = х + х, и т.д. - многочлены Чебышёва-Диксона над ОР(2).

Утверждение 0.12. Для любого п = З5, 5 = 1, 2, 3, ..., справедливо тождество Г„(х) = х[/о(х)]2[/1(х)]2. ■ • [/¡1 (х:)]2.

Теорема 0.2. Многочлен/¡(х) неприводим для любого г = 0, 1,2,... Переход к 3 и 5 степеням сближает генерацию неприводимых многочленов с тематикой построения эллиптических суперсингулярных кривых.

2 3

Нахождение точек кривой Е\ с уравнением у + у = х аналогично переходу из поля ОР(2") в поле ОР(23"), а для кривой Е2 с уравнением у2 + у = х3 + х - из ОР(2") в ОР(25").

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

Список литературы диссертационного исследования кандидат наук Геут, Кристина Леонидовна, 2015 год

Литература

[1] Адрианов Н.М. Классификация примитивных групп вращений рёбер плоских деревьев / Н.М. Андрианов // Фундаментальная и прикладная математика. 1997. Т.З. вып. 4. С. 1069-1083.

[2] Асосков A.B. Поточные шифры / A.B. Асосков, М.А. Иванов, A.A. Мирский, A.B. Рузин, A.B. Сланин, А.Н. Тютвин. М: КУДИЦ-ОБРАЗ, 2003. 336 с.

[3] Айерлэнд К. Классическое введение в современную теорию чисел : пер. с англ. / К. Айерлэнд, М. Роузен. М.: Мир, 1987. 416 с.

[4] Баданова О.М. Вычисление коэффициентов неприводимых делителей суммы геометрической прогрессии / О.М. Баданова, М.А. Ициксон, С.С. Титов, A.B. Усольцев // Проблемы теоретической и прикладной математики : труды 34-й региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 3-4.

[5] Баранский В.А. Введение в общую алгебру и ее приложения. / В.А. Баранский. Екатеринбург, 1998 г. 169 с.

[6] Бейхут Р. Теория и практика кодов, контролирующих ошибки : пер с англ. / Р. Бейхут. М.: Мир, 1986. 576 с.

[7] Берлекэмп Э. Алгебраическая теория кодирования : пер. с англ. / Э. Берлекэмп ; под ред. С.Д.Бермана. М.: Мир, 1971. 480 с.

[8] Богацкая И.М. Предельные соотношения между многочленами Чебышёва и Хана / И.М. Богацкая, A.A. Минько // Кибернетика и системный анализ. 1994. №1. С. 45-50.

[9] Болотов A.A. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы / A.A. Болотов, С.Б. Гашков, А.Б. Фролов. М.: КомКнига, 2012. 328 с.

[10] Болотов A.A. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых / A.A. Болотов, С.Б. Гашков, А.Б. Фролов. М.: КомКнига. 2006. 280 с.

[11] Бухштаб A.A. Теория чисел. / A.A. Бухштаб. М.: Просвещение, 1966. 384 с.

[12] Вейль А. Основы теории чисел / А.Вейль. М.: Мир. 1972. 408 с.

[13] Виноградов И.М. Основы теории чисел / И.М. Виноградов. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика». 2003. 176 с.

[14] Гараков Г.А. Таблицы неприводимых полиномов над GF(p) (р < 11) / Г.А. Гараков // Математические вопросы кибернетики и вычислительной техники. Труды ВЦ АН Арм.ССР и Ереван.гос.унив. №6. 1970. С. 112-142.

[15] Гельфонд А.О. Исчисление конечных разностей / А.О. Гельфонд. М.: Наука, 1967. 376 с.

[16] Гиндикин С.Г. Дебют Гаусса / С.Г. Гиндикин // Квант, No 1. 1972. С. 2-11.

[17] Демкина O.E. Рекуррентное вычисление неприводимых многочленов в задачах двоичного кодирования / O.E. Демкина, С.С. Титов, A.B. Торгашова // Молодые ученые - транспорту: Труды IV научно-технической конференции. Екатеринбург: УрГУПС, 2003. С. 391-404.

[18] Зубов А.Ю. Совершенные шифры. / А.Ю. Зубов. М.: Гелиос АРВ, 2003. 160 с.

[19] Иванов М.А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей / М.А. Иванов, И.В. Чугунков. М. :КУДИЗ-ОБРАЗ, 2003. 240 с.

[20] Кнэпп Э. Эллиптические кривые : пер. с англ. Ф.Ю. Попеленского. / Э. Кнэпп. М.: изд-во «Факториал-Пресс». 2004. 488 с.

[21] Кузьмин E.H. О неприводимых многочленах над конечным полем / E.H. Кузьмин // Алгебра и логика. 1994. Т. 33, №4. С. 387-414.

[22] Ленг С. Алгебра / С. Ленг // М.: Мир. 1968. 360 с.

[23] Лидл Р. Конечные поля. В 2-х т. Т. 1. : пер. с англ. / Р. Лидл, Г. Нидеррайтер. М.: Мир, 1988.430 с.

[24] Логачев O.A. Булевы функции в теории кодирования и криптологии / O.A. Логачев, А.А Сальников., В.В. Ященко. М.:МЦНМО, 2004. 470 с.

[25] Мирончиков Е.Т. Класс кодов, исправляющих двойные ошибка, и их реализация / Е.Т. Мирончиков // Авт., телем. и прибор., № 3. 1963. С. 251-255.

[26] Мэсси Дж. JI. Веса многочленов и кодовые конструкции / Дж. JI. Мэсси, Д.Дж. Кастелло, И. Юстесен // Кибернетический сборник (новая серия), М.: Мир. 1974. вып. 11. С. 24-47.

[27] Паршин A.B. Классический протокол пакетной коммутации: монография / A.B. Паршин. Екатеринбург: изд-во УрГУПС, 2007. 242 с.

[28] Предварительный государственный стандарт республики Беларусь «Информационные технологии и безопасность алгоритмы разделения секрета» Госстандарт, Минск СТБ П 34.101.44-2011. 19 с.

[29] Сапожников В.В. Теоретические основы железнодорожной автоматики и телемеханики: учебник для вузов ж.-д. транспорта / В.В. Сапожников, Ю.А Кравцов, Вл.В. Сапожников ; под. ред. В.В. Сапожникова. М.: ГОУ «Учебно-методический центр по образованию на железнодорожном транспорте», 2008. 394 с.

[30] Сапожников Вл.В. Методы построения функциональных элементов самопроверяемых самодвойственных структур / Вл.В. Сапожников, В.В. Сапожников, Р.Ш. Валиев // Транспорт Урала. 2006. № 2(9). С. 2-8.

[31] Сергеев И.С. О реализации некоторых операций в конечных полях схемами логарифмической глубины : автореф. дис. ... канд. физ.-мат. наук : 01.01.09 / [Моск. гос. ун-т им. М.В. Ломоносова] Сергеев Игорь Сергеевич ; Москва, 2007. 96 с.

[32] Титов С.С. Генерация неприводимых многочленов, связанных степенной зависимостью корней / С.С. Титов, A.B. Торгашова // Доклады Томского государственного университета систем управления и радиоэлектроники. №2 (22), часть 1. 2010. С. 310-318.

[33] Ушаков В.Н. Египетские треугольники и числа Фибоначчи / В.Н. Ушаков // Империя математики. №1. 2001. С. 21-60.

[34] Харин Ю.С. Математические и компьютерные основы криптологии. / Ю.С. Харин, В.И. Берник, Г.В. Матвеев, С.В. Агиевич. Минск: Новое знание. 2003. 382 с.

[35] Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С. / Б. Шнайер. М.: Триумф. 2002. 318 с.

[36] Яковлев В.В. Информационная безопасность и защита информации в корпоративных сетях железнодорожного транспорта: учебник для вузов ж.-д. транспорта / В.В. Яковлев, А.А. Корниенко ; под ред. В.В.Яковлева. М.: УМК МПС России, 2002. 328 с.

[37] Янтаров И. Коммутирующие многочлены. / И. Янтаров // Квант, №4. 1979. С. 19-23.

[38] Biryukov A. Real Time Cryptanalysis of A5/1 on a PC./ A. Biryukov, A.Shamir, A.Wagner // Fast Software Encryption Workshop. April 10-12. 2000. Pp. 1-18.

[39] Kazeka A. Security model evaluation of 3G Wireless Networks. / A. Kazeka // Colorado State University. 15 pp.

[40] Koblitz N. Algebraic aspects of Cryptography. / N. Koblitz // Springer. 2004. 109 pp.

[41] Koblitz N. Hyperelliptic cryptosystems / N. Koblitz // Journal of cryptology. № 1. 1989. Pp. 139-150.

[42] Menezes A.J. Elliptic Curve Cryptosystems and their implementation / A.J. Menezes, S. Vanstone // Journal of Cryptology. №6. 1993. P. 209-224.

[43] Rosing M. Implementing Elliptic Curve Cryptography. / M. Rosing. Greenwich : Manning Publication. 1998. 338 p.

[44] Zirler N. On primitive trinomials (mod 2) / N. Zirler, J. Brillhart // Inform. Contr. 1968. 13. Pp.541-554.

[45] Zirler N. On x" + x + 1 over GF(2) / N. Zirler // Inform. Contr. 1970. 16. Pp.502505.

[46] Zirler N. On primitive trinomials / N. Zirler, J. Brillhart // Inform. Contr. 1969. 14. Pp.566-569.

[47] Zivkovic M. A table of primitive binary polynomials / M. Zivkovic // Math. Comp. 1994 . 62. Pp. 385-386.

[48] Zivkovic M. A table of primitive binary polynomials. II / M. Zivkovic // Math. Comp. 1994.63. Pp 301-306.

Список публикаций по теме диссертации Публикации в изданиях, рекомендованных ВАК

[49] Геут К.Л. О генерации неприводимых многочленов простых порядков для построения дискретных устройств СЖАТиС / К.Л. Геут, С.С. Титов // Транспорт Урала : науч.-тех. журнал. Екатеринбург: УрГУПС, 2014. № 1 (40). С. 61-64.

[50] Глуско К.Л. Арифметический алгоритм решения квадратных уравнений в конечных полях характеристики два / К.Л. Глуско, С.С. Титов // Доклады Томского государственного университета систем управления и радиоэлектроники. Томск: ТУСУР. 2012. №1(25), часть 2. С. 148-152.

[51] Глуско К.Л. О квадратичных расширениях бинарных полей / К.Л. Глуско, С.С. Титов // Известия Российского государственного педагогического университета им. А.И. Герцена. = Izvestia: Herzen University Jornal of Humanities & Sciences. № 154: Рецензируемый научный журнал. СПб., 2013. С. 7-16.

Другие публикации

[52] Построение бинарного дерева посредством поликвадратичного расширения / Е.А. Букина, О.О. Ванцева, М.Ю. Филиппов, Кр.Л. Геут //

Математическое моделирование системных взаимосвязей в прикладных исследованиях : сб. науч. тр. Екатеринбург : Изд-во УрГУПС, 2013. Вып. 13(196). С. 73-77.

[53] Автоматизация математического алгоритма расширения бинарных полей / Е.А. Букина, О.О. Ванцева, М.Ю. Филиппов, Кр.Л. Геут // Безопасность информационного пространства : материалы XII Всерос. науч.-практ. конф. Екатеринбург: Изд-во Урал, ун-та, 2014. С. 214-219.

[54] Геут (Глуско) Кр.Л. О свойствах поликвадратичных расширений бинарных полей / Кр.Л. Геут (Глуско), С.С. Титов // Проблемы теоретической и прикладной математики: Труды 44-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН, 2013. С. 17-19.

[55] Геут (Глуско) Кр.Л. Модель арифметики конечных полей и ее реализация для решения квадратных уравнений / Кр.Л. Геут (Глуско), С.С. Титов // Математические методы и модели в теоретических и прикладных исследованиях : сборник научных статей. Екатеринбург : Издательство УрГУПС, 2012. С. 57-65.

[56] Геут К.Л. О генерации и применении неприводимых многочленов / К.Л. Геут, С.С. Титов // III междисциплинарная молодежная научная конференция УрО РАН "Информационная школа молодого ученого" : сб. научных трудов ЦНБ УрО РАН. Екатеринбург, 2013. С. 293-298.

[57] Геут Кр.Л. О поликвадратичном расширении бинарных полей / Кр.Л. Геут, С.С. Титов // Прикладная дискретная математика (Приложение). Томск: ТПУ. 2013. №6. С. 12-13.

[58] Геут Кр.Л. О генерации неприводимых многочленов / Кр.Л. Геут, С.С. Титов // Математическое моделирование системных взаимосвязей в прикладных исследованиях : сб. науч. тр. Екатеринбург : Изд-во УрГУПС,

2013. Вып. 13(196). С. 12-18.

[59] Геут Кр.Л. Построение неприводимых многочленов простого порядка / Кр.Л. Геут, С.С. Титов // Безопасность информационного пространства : материалы XII Всерос. науч.-практ. конф. Екатеринбург: Изд-во Урал, ун-та,

2014. С. 219-225.

[60] Геут Kp.JI. Задача, эквивалентная проверке простоты чисел Ферма / Кр.Л. Геут, С.С. Титов // Прикладная дискретная математика (Приложение). Томск: ТПУ. 2014. №7. С. 13-14.

[61] Геут Кр.Л. О простых числах и рекуррентных соотношениях / Кр.Л. Геут, С.С. Титов // Актуальные проблемы прикладной математики и механики: тезисы докладов VII Всероссийской конференции посвященной памяти академика А.Ф.Сидорова. Екатеринбург: УрО РАН, 2014. С. 20.

[62] Геут К.Л. О задаче построения нелинейных рекуррентных соотношений / К.Л. Геут, С.С. Титов // IV междисциплинарная молодежная научная конференция УрО РАН "Информационная школа молодого ученого" : сб. научных трудов ЦНБ УрО РАН. Екатеринбург, 2014. С. 203-208.

[63] Глуско К.Л. О следах в конечных полях / К.Л. Глуско, Т.С. Носачёва // Проблемы прикладной математики и механики: Сб. научн. трудов // Под общей ред. С.Л. Дерябина, д-ра физ.-мат. наук. Екатеринбург: УрГУПС. Вып. 58(141). В 2-х т.: В 3-х ч. Т.2. 2007. С. 100-117.

[64] Глуско К.Л. Вектор следа / К.Л. Глуско, Т.С. Носачёва, Титов С.С. // Науч. труды междунар. науч.-практ. конф. «СВЯЗЬ-ПРОМ 2009» в рамках бго Междунар. форума «СВЯЗЬ-ПРОМЭКСПО 2009», поев. 150 - летию со дня рожд. изобретателя радио A.C. Попова. Екатеринбург: УрТИСИ ГОУ ВПО «СибГУТИ», 2009. С. 175-176.

[65] Глуско К.Л. Следы в конечных полях и эллиптическая криптография / К.Л. Глуско, Т.С. Носачёва // Сб. материалов VIII региональной научно-практической конференции студентов, аспирантов и молодых ученых «Безопасность информационного пространства». Челябинск: ЮУрГУ, 2009. С. 226-228.

[66] Глуско К.Л. О минимизации вектора следа / К.Л. Глуско, Т.С. Носачёва // Проблемы теоретической и прикладной математики: Труды 41-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН, 2010. С. 436-440.

[67] Глуско K.JI. О минимизации вектора следа / К.Л. Глуско, Т.С. Носачёва // Сборник тезисов докладов IX научно-практической конференции молодых специалистов. Нижний Тагил: ООО «Тагил-Принт», 2010. С. 307-311.

[68] Глуско К.Л. Vector Trace / К.Л. Глуско, Т.С. Носачёва // Современные компьютерные и информационные технологии: Сборник трудов. Екатеринбург: УрФУ, 2011. С. 126-131.

[69] Глуско Кр.Л. След и полуслед в конечных полях. В 2 т. Т.1 / Кр.Л. Глуско // Мат. науч.-техн. конф., поев. 55-летию УрГУПС. Вып. 97(180). Екатеринбург: УрГУПС. 2011. С. 356-364. 1 электрон, опт. диск (CD-ROM)

[70] Глуско К.Л. Решение квадратных уравнений в конечных полях характеристики два / К.Л. Глуско, С.С. Титов // Проблемы теоретической и прикладной математики: Труды 43-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН, 2012. С. 23-25.

[71] Глуско К.Л. Нормальные базисы и дерево квадратичных расширений бинарных полей / К.Л. Глуско, С.С. Титов // Некоторые актуальные проблемы современной математики и математического образования: Материалы научной конференции «Герценовские чтения 2012». СПб.: БАН. 2012. С. 221-226.

[72] Глуско К.Л. Специфика проблем связи и управления на транспорте / К.Л. Глуско, С.С. Титов // Инновационный транспорт. Екатеринбург: УрГУПС, 2012. С. 44-50.

[73] Глуско К.Л. О решении квадратных уравнений в бинарных полях / К.Л. Глуско, С.С. Титов // Прикладная дискретная математика (Приложение). Томск: ТПУ. 2012. № 5. С. 6-7.

Приложение А. Таблицы степеней корней многочленов

Таблица А. 1. X + X + 1.

Таблица А.2.хь + х3+ 1.

0 1 2 3 Тг

степень 1 0 0 1

0 1 0 0 0

1 0 1 0 0

2 0 0 1 0

3 0 0 0 1

4 1 0 0 1 0

5 1 1 0 1 1

6 1 1 1 1 1

7 1 1 1 0 1

8 0 1 1 1 1

9 1 0 1 0 0

10 0 1 0 1 1

11 1 0 1 1 0

12 1 1 0 0 1

0 1 2 3 4 5 Тг

степень 1 0 0 1 0 0

0 1 0 0 0 0 0

1 0 1 0 0 0 0

2 0 0 1 0 0 0

3 0 0 0 1 0 0

4 0 0 0 0 1 0

5 0 0 0 0 0 1

6 1 0 0 1 0 0 0

7 0 1 0 0 1 0 0

8 0 0 1 0 0 1 0

9 1 0 0 0 0 0 1

10 0 1 0 0 0 0 0

11 0 0 1 0 0 0 0

12 0 0 0 1 0 0 1

Таблица А.З. х6 + д;5+ 1.

Таблица А.4. * + л: + 1.

0 1 2 3 4 5 Тг

степень 1 0 0 0 0 1

0 1 0 0 0 0 0

1 0 1 0 0 0 0

2 0 0 1 0 0 0

3 0 0 0 1 0 0

4 0 0 0 0 1 0

5 0 0 0 0 0 1

6 1 0 0 0 0 1 0

7 1 1 0 0 0 1 1

8 1 1 1 0 0 1 1

9 1 1 1 1 0 1 1

10 1 1 1 1 1 1 1

11 1 1 1 1 1 0 1

12 0 1 1 1 1 1 1

13 1 0 1 1 1 0 0

14 0 1 0 1 1 1 1

15 1 0 1 0 1 0 0

0 1 2 3 4 5 Тг

степень 1 1 0 0 0 0

0 1 0 0 0 0 0

1 0 1 0 0 0 0

2 0 0 1 0 0 0

3 0 0 0 1 0 0

4 0 0 0 0 1 0

5 0 0 0 0 0 1

6 1 1 0 0 0 0 0

7 0 1 1 0 0 0 0

8 0 0 1 1 0 0 0

9 0 0 0 1 1 0 0

10 0 0 0 0 1 1 0

11 1 1 0 0 0 1 1

12 1 0 1 0 0 0 0

13 0 1 0 1 0 0 0

14 0 0 1 0 1 0 0

15 0 0 0 1 0 1 0

Таблица А.5. х6 + х5 + х4 + х + 1. Таблица А.6. х6 + хэ + х2 + х + 1.

0 1 2 3 4 5 Тг

степень 1 0 0 1 0 0

0 1 0 0 0 0 0

1 0 1 0 0 0 0

2 0 0 1 0 0 0

3 0 0 0 1 0 0

4 0 0 0 0 1 0

5 0 0 0 0 0 1

6 1 1 0 0 1 1 0

7 1 0 1 0 1 0 1

8 0 1 0 1 0 1 1

9 1 1 1 0 0 1 0

10 1 0 1 1 1 1 1

11 1 0 0 1 0 0 0

12 0 1 0 0 1 0 0

13 0 0 1 0 0 1 0

14 1 1 0 1 1 1 1

15 1 0 1 0 0 0 0

0 1 2 3 4 5 Тг

степень 1 1 1 0 0 1

0 1 0 0 0 0 0

1 0 1 0 0 0 0

2 0 0 1 0 0 0

3 0 0 0 1 0 0

4 0 0 0 0 1 0

5 0 0 0 0 0 1

6 1 1 1 0 0 1 0

7 1 0 0 1 0 1 1

8 1 0 1 0 1 1 1

9 1 0 1 1 0 0 1

10 0 1 0 1 1 0 1

11 0 0 1 0 1 1 1

12 1 1 1 1 0 0 1

13 0 1 1 1 1 0 0

14 0 0 1 1 1 1 1

15 1 1 1 1 1 0 0

Таблица А.7. х8 + х6 + х5 + х + 1.

Таблица А.8.x8 + х5 + х3 + х + 1.

0 1 2 3 4 5 6 7 Тг

1 1 0 0 0 1 1 0

0 1 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0

2 0 0 1 0 0 0 0 0

3 0 0 0 1 0 0 0 0

4 0 0 0 0 1 0 0 0

5 0 0 0 0 0 1 0 0

6 0 0 0 0 0 0 1 0

7 0 0 0 0 0 0 0 1

8 1 1 0 0 0 1 1 0 0

9 0 1 1 0 0 0 1 1 0

10 1 1 1 1 0 1 1 1 0

11 1 0 1 1 1 1 0 1 1

12 1 0 0 1 1 0 0 0 0

13 0 1 0 0 1 1 0 0 1

14 0 0 1 0 0 1 1 0 1

15 0 0 0 1 0 0 1 1 0

16 0 0 0 0 0 0 0 0 0

0 1 2 3 4 5 6 7 Тг

1 0 1 1 0 1 0 0

0 1 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0

2 0 0 1 0 0 0 0 0

3 0 0 0 1 0 0 0 0

4 0 0 0 0 1 0 0 0

5 0 0 0 0 0 1 0 0

6 0 0 0 0 0 0 1 0

7 0 0 0 0 0 0 0 1

8 1 0 1 1 0 1 0 0 0

9 0 1 0 1 1 0 1 0 0

10 0 0 1 0 1 1 0 1 0

11 1 0 1 0 0 0 1 0 1

12 0 1 0 1 0 0 0 1 0

13 1 0 0 1 1 1 0 0 1

14 0 1 0 0 1 1 1 0 1

15 0 0 1 0 0 1 1 1 0

16 1 0 1 0 0 1 1 1 0

Таблица А.9. х* +х4 +х3 + х2+\

0 1 2 3 4 5 6 7 7>

1 0 1 1 1 0 0 0

0 1 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0

2 0 0 1 0 0 0 0 0

3 0 0 0 1 0 0 0 0

4 0 0 0 0 1 0 0 0

5 0 0 0 0 0 1 0 0

6 0 0 0 0 0 0 1 0

7 0 0 0 0 0 0 0 1

8 1 0 1 1 1 0 0 0 0

9 0 1 0 1 1 1 0 0 0

10 0 0 1 0 1 1 1 0 0

11 0 0 0 1 0 1 1 1 0

12 1 0 1 1 0 0 1 1 0

13 1 1 1 0 0 0 0 1 1

14 1 1 0 0 1 0 0 0 0

15 0 1 1 0 0 1 0 0 0

16 0 0 1 1 0 0 1 0 0

Приложение Б. Орграфы неприводимых многочленов

х6+х3+ 1

Рисунок Б.1. Орграф неприводимых многочленов третей степени

х8 + х5 + х4 + х3+1

Рисунок Б.2. Орграф неприводимых многочленов четвертой степени

Рисунок Б.З. Орграф неприводимых многочленов пятой степени

Рисунок Б.4. Орграф неприводимых многочленов шестой степени

Рисунок Б.5. Орграф неприводимых многочленов седьмой степени с

Тг(х)=Тг(х^)+\

х1+ хь + хь + х*+х2 + х + 1

х1+ хь + х5 + хъ +Х1+ х + 1

х7+хъ +

¥

Рисунок Б.6. Орграф неприводимых многочленов седьмой степени с

Тг(х) = Тг(х~1)

х7 + х4 + х3+х2 + 1

Х7 + Х6 + Х4+Х + 1

Тг(х)=Тг(х~])+\

Рисунок Б.8. Орграф неприводимых многочленов восьмой степени с

Щх)=Тг(х~;)=0

х8 + лг7 + / + / + х2 + л: + 11

V

Рисунок Б.9. Орграф неприводимых многочленов восьмой степени с

Тг(х)=Тг(хх)=\

Рисунок Б. 10. Орграф неприводимых многочленов девятой степени с

Тг(х)=Тг(х~х)+\

I11100011111 ¡1111 ООО1»1]

Рисунок Б.11. Орграф неприводимых многочленов девятой степени с

Тг(х)=Тг(х ')

[ 10011 ООО 101 ]

_•» < _

11ИЮ1001 ГП~|[ п поощри || ШЮ0010011 ||п 00100001 11 110000110101

10101100001

10111100101

_4 % 4 1_

¡1101111011] II 111011 МОП Я 11ШЮ1011 I }7] 1010001 III

10000101101 10110100001

1 Л

10110111001

_4 •> * __

11 ЮЮЮоПТ}111100101011 || 1100101 юн ¡¡ТкГ|п>пюГ|

110100111101 к

¡10000011101 *

¡10111000001

------'

¡110011111111! 11111110011II1) ИХНЮ11111! 11110О0Ш 11 I

Рисунок Б. 12. Орграф неприводимых взаимовозвратных многочленов десятой

степени с Тг(х)=Тг(х~])

х,п + х9 + х5 + х + 1

Vй'+ х9 + х' + х1 + х''+ к> + х4 + + V2 + V + 1

х>° + х,9 + х,7 + х16 + х" + х" + х" + х'° + х9 + х7 + х5 ■>■ х4 + х3 + х+1

х2» + х'9 + хп + х14 + хп +х" +х"> + х9 + х7 + х* + г + а ч 1

\х5+х1+х2+х + 1

[7Т, + х" + х*+х1+хь + хъ+х>+х+\

V V

Рисунок Б. 13. Орграфы неприводимых самовозвратных многочленов десятой

степени с Тг(х) = Тг{х~

| 10000100111]| || пюоюоооТ] 110110101011 1

110011100111]| ||1110011100Т1

|10101000011|| 4

11000001101 11011000001 • о

110001010011 I Я" " 11100101 ООО 11

11011000111П| |1 II110001 юП

10001000111 !* Ц 11100010001

\

\

1 10111111011 1| Ц 1101111 НОГ] \

• о \

|10111110111]| || 11101111101 I

|10110011011]| |Т"|011001101 | • .

1Ю10001111Г| £ ^ШмобшоТ,

• о

11010000101"0100001011

1101100101 п!| || II101001101"] •

¡10000001II Г] ¡Г" ">ГП 1100000011

[юоююнп]^ Цп и 10ЮЮ01,

I-1 £-----

|101оПоГо"П]| ||1ТоТо1_1^Го11

у- "

110010001011

Рисунок Б. 14. Орграф неприводимых многочленов десятой степени с

Тг(х)=Тг(х~х)+\