Решение полинома с целыми коэффициентами (уравнение)

[Andrej-V]

Решение полинома с коэффициентами из целых чисел ищется среди частных делителей старшего коэффициента на делители свободного члена, взятых с разными знаками. Так можно найти только рациональные корни.
Но увидел программку, которая искала корни, по какому-то алгоритму разлагая коэффициенты на сумму (при степенях неизвестного ), с тем, чтобы потом объединить члены в сумму и вынести ее за скобки. Это подведение под ответ, т.е. сначала все же находятся решения, а потом многочлен уже ясно как разбивать, или есть какой-то алгоритм для такого полинома?

[незваный гость]

Скорее всего, программа сначала находила множители, а потом демонстрировала, как это разложение работает.

В некоторых случаях такие разложения более или менее очевидны (например, биквадратные уравнения, уравнения с $a_k = a_{n-k}$), иногда нет. Существуют «полные» (т.е. всегда находящие ответ, либо выдающие что ответа не существует) алгорифмы факторизации, но они, как правило, малопригодны для ручных вычислений (если Вы не Эйлер).

[Andrej-V]

незваный гость,

Цитата:

Существуют «полные» (т.е. всегда находящие ответ, либо выдающие что ответа не существует) алгорифмы

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

[незваный гость]

Andrej-V писал(а):

Вы имеете в виду … или что-то другое?

Что-то другое. Например, $-3 + 6 x + 52 x^2 - 105 x^3 + 30 x^4 + 2 x^5$ будет найдено разложение $(3-6x + 2 x^2)(-1 + 18x^2+x^3)$. Ни целых, ни рациональных корней этот полином не имеет.

[Andrej-V]

незваный гость, спасибо.
Не могли бы Вы сообщить, где описаны данные алгоритмы.

[незваный гость]

Например, P. M. A. Moore and A. C. Norman, ``Implementing a Polynomial Factorization and GCD Package'', Proc. SYMSAC '81, ACM (New York) (1981), 109-116 (По ссылке можно загрузить статью). Статья старая (почти 30 лет), а результат и того старше. Зато поиск аналогичных статей дает более свежие ссылки. Можно, наверное, поискать в arxiv. (Зацепка, наверное, уже будет.)

В любом случае, этот вопрос поднимается в системах символьных вычислений.

P.S. Еще один простой случай — это кратные корни. Все их «легко» найти, как $\gcd(P, P')$ (наибольший общий делитель многочлена и его производной).

[Andrej-V]

незваный гость, спасибо, крепко помогли.