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

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

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

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

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

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

Если ($f(i)=0$) то

$g=x-i$

$m=1$

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

Конец если

Конец цикла

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

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

Цикл от $i=1$ до $[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 dо;  
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,-1, +3, -3, +7,-7,+ 21, -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$ на неприводимые множители.

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

Дано: $f\in \mathbb {Z} [x_{1},...,x_{n}]$

Надо: $G$ — разложение

Переменные: многочлен ${\bar {f}}\in \mathbb {Z} [y]$, разложение ${\bar {G}}$ многочлена ${\bar {f}}$, множество $M$ элементов типа $\mathbb {Z}$.

Идея реализации: Редуцировать задачу к одномерному случаю, путем введения новой неизвестной и заменой всех переменных достаточно высокими степенями этой неизвестной. Факторизовать получившийся многочлен. Выполнить обратную подстановку, пробным делением убедиться, получено ли желаемое разложение.

Начало
Выбрать целое $d$ большее, чем степени отдельных переменных в $f$ заменить все переменные степенями новой неизвестной $y$:

${\bar {f}}(y):=S_{d}(f)=f(y,y^{d},...,y^{d^{n-1}})$

Разложить ${\bar {f}}(y)$ на неприводимые множители, то есть

${\bar {f}}(y)={\bar {g}}_{1}(y)...{\bar {g}}_{s}(y),\quad {\bar {g}}_{i}(y)\in \mathbb {Z} [y],\quad 1\leq i\leq s$

$G$.число_множителей := 1

$m:=1$

$M:=\{1,...,s\}$

Цикл пока $m\leq [s/2]$

Цикл для каждого подмножества ${i_{1},...,i_{m}}\subset M$ пока $m\leq [s/2]$

$g_{i_{1},...,i_{m}}(x_{1},...,x_{n}):=S_{d}^{-1}({\bar {g}}_{i_{1}}(y){\bar {g}}_{i_{2}}(y)...{\bar {g}}_{i_{m}}(y))$

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

$G$.множитель[$G$.число_множителей]:=$g$

$G$.число_множителей:=$G$.число_множителей + 1

$f:=f/g$

$s:=s-m$

$M$.удалить{$i_{1},...,i_{m}$}

Конец если

Конец цикла

$m:=m+1$

Конец цикла
$G$.множитель[$G$.число_множителей]:=$f$
Конец

В этом алгоритме обратное преобразование $S_{d}^{-1}$ определяется на одночленах по формуле:

$S_{d}^{-1}(y^{b_{1}+db_{2}+...+d^{v-1}b_{v}})=x_{1}^{b_{1}}...x_{v}^{b_{v}}$

$(0\leq b_{i}<d$ для $1\leq i\leq v,\quad v\in \mathbb {Z} )$, далее $S_{d}^{-1}$ распространяется по линейности.

Литература

• Е. В. Панкратьев «Элементы компьютерной алгебры.» М.:МГУ, 2007;
• Kronecker L. «J. reine und angew. Math.», 1882;
• Окунев Л. Я. «Высшая алгебра», М., 1937;
• Курош А. Г. «Курс высшей алгебры», 11 изд., М., 1975;