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

Метод Кронекера — метод разложения многочлена с целыми коэффициентами на неприводимые множители над кольцом целых чисел; предложен в 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=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)$

Конец если

Конец цикла

Конец цикла

Конец если

Конец.

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

Пример

$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;