Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 1 из 8)
Министерство образования Российской Федерации
Ярославский государственный университет имени П.Г. Демидова
Математический факультет
Курсовая работа
на тему:
Факторизация полиномов над конечными полями (Алгоритм Берлекампа)
Выполнил: Степанов А.Ю.
Группа КБ-21
Ярославль, 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], при этом либо 
либо . Для доказательства единственности предположим наличие другой пары 
и 
, такой что 
, 
. Тогда 
и 
. A это может иметь место только в случае 
. Следовательно 
и 
Следует заметить, что если К – поле, то для наличия свойства евклидовости достаточно чтобы полином-делитель
не был нулевым полиномом.Легко можно составить алгоритм полиномиалного деления над полем, который более известен как алгоритм PDF (Polynomial Difvision over the Field).
Вход:
и 
- два полинома, 
, причём 
(кстати, алгоритм будет работать и над областью целостности, если в ней
обратим)Выход:
и 
, обладающие свойством евкидовости.Cам алгоритм будет состоять из двух частей:
1. FOR k=m-n DOWNTO 0 // основной вычислительный цикл
BEGIN
FOR j=n+k-1 DOWNTO k