Курсовая: Факторизация полиномов над конечными полями

Министерство образования Российской Федерации

Ярославский государственный университет имени П.Г. Демидова

Математический факультет

Курсовая работа

Ярославль, 2004

Краткий план.

1. Введение в алгебру полиномов.

2. Наибольшие общие делители полиномов над полем.

3. Неприводимые сомножители полиномов.

4. Разложение полиномов на свободные от квадратов множители.

5. Основные факты о конечных полях.

6. Разложение полиномов на множители в конечных полях.

7. Вычисление числа неприводимых полиномов над конечным полем.

8. Подход к алгоритму Берлекампа.

9. Алгоритм Берлекампа.

10. Пример.

1. Введение в алгебру полиномов. Пусть K – область целостности, x –

независимая переменная – её можно рассматривать как просто формальный символ, а

не как независимый аргумент области К. Тогда выражение вида

, где для

называется полиномом от переменной х над K.

Полиномы называются равными, если у них равны коэффициенты при

соответствующих степенях х

Определим так сумму и произведение полиномов:

Очевидно, что сумма и произведение полиномов от х над К также представляют собой

полином над K. Mножество полиномов от х над областью целостности К само

является областью целостности, которая обозначается как K[x]. Покажем это.

Возьмём полиномы и

. Тогда их произведение

. Знаком 0 здесь обозначен нулевой многочлен -

. Предположим и

, так что и

не обращаются в 0. Следствием из этого является

так как и

являются элементами области целостности К. Но

- коэффициент при старшем члене полинома-произведения, т.е.

, что означает отсутствие в K[x] делителей нуля.

Рассмотрим полином

- не равный тождественно 0 полином над К. Тогда полином

делит полином если

- некоторый полином над К, что

. В этом случае используется запись

. Полином

называется делителем полинома

.

Докажем важный факт, известный как свойство евклидовости:

Пусть К – область целостности, а

и - два полинома

над К[x] и пусть

обратим в К. Тогда существуют единственные полиномы

и (частное и

остаток соответственно), что

, .

Доказательство производится индукцией по степени делимого

.Если или

то положим и

. В противном случае пусть

, и образуем

полином . При этом

так как убрана старшая степень х. В случае

или - всё

доказано. В противном случае по индукции

для некоторых и

, таких что .

Поэтому , что и

доказывает существование полиномов

и . Ясно, что

и - полиномы в

кольце К[x], при этом либо

либо . Для

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

и , такой что

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9