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

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

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

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

1. Если степень многочлена равна , то степень хотя бы одного множителя многочлена не превосходит  ;
2. Значения как , так и в целых точках — целые числа, причем ) делит для любого целого ;
3. При фиксированном , если не равно 0, то может принимать только конечное множество значений, состоящее из делителей числа ;
4. Коэффициенты многочлена однозначно восстанавливаются по его значениям в точке.

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

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

Рассмотрим  — многочлен степени . Пусть приводим над . Тогда и один из двух многочленов и имеет степень не выше . Пусть без ограничения общности . Тогда , следовательно . Рассмотрим различных целых чисел таких, что . Поскольку числа имеют конечное количество целых делителей, можно перебрать всевозможные наборы значений для . По каждому такому набору построим интерполяционный многочлен степени . Если теперь , к многочленам и можно применить тот же метод, и так до тех пор, пока все множители не станут неприводимыми. В противном случае, если , многочлен уже является неприводимым.

Алгоритм Кронекера (одномерный)

Дано:
Надо:
 — степень полинома ,  — степень полинома
,  — целочисленное.
Цикл от до
если , то , , успешно найден ответ.
Конец если. Конец цикла. Если не успешно найден ответ то
Цикл от до
 — множество делителей (целочисленных)
цикл для каждого
построить многочлен степени , такой, что
для
если делиться на , то
, решение успешно найдено, ответ
Конец если, конец цикла, конец цикла, конец если.
Конец.

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

Пример

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

Литература

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