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

Из теоремы 3.3.20 нам известно, что в для любого существует неприводимый полином степени более того, из теоремы 3.3.21 нам известно, что — произведение всех неприводимых полиномов в степени которых делят Теорема 3.3.21 будет использована ниже для (частичного) разложения на множители разных степеней; в данном разделе мы представим некоторый результат о — числе всех нормированных неприводимых полиномов степени в Заметим, что, согласно теореме полином степени имеет в качестве сомножителей неприводимых полиномов степени d для каждого d, делящего ; отсюда следует, что степень произведения всех нормированных неприводимых полиномов над степени которых делят равна

Чтобы получить выражение для нам понадобятся некоторые дополнительные результаты, и прежде всего мы введем следующее (Bender et al., 1975; Berlekamp, 1968; Childs, 1979)

Определение 6.2.4. Функция Мёбиуса определяется для следующим образом:

Заметим, что если делится на квадрат простого числа, и что для любого простого . Кроме того, легко проверяется, что если , то , т.е. — мультипликативная функция. (Другим примером мультипликативной функции является функция Эйлера )

Имеет место следующая теорема о мультипликативных функциях.

Теорема 6.2.5. Если — мультипликативная функция и функция F определена соотношением то F — также мультипликативная функция.

Локазательство. Пусть . Тогда каждый делитель d числа может быть единственным способом представлен в виде , где . Поэтому

Обратное для данного утверждения также имеет место, но нам оно не понадобится. Мы докажем сейчас теорему о функции .

Теорема если .

Доказательство. Из теоремы 6.2.5 нам известно, что функция

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

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

то

Доказательство. Положим Равенство двух сумм становится очевидным. Затем по определению F мы имеем

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

По теореме 6.2.6 в последней сумме коэффициент при равен 0, кроме случаев, когда или . Поэтому эта сумма сводится к единственному члену и теорема доказана.

Мы теперь в состоянии получить формулу для

Теорема 6.2.8. Число всех нормированных неприводимых полиномов степени над задается формулой

Доказательство. Из теоремы 3.3.21 следует, что степень произведения всех нормированных неприводимых полиномов над степени которых делят , равна

Применяя теорему 6.2.7 при получаем желаемый результат.

Интересно знать, насколько быстро растет Приведенная ниже табл. 6.2.1 для взята из (Simmons, 1970).

Таблица 6.2.1 Рост функции

Тесты неприводимости в Ниже предлагаются два теста для определения, является ли нормированный полином степени неприводимым в третий тест будет представлен в разд. 6.2.4. Ни один из этих тестов не требует, чтобы полином был свободным от квадратов, но создается впечатление, что в среднем применение сначала алгоритма разложения на свободные от квадратов множители позволяет экономить время.

Тест 1. Полином степени неприводим в тогда и только тогда, когда

Этот тест непосредственно следует из теоремы 3.3.21. Если полином приводим, то данный тест работает очень быстро. Однако для неприводимых полиномов он становится довольно неэффективным из-за большого числа вычислений Можно уменьшить число вычислений если воспользоваться следующим тестом.

Тест 2. Полином степени неприводим в тогда и только тогда, когда (а) для всех где — простой делитель числа .

Локазательство. Заметим, что если — неприводимый полином, то любой корень уравнения лежит в поле а поскольку — то откуда немедленно следует условие (а). Кроме того, поскольку — неприводимый полином степени , у него нет корней ни в каком поле откуда непосредственно следует условие (b).

Для доказательства обратного предположим, что выполнены условия (а) и (b). Из условия (а) следует, что все корни полинома лежат в . Предположим теперь, что имеется неприводимый сомножитель степени Тогда все корни полинома лежат в поле порожденном над любым из этих корней. Поэтом Значит, для некоторого максимального делителя - числа , и все корни полинома лежат в . В этом случае, однако, что противоречит (b). Следовательно, полином неприводим.