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

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

JWf

Геут Кристина Леонидовна

НОРМАЛЬНЫЕ БАЗИСЫ В КОНЕЧНЫХ ПОЛЯХ И ИХ ПРИЛОЖЕНИЯ

01.01.06 - Математическая логика, алгебра и теория чисел

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

005568971

2015

Екатеринбург - 2015

005568971

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Уральский государственный университет путей сообщения», на кафедре «Высшая и прикладная математика».

Научный руководитель: Титов Сергей Сергеевич

доктор физико-математических наук, профессор, ФГБОУ ВПО «Уральский государственный университет путей сообщения», г. Екатеринбург

Официальные оппоненты: Романьков Виталий Анатольевич

доктор физико-математических наук, профессор, ФГБОУ ВПО «Омский государственный университет им. Ф. М. Достоевского», г. Омск

Ананичев Дмитрий Сергеевич

кандидат физико-математических наук, доцент, ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина», г. Екатеринбург

Ведущая организация: ФГБОУ ВПО «Южно-Уральский

государственный университет», г. Челябинск

Защита диссертации состоится 02 июня 2015 года в 11.30 на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в научной библиотеке и на сайте Института математики и механики УрО РАН: http://wwwrus.imm.uran.ru/C16/Diss/.

Автореферат разослан 30 апреля 2015 года.

Ученый секретарь диссертационного совета, кандидат физ.-мат. наук

И. Н. Белоусов

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

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

Актуальность темы исследования. Теория конечных полей была построена в работах Ферма, Эйлера, Лежандра, Гаусса, Галуа, Диксона и других выдающих ученых, и до последней четверти 20-го века развивалась как область чистой математики, но в связи с потребностями кодирования и криптографии в настоящее время активно развиваются прикладные аспекты теории. Вопросам эффективной реализации арифметики в конечных полях посвящено много работ и специальных книг, отечественных и зарубежных авторов1,2'3.

Неприводимые многочлены, корни которых образуют базис для представления элементов конечных полей, аналогичны простым числам. Они нашли свое применение в различных областях математики, информационной техники и защите информации. Использование свойств неприводимых многочленов позволяет максимизировать эффективность компьютерной реализации арифметики в конечных полях, что имеет особое значение для криптографии и теории кодирования. Таковы, например, реализация электронной цифровой подписи на эллиптических кривых4,5; коды Рида-Маллера, Рида-Соломона и другие ; программирование дискретных устройств; современные стандарты шифрования. Для нахождения таких многочленов нет определенного (детерминированного) алгоритма, так что их построение производится подбором, т.е. вероятностными алгоритмами, что требует временных затрат и объемных вычислений. Коэффициенты многочленов, как элементы конечных полей характеристики два, можно интерпретировать в многобитовые последовательности для передачи по современным каналам связи. Поэтому важной

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

2 Ленг С. Алгебра. М.: Мир. 1968. 360 с.

3 Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х т. Т. 1.: пер. с англ. М.: Мир, 1988. 430 с.

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

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

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

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

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

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

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

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

- построение нормальных базисов расширений конечных полей характеристики два и три;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Основные результаты диссертации опубликованы в 25 работах, список которых приведен в конце автореферата.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

ние о быстром и упрощенном нахождении вектора следа неприводимого многочлена. Результаты исследований опубликованы в работах [15-21].

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

вид:

q=p"=> Tr(z) = z + т? + z'2 + ... + zr' (1)

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

Если поле GF(^m) является расширением поля GF(g), то вычисляется след элемента поля GF(<7™).

Tr:G¥(qm)-^G¥(q),q=pn.

Trm(z) = z + z" + z'2 + ... + ¡Г (2)

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

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

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

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

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

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

Sr(z) = д: = z + z4 + z16 + ... + z2"'1. (3)

