|
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 в 
будет обозначаться  .
Введём для  функцию Мёбиуса  следующим образом:
 если 
если  для некоторого простого p и некоторого 
если n раскладывается в произведение r различных простых чисел
Если n делится на квадрат простого числа, то 
; для простого числа p 
. Также m и n – взаимно простые числа, то 
, то есть  -
мультипликативная функция. А для мультипликативных функций верна теорема
Если f – мультипликативная функция, а функция F определена
соотношением  , то
F – также мультипликативная функция.
Доказательство: Пусть числа m и n – взаимно простые. Тогда каждый делитель d
числа  может быть
представлен в виде произведения взаимно простых 
, таких что  и 
. Поэтому
Теперь ещё небольшой факт:
Если  , то  .
Доказательство: Функция 
является мультипликативной, если e=0 
и в то же время  ,
если  . Если n
делится на простое число, то 
, из этого всего и следует это утверждение.
Формула обращения Мёбиуса. Для любой функции f, определённой на множестве
натуральных чисел (не обязательно мультипликативной), если
 для каждого  , то  .
Доказательство: Положим  . Тогда суммы очевидно равны. По определению F
 .
Теперь изменим порядок суммирования и воспользуемся тем, что если 
, то  далее следует 
.
В последней сумме коэффициент при 
равен 0, кроме случаев 
или  . Эта сумма
сводится к единственному члену 
.
Теорема. Число всех нормированных неприводимых полиномов степени n над 
задаётся формулой  .
Доказательство: Возьмём  ,  , подставим в предидущую формулу.
Теперь можно перейти к тестам неприводимости полиномов в  .
Тест1. Полином  степени n>1 неприводим в  тогда и только тогда когда
 для  .
Причём если полином приводим то тест сработает достаточно быстро. Для
неприводимых полиномов этот тест становится медлительным из-за вычислений НОД в 
. Для исправления этого создан
Тест2. Полином 
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9
| 
