Как определить, является ли многочлен квадратом другого м-на

[Padawan]

Как по многочлену определить, является ли он квадратом другого многочлена?

[ИСН]

Мобыть, скрестить его с производной от него же - и истина откроется?

Добавлено спустя 1 минуту 20 секунд:

Чёрт; вообще говоря, нет.

[Руст]

Пусть задан $P(x)=a(x-x_1)^{k_1}...(x-x_m)^{k_m}$ разложение на неприводимые. Найдём НОД этого многочлена с производной $S(x)=GCD(P(x),P'(x))=a(x-x_1)^{k_1-1}...(x-x_m)^{k_m-1}$ и вычислим $R(x)=P(x)/S(x)=(x-x_1)...(x-x_k)$. Отметим, что для этих операций не требуется разложение на множителей (это приведено только для демонстрации). Если многочлен P(x) квадрат, то P(x) должен делится на квадрат R(x). Отношение обозначим через P1(x), который так же должен быть квадратом, который привродится аналогично к P2(x) и т.д.

[RIP]

Алгоритм Руста будет работать долго, если $m$ мало, поэтому предлагаю небольшую модификацию.
Делим $P(x)$ на наибольшую возможную степень $R(x)$. Если эта степень нечетна, то сразу стоп. Если же четна, то делаем то же самое для частного итд.
Думаю, что можно еще эффективнее.
Например, можно искать НОД частного и $R(x).$ Это сразу дает $R_1(x)$ для частного (без вычисления $S_1(x)$ и последующего деления) Но это имеет смысл делать, если степень частного больше степени $R(x)$.

[Padawan]

Все это хорошо и эффективно. Но мне хотелось бы найти условие (в виде каких-то уравнений) на коэффициенты исходного многочлена. Или это невозможно?

Я хочу сделать в P(x) подстановку x(t)=A*exp(at)+B*exp(bt)+...+C*exp(ct), подобрав A,B,...,C,a,b...,c так, чтобы получился квадрат некоторой другой линейной комбинации экспонент.
И тогда можно было бы рационализировать, например, эллиптический интеграл.