Решение уравнений высших степений

#алгоритм #математика

Прошу подсказать алгоритм для поиска корней уравнения высшей степени. Конкретней:
есть многочлен вида k[0] * x^n + k[1] * x ^ (n - 1) + ... + k[n - 1] k[i] принадлежит
Z и |k[i]| <= 10^9.Известно, что все корни целые.
    

Ответы

Ответ 1

Все целые корни многочлена с целыми коэффициентами являются делителями его свободного
члена. 
Поэтому есть такой путь:
 1. Провести факторизацию свободного члена.
 2. Найти все делители свободного члена как произведения его простых множителей (взятых
в степенях не выше, чем в каноническом разложении),  со знаками плюс и минус.
 3. Отобрать все корни среди делителей.

На самом деле главная проблема - в нахождении одного корня x=a, поскольку в соответствии
с теоремой Безу многочлен разделится на x-a, и следующий корень можно будет подставлять
в частное. При этом повторная факторизация также получается путём несложного пересчёта.


Ответ 2

То, что корни общего уравнения пятой степени[en] и выше не выражаются при помощи
рациональных функций и радикалов от коэффициентов, было доказано норвежским математиком
Нильсом Абелем в 1826 году.



взято из Википедии.
Это я имел ввиду когда говорил что алгоритма нет.


Это вовсе не значит что корни можно найти, например подбором, или графическим методом
(если они есть).


Ответ 3

Перебираем все корни по небольшим простым модулям, затем используем китайскую теорему
об остатках для получения самих корней уравнения (произведение модулей должно быть
достаточно большим).