6.1.1. Метод Кронекера—Шуберта разложения на множители над целыми числами

Этот метод работает следующим образом. Пусть — данный полином с целыми коэффициентами степени , который мы хотим разложить на множители. Если в действительности разлагается на множители, то один из его множителей должен иметь степень не выше . Пусть наибольшее целое число тогда мы должны выяснить, имеет ли множитель степени . Для различных целых значений вычисляем Если — делитель полинома то число должно быть делителем числа — числа и т. д. Обозначим через конечное множество всех различных целых делителей числа Тогда для выполняем следующие операции: выбираем к элементов 6, из различных и вычисляем интерполяционный полином Лагранжа степени такой, что -для всех I. Если делит то мы нашли множитель полинома и можем рекурсивно применить этот метод к . В противном случае выбираем другое множество к элементов (не совпадающее ни с одним из выбранных ранее множеств), интерполируем и снова проверяем на делимость. Когда мы испытаем все возможные комбинации из или меньшего количества целых значений из мы придем к заключению, что полином неприводим.

Рис. 6.1.1.

Окольный способ разложения на множители произвольного полинома

Пример. Попробуем разложить на множители полином Заметим, что Тогда выберем

точки и сформируем множества

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

получаем

Затем делим на и видим, что не является сомножителем так как

Тогда выбираем и пары для интерполяции

получаем

Видим, что на этот раз является сомножителем полинома так как

и это — полное разложение на множители полинома поскольку по критерию Эйзенштейна (теорема 3.2.15) эти два сомножителя неприводимы.

Очевидно, что время вычислений рассмотренного метода экспоненциально, и для метод работает очень неэффективно.