В книге Болотова A.A., Гашкова С.Б., Фролова А.Б.1 вычисление решения квадратного уравнения в полях GF(2"), где и четное, сводится к системе линейных уравнений, вычисление которой довольно громоздко и требует временных затрат. Трудность задачи поиска формулы решения для четной степени иллюстрирует следующее

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

Z2* 2

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

кеК

1 Болотов A.A., Гашков С.Б., Фролов А.Б. 280 с. Указ. соч.

7

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

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

а = р + р"1, (4)

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

Р=Д/,^(0 = Г/(; + Г1), где/- многочлен степени т расширяемого поля Р, F — многочлен для расширенного поля К.

2 2я"'

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

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

После последовательного применения операции СКР получены неприводимые многочлены В^ц степени я = 2\ образующие нормальные базисы:

£>!(*) = *+1;

В2(х) = х2+х + 1;

£>з(х)=х4 + х3 + х2 + х + 1;

П4(х)=х* + х7 +х6+х* +х1 + х+ 1;

05(х)=хХ6+хи+хи + хп+хп + хп+хъ + хь + х', + хг+х1 + х+\-,

АЮ = *32 + *31 +*30 + *28 + х11 + X26 + X24 + X22 + X17 + X16 + х15 + X10 + х8 + + х6 + х5+х4 + х2 + х+ 1.

В7(х) = Xм + х63 + X62 + х61 + х60 + х56 + х54 + X52 + X51 + х48 + X47 + х44 + + х43 + х41 + х39 + X33 + х34 + X33 + х32 + х31 + х30 + х29 + X25 + х23 + X21 + X20 + х17 + + х16 + х13 + х12 + х10 + х8 + х4 + х3 + х2 + х+1.

Примеры решения квадратных уравнений в нормальных базисах описаны в работах [2, 7, 22-23, 25].

Вторая глава посвящена алгоритмам расширений бинарных полей.

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

В параграфе 2.1 описана функция

*„ = йя(*) = й(й(Л...(й(й(дО)))), (5)

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

(А)2

(6)

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

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

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

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

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

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

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

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

+х2+ 1 = 0, (7)

х^+3 + + х4 + х-2 + 1 = 0, (8)

x"+7 + x"+,+x8 + x6+x4+x2+l=0. (9)

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

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

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

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

m=A?+t) (ю)

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

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

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

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

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

Утверждение 2.7. Если h(x) = z, deg f = п, неприводим, j{z) = О, deg g = 2л, g(x) = 0, неприводим то Tr(z) = Тг(х), где h(z) = (z + z~') равен следу элемента z из поля GF(22") в поле GF(2").

Утверждение 2.8. Если в поле GF(2m), т > 1, z - корень симметричного многочлена f, то однозначно определен периодический многочлен g,

гдеу=—--его корень. И наоборот, если g — периодический, то f - симмет-

2 + 1

ричный, где z = — +1.

у

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

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

Взяв в поле GF(2J) при 5 = 0 неприводимый многочлен fo(x) = х + 1 степени и = 3° = 1, можно построить неприводимый многочлен третьей степени /i(x) = х3 + + х + 1 при 5=1, решая уравнение Х]3 + х\ + 1, где Х\ - корень многочлена /о- Далее, решая уравнение Хг + х2 - Х\, получим корень х2 многочлена/(х) =/](х3 + х) = (х3 + х)3 + (х3 + x) + 1 = х9 + х1 + х5 + х + 1, который также будет неприводимым, согласно таблицам неприводимых многочленов1.

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

Утверждение 2.9. Для любого п = 3s, s = 1, 2, 3, ..., справедливо тождество Г„(х) = x[/o(x)]2[/i(x)]2... K-i(x)]2.

Теорема 2.1. Многочлен/,(х) неприводим для любого С = 0, 1,2,...

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

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

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

Задача проверки простоты чисел р эквивалентна генерации многочленов вида х^1 + о\хГ~2 + о2хГг + ... + а^х + ар с заданными свойствами.

