Смекни!
smekni.com

Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 4 из 8)

Теорема1. Если F - поле, |F|=q,

,
, то
.

Cледствие. При условиях теоремы любой

удовлетворяет уравнению

Теорема2. Пусть F - поле, |F|=q,

,
. Если n – порядок элемента a, то n|(q-1).

Теорема3. Пусть F – поле, |F|=q, тогда

, p – простое,
.

Cледствие. Если F – конечное поле, то оно имеет характеристику p – простое натуральное число, таким образом содержит подполе, изоморфное

.

Теорема о примитивном корне (4). Элемент группы называется примитивным корнем, если его степени 0,1,2,… пробегают все элементы группы. Cуть теоремы в том, что в поле F из q элементов найдётся элемент а , что каждый ненулевой элемент поля представляет степень а, т.е. a – примитивный корень, и порядок элемента а равен q-1.

Теорема 5. Пусть F – поле и

- нормализованный полином из F[х]. Тогда существует таккое содержащее F поле K, что в К[x] полином
разлагается в произведение линейных сомножителей. Это поле К называют полем расщепления для
. К примеру,

C – поле расщепления для любого полинома из Q[x].

Пусть

- корень некоторого ненулевого полинома из F[x]. Тогда элемент х называют алгебраичным над F. Иначе – трансцендентным.

Теорема 6. Пусть

алгебраичен над F. Тогда существует единственный неприводимый нормированный полином
, что
, и каждый полином
с корнем а делится на m(x). Этот полином называют минимальным полиномом элемента а над F.

Разложение полиномов на множители в конечных полях. Любой полином степени n в

может быть разложен на множители за конечное число шагов, так как существует
возможных полиномов степени <n, но такой алгоритм "проб и ошибок” чрезмерно трудоёмкий(этот алгоритм осуществляется через PDF). Так что неплохо бы иметь более быстрые алгоритмы.

Если взять полином

, то его производная
равна нулю тогда и только тогда
для каждого i. Это будет выполнено в случаях p|i или
для каждого i. Поэтому
если
- полином от
. Теперь несколько обобщим данную ранее теорему о НОД(
,
):

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

- примитивный полином в K[x], отличный от константы. Возьмём его однозначное разложение на множители
.Пусть
, если
, в противном случае
. Тогда НОД(
,
)=
.

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

На этой теореме также основана некоторая модификация алгоритма PSQFF, но перед этим нужно доказать ещё две вспомогательные теороемы.

Теорема 1. Пусть

- полином в
. Тогда
.

Доказательство:Пусть

,
.Тогда

=
(все биномиальные коэффициенты делятся на р). Так как
(малая теорема Ферма) то
=
.

Теорема 2. Пусть

- полином в
. Тогда
в том и только в том случае, когда p(x) eсть р-ая степень некоторого полинома
.

Доказательство:

. Обратно, если
, то
. Тогда
.

Таким образом получен следующий алгоритм PSQFFF разложения на свободные от квадратов множители над конечным полем (Polynomial Square-free Factorization over a Finite Field) :

Вход:

- нормированный полином из
, не являющийся константой, p>0 – простое число.

Выход:

и е, такие что
- разложение полинома
на свободные от квадратов множители.

Реализация:

BEGIN

k:=0; m:=1; e:=0 // инициализировали

label3:

j:=1;

;

IF

THEN GOTO label1

label2:

e1:=j*m; IF e1>e THEN FOR i:=e to e1-2 do

;

; e:=e1;

;
// вычислили

IF

THEN

BEGIN

;
; incr(j); GOTO label2

END

IF

THEN EXIT

label1:

; inkr(k); m:=m*p; GOTO label3;

END

Вычисление числа неприводимых полиномов над конечным полем. Согласно ранее доказанным фактам в

найдётся неприводимый полином степени n для любого n. Также
- произведение всех неприводимых полиномов в
, степени которых делят n. Отсюда степень произведения всех неприводимых полиномов, степени которых делят n равна
. Число всех нормированных полиномов степени n в
будет обозначаться
.