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

Введём для

функцию Мёбиуса следующим образом:

если

если

для некоторого простого p и некоторого

если n раскладывается в произведение r различных простых чисел

Если n делится на квадрат простого числа, то

; для простого числа p . Также m и n – взаимно простые числа, то , то есть - мультипликативная функция. А для мультипликативных функций верна теорема

Если f – мультипликативная функция, а функция F определена соотношением

, то F – также мультипликативная функция.

Доказательство: Пусть числа m и n – взаимно простые. Тогда каждый делитель d числа

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

Теперь ещё небольшой факт:

Если

, то .

Доказательство: Функция

является мультипликативной, если e=0 и в то же время , если . Если n делится на простое число, то , из этого всего и следует это утверждение.

Формула обращения Мёбиуса. Для любой функции f, определённой на множестве натуральных чисел (не обязательно мультипликативной), если

для каждого , то .

Доказательство: Положим

. Тогда суммы очевидно равны. По определению F

.

Теперь изменим порядок суммирования и воспользуемся тем, что если

, то далее следует .

В последней сумме коэффициент при

равен 0, кроме случаев или . Эта сумма сводится к единственному члену .

Теорема. Число всех нормированных неприводимых полиномов степени n над

задаётся формулой .

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

, , подставим в предидущую формулу.

Теперь можно перейти к тестам неприводимости полиномов в

.

Тест1. Полином

степени n>1 неприводим в тогда и только тогда когда

для .

Причём если полином приводим то тест сработает достаточно быстро. Для неприводимых полиномов этот тест становится медлительным из-за вычислений НОД в

. Для исправления этого создан

Тест2. Полином

степени n>1 неприводим в тогда и только тогда когда и для всех , - простые делители n.

Алгоритм Берлекампа разложения на множители над конечными полями. Идея Берлекампа основана на китайской теореме об остатках для полиномов:

Пусть

- полиномы из , причём взаимно прост с при . Пусть - произвольные полиномы из . Тогда существует единственный полином , такой что и . Это же можно сформулировать на языке отображений:

Отображение, ставящее в соответствие полиному

вектор , где , является биекцией между и .

Доказательство: Проводится расширенным алгоритмом Евклида. То есть определяются полиномы

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

Теорема. В поле GF(p) – поле Галуа (конечное поле, содержащее p (простое число) элементов) имеет место разложение:

.

Доказательство: В поле Галуа

(а также по малой теореме Ферма) . Значит s является корнем полинома , то есть (x-s) является делителем . А так как это выполнено для всех то . Также следует заметить, что и это два нормированных полинома, из этого всего и следует их равенство.