Если р - простое, многочлен + +...+^+1=0 неприводим, так что t* = 1 и К, € GF(3f>_1) порядка р, то вычисление следа С, (операция СКР) дает неприводимые многочлены g,{x), связанные с известными многочленами Чебышёва-Диксона /,(х)2. Еще один шаг вычислений следа дает многочлены G,(x). Так, к примеру, при п = 4, р = 17, G4((3) = (З4 + р3 - 602 - (3 +1, по mod 3 G^P) совпадает с ft,(X).

1 Болотов A.A., Гашков С.Б., Фролов А.Б. 280 с. Указ. соч.

2 Болотов A.A., Гашков С.Б., Фролов А.Б. 328 с. Указ. соч.

Проверка простоты чисел Ферма р = 22 +1 эквивалентна генерации неприводимых симметричных многочленов степени п = 2к + 1 и порядка р = 2 +1, имеющих особую значимость в кодировании.

Утверждение 3.2. Если представить число Ферма р как порядок симметричного неприводимого многочлена fix) степени п, то простота р равносильна равенству р порядков всех fix). Если же р = 1т не простое, то существуют fix) порядка р, I и т.

т, „ Л ord f(x)-\ 22'

Количество fix) равно-— = —.

п п

При к = 0,р = 3 = ord f, т.е. многочлен deg/= 2, ord/= 3 ,fix)=x2+x+ 1; к = 1, р = 5 = ord / - один симметричный многочлен deg / = 4, fix) = x4 + xs +х2 + х+ 1;

к = 2,р= 11 = ord / - два многочлена deg/= 8, Лх)=х* + х7 + х6 + х4+х2 + х+ 1 (111010111), fix)=x* + x5+x* + x?+ 1 (100111001); к = 3,р = 257 = ord/ имеется 16 многочленов с deg/= 16: к = 4,р = 65537, имеется 2048 многочленов с deg/ = 32. к = 5, р = 4294967297 = 641*6700417, из которых 10 многочленов deg/= 64, ord/= 641;

к=6,р= 18446744073709551617 = 274177*67280421310721. Пусть р - простое число, и пусть gp-t(x) разлагается в произведение симметричных многочленов степени 2к\ тогда имеем g^\(x) делит g2k, т.е. 2к+ 1=0 (modр), т.к. р = ord/дляДх), делящего gp-i(x).

Обратно, пусть р — простое число, к — наименьшее такое, что 2к = -1 (mod р). Тогда gp_i(x) делит g2k (и такая степень двойки в индексе - наименьшая возможная), отсюда gp-\(x) разлагается в произведение неприводимых симметричных многочленов степеней 2т, где к/т нечетно, отсюда к = т, т.к. ясно, что если р - простое число и gp~i(x) разлагается в произведение неприводимых многочленов qj(x) (j > 1) одной и той же степени. Пусть deg/= п, ord f-p,fix) неприводим, тогда |<х>| =р в К/~ GF(2"), и для любого у Ф 1, у е <х> имеем <у> = <х> (т.к. р - простое число); следовательно, никакой уф\,у е <х> не принадлежит собственному подполю поля GF(2") ~ Kf, т.е. у удовлетворяет неприводимому уравнению той же степени п'.

Степень таких неприводимых многочленов определяется как наименьшая натуральная степень п такая, что 2" =l(mod р). Соответственно их количество j = ——-. В случае если неприводимых многочленов q/x) (j > 1) иско-

1 Лидл Р., Нидеррайтер Г. Указ. соч.

мого порядка два, то их поиск сводится к нахождению наибольшего общего

л р-\ р

делителя многочленов s(x) = ^x mod/? и /(*) = <=> f(;c) = jV (выбор

í=l i=О i»l

формулы зависит от значения следа многочлена д/х)). Если же таких многочленов qj(x) > 2, то задача сложнее, т.к. НОД в таком случае будет произведением всех <7; (X) с заданным значением следа Тг(х) = {0, 1} [8].

Используя описанный алгоритм, были найдены все 10 многочленов J[x) степени deg/= 64 порядка ord/= 641:

11110001100100110111010111001110101110011101011101100100110001111;

10110111000110011110010010001101110110001001001111001100011101101;

10101010010110101011000111001010101010011100011010101101001010101;

10000011000101001010010000111010101011100001001010010100011000001;

11011000110010110110110101000011111000010101101101101001100011011;

11000001111001011000010001011100100111010001000011010011110000011;

