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

Метод Кронекера — метод разложения многочлена с целыми коэффициентами на неприводимые множители над кольцом целых чисел; предложен в 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$, успешно найден ответ.
Конец если. Конец цикла. Если не успешно найден ответ то
Цикл от $i=0$ до $[n/2]$
$U$ — множество делителей $f(i)$ (целочисленных)
цикл для каждого $u\in U$
построить многочлен $g$ степени $i$, такой, что
$g(j)=u(j)$ для $j=0...i$
если $f$ делиться на $g$, то
$m=i$, решение успешно найдено, ответ $g(j)$
Конец если, конец цикла, конец цикла, конец если.
Конец.

ЗАМЕЧАНИЕ. Достаточно научиться разлагать на множители многочлены со старшим коэффициентом, равным единице.

Пример

$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-й степеней, не имеющие рациональных корней).

Литература

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