Метод Кронекера

Метод Кронекера — метод разложения многочлена с целыми коэффициентами на неприводимые множители над кольцом целых чисел; предложен в 1882 Кронекером.

Алгоритм Кронекера находит для данного многочлена $F(x)$ многочлен $f(x)$ , такой, что $F(x)$ делится на $f(x)$ , или доказывает, что такого многочлена нет.

Содержание

1 Описание метода
2 Одномерный алгоритм Кронекера
3 Многомерный алгоритм Кронекера
- 3.1 Запись условий задачи
- 3.2 Запись алгоритма
4 Литература

Описание метода

Алгоритм Кронекера основан на следующих соображениях:

Если степень многочлена $F$ равна $n$ , то степень хотя бы одного множителя $f$ многочлена не превосходит $\left\lfloor {n\over 2} \right\rfloor$ ;
Значения как $F$ , так и $f$ в целых точках — целые числа, причем $f(i$ ) делит $F(i)$ для любого целого $i$ ;
При фиксированном $i$ , если $F(i)$ не равно 0, то $f(i)$ может принимать только конечное множество значений, состоящее из делителей числа $F(i)$ ;
Коэффициенты многочлена $f$ однозначно восстанавливаются по его значениям в точке.

Таким образом, для $f$ получается конечное число возможностей; непосредственным делением проверяем, получили ли делитель многочлена $F$ .

Строгое Изложение:

Рассмотрим $f(x) \in \mathbb{Z}[x]$ — многочлен степени $n$ . Пусть $f(x)$ приводим над $\mathbb{Z}$ . Тогда $\! f(x) = g(x)h(x)$ и один из двух многочленов $g(x)$ и $h(x)$ имеет степень не выше $n/2$ . Пусть без ограничения общности $\operatorname{deg} \, g(x) \leqslant n/2$ . Тогда $\forall a \in \mathbb{Z} \; h(a) \in \mathbb{Z}$ , следовательно $f(a) \vdots g(a)$ . Рассмотрим $m=n/2+1$ различных целых чисел $a_i, i=\overline{1,m}$ таких, что $f(a_i)\not=0$ . Поскольку числа $\!f(a_i)$ имеют конечное количество целых делителей, можно перебрать всевозможные наборы значений для $\!g(a_i)$ . По каждому такому набору построим интерполяционный многочлен $\!g^*(x)$ степени $m-1=n/2$ . Если теперь $f(x)\vdots g^*(x)$ , к многочленам $\!g^*(x)$ и $\frac{f(x)}{g^*(x)}$ можно применить тот же метод, и так до тех пор, пока все множители не станут неприводимыми. В противном случае, если $\forall g^*(x) \ f(x)\!\!\not\vdots g^*(x)$ , многочлен $f(x)$ уже является неприводимым.

Одномерный алгоритм Кронекера

Запись алгоритма

Дано: $f(x) \in \mathbb{Z}[x]$

Надо: $g(x) \in \mathbb{Z}[x]$

Где: $n$ — степень полинома $f$ , $m$ — степень полинома $g$ , $i$ — целочисленное.

Цикл от до

Если () то

Ответ найден.

Конец если

Конец цикла

Если (ответ не найден) то

— множество делителей (целочисленных)

Цикл от $i = 0$ до $[n/2]$

$M$ — множество делителей $f(i)$ (целочисленных)

$U :=$ декартово произведение U и M

Цикл для каждого $u \in U$

Построить многочлен $g$ степени $i$ , такой, что $g(j)=u(j)$ для $j=0...i$

Если ( $f$ делиться на $g$ ) то

$m=i$

Решение успешно найдено, ответ $g(j)$

Конец если

Конец цикла

Конец если

Конец.

ЗАМЕЧАНИЕ. Достаточно научиться разлагать на множители многочлены со старшим коэффициентом, равным единице. Действительно, если старший коэффициент равен a, то домножив на a_n−1 и сделав замену $x = y/a$ , сводим задачу к этому случаю. После ее решения остается сделать обратную замену и сократить на общий множитель a_n−1 . Однако этот метод обычно оказывается неэффективным: из-за увеличения коэффициентов ухудшаются различные оценки и скорость работы алгоритмов. Поэтому в большинстве работающих алгоритмов таких преобразований не производится.

Реализация на Maple

kronecker:=proc(f::polynom)
 local g,i,n,U,V,j;
 with(linalg);
 n:=degree(f)/2; 
 U:=myfactor(subs(x=0,f));
 for i from 1 to n do
   U:=U,myfactor(subs(x=i,f));
   V:=mcarp(U);
   for j in V do   
    g:=interp([$0..i],j,x);
    if rem(f,g,x)=0 and not type(g,'constant') then     
      print(g);               
    end if;
   end do;
  end do;  
end proc;
 
myfactor:=proc(n::integer)
 local a,b,i,j;
 b:=[];
 for i from 1 to abs(n) do
  if (irem(n,i)=0) then  
   b:=ArrayTools[Concatenate](2,b,i);
   b:=ArrayTools[Concatenate](2,b,-i);
  end if;
 end do;
 convert(b,'list');
end proc;
 
# Next 2 functions computes cartesian product of multiple sets.
# They are taken from http://people.oregonstate.edu/~peterseb/mth355/docs/355f2001-cartesian-product.pdf
carp:=proc(X,Y)
 local Z,x,y;
 Z:={};
 for x in X do
  for y in Y do
   Z:=Z union {[x,y]};
  end do;
 end do;
 return Z;
end proc;
 
mcarp:=proc()
 local Z,k,x,y; option remember;
  if nargs=0 then
   Z:={};
  elif nargs=1 then
   Z:=args[1];
  else Z:={};
   for x in mcarp( seq(args[k], k=1..nargs-1) ) do
    for y in args[nargs] do
    Z:= Z union {[op(x),y]};
    end do;
   end do;
  end if;
 return Z;
end proc;

Пример

$f(x)=x^5-x^4-2x^3-8x^2+6x-1$ (это многочлен с целыми коэффициентами и без рациональных корней). Если $f(x) = g(x)*h(x)$ где степень k многочлена $g(x)$ не больше степени $h(x)$ , то k=2. Пусть Тогда f(0)=1; f(1)= −5; f(2)=-21. Делители этих чисел: для первого +1 и −1, для второго +1, −1, +5, −5, для третьего 1, 3, 7, 21. Всего получается $2*4*8=64$ комбинации. Две комбинации отличающиеся лишь знаком, дают два многочлена. Поэтому можно проверять лишь половину. Остаются 32 случая. Перебирая все эти случаи, можно найти лишь один многочлен 2-й степени, делящий $f(x)$ . Это $g(x)=x^2-3x+1$ . Оба сомножителя этого разложения неприводимы (как многочлены 2-й и 3-й степеней, не имеющие рациональных корней).

Многомерный алгоритм Кронекера

Запись условий задачи

Пусть $D$ — область целостности с однозначным разложением на множители, $f(x_1,...,x_n) \in D[x_1,...,x_n]$ . Требуется разложить $f$ на неприводимые множители.