10010010110001100100001001100101110100110010000100110001101001001;

11010100100011110001011110011000100011001111010001111000100101011;

10111110011010100000100101111011111011110100100000101011001111101;

11100000100000010101100101011101110111010100110101000000100000111;

11110001100100110111010111001110101110011101011101100100110001111.

Результаты исследований изложены в работах [8, 11-12].

Проверка простоты чисел Мерсенна д = 2m - 1 эквивалентна генерации примитивных многочленов степени т и порядка 2т - 1.

Утверждение 3.4. Примитивность всех неприводимых многочленов степени т равносильна простоте числа 2т — 1.

В параграфе 3.4 рассматривается задача построения нелинейной рекурсии первого порядка для произвольного линейного рекуррентного соотношения второго порядка с постоянными коэффициентами, поставленная и решенная в статье В.Н. Ушакова1 для чисел Фибоначчи.

Утверждение 3.6. Если в уравнении X2 + a\l} + аг = 0 порядок а2 конечен и равен р, то для /я+1 = С,Х"+1 + С2Ц*' при заданных Сь С2 корень х = А" является функцией одной переменной f„ и задается формулой р видов.

При конечном порядке а2 решение в общем виде [14]:

—, (П)

2С> (/.+>//. -4а"2СС2)\

Следствие 3.1. В случае, когда C¡ = - С2и D ~ а2, формула (11) сводится к формулам из статьи В.Н. Ушакова\

При аг = 1 доказана

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

Теорема 3.1. Пусть/0 = С1 + = С,Х. + С2Г' , X2 + а1Х' + 1=0, тогда линейное рекуррентное соотношение второго порядка /„ = С\Хп + СгХ'" приводится к рекуррентному соотношению первого порядка

/„+1=Л/„±Я^//„2-4С,С2, (12)

1 + V"1 V — х-1

где А = —-—, В = —-—, и нелинейность в соотношении (12) выражается

единственным квадратным корнем.

Для иллюстрации рекуррентных соотношений рассмотрены коммутирующие функции - аналог многочленов Чебышёва-Диксона.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1) Доказана теорема о нормальных базисах при симметричном квадратичном расширении конечных полей; сгенерированы все неприводимые многочлены степени 2" над ОР(2), построено полное бинарное дерево таких многочленов и изучены их свойства;

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

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

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

Благодарности. Автор выражает глубокую признательность своему научному руководителю, доктору физ.-мат. наук, профессору Сергею Сергеевичу Титову за постановку задач и помощь в работе, а также Александру Алексеевичу Махневу за ценные советы и поддержку.

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

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

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

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

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

Публикации в других изданиях

4. Построение бинарного дерева посредством поликвадратичного расширения / Е.А. Букина, О.О. Ванцева, М.Ю. Филиппов, Кр.Л. Геут // Математическое моделирование системных взаимосвязей в прикладных исследованиях : сб. науч. тр. Екатеринбург: Изд-во УрГУПС, 2013. Вып. 13(196). С. 73-77.

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

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

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

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

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

10.Геут Кр.Л. О генерации неприводимых многочленов / Кр.Л. Геут, С.С. Титов // Математическое моделирование системных взаимосвязей в прикладных исследованиях : сб. науч. тр. Екатеринбург : Изд-во Ур-ГУПС, 2013. Вып. 13(196). С. 12-18.

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

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

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

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

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

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

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

18.Глуско К.Л. О минимизации вектора следа / К.Л. Глуско, Т.С. Носачёва // Проблемы теоретической и прикладной математики: Труды 41-й Всерос-

сийской молодежной конференции. Екатеринбург: УрО РАН, 2010. С. 436—440.

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

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

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

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

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

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

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

Геут Кристина Леонидовна

Нормальные базисы в конечных полях и их приложения

Специальность: 01.01.06 - Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Подписано в печать 26.03.15. Формат 60x84/16 Усл. печ. л. 1,2. Тираж 100 экз. Заказ 159

Издательство УрГУПС 620034, г. Екатеринбург, ул. Колмогорова, 66