Теорема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 в

будет обозначаться

.