Коротко и по делу — критерии, практические приёмы и рекомендации для больших $n$.
Основные теоремы/факты
- Теорема о рациональных корнях (Rational Root Theorem): если $P(x)=a_n{x}^n+\cdots +a_{1}x+a_0$ с целыми коэффициентами и $\frac{p}{q}$ — несократимая рациональная корень, то $p\mid a_0$ и $q\mid a_n$.
- Для приведённого (моногонического) многочлена ($a_n=1$) все рациональные корни целые и делители $a_0$.
- Ограничение по модулю (Cauchy): все корни удовлетворяют $|x|\le 1+\underset{0\le i<n}{\max }\frac{|a_i|}{|a_n|}$. Это ограничивает кандидатов по величине.
- Мультипликативность/примитивность (Гаусс): очистите коэффициенты от общего множителя (content) — достаточно работать с примитивным многочленом.
- Если $\gcd (P,P^{\prime })\ne 1$, есть кратные корни; найдите и удалите общий множитель перед тестами.
Практический алгоритм (пошагово)
1. Очистить многочлен: поделить на content, сделать примитивным.
2. Вычислить список кандидатных рациональных корней по Rational Root Theorem: все $\pm \frac{p}{q}$ с $p\mid a_0,q\mid a_n$, в несократимой форме, дополнительно ограничить по Cauchy.
- Для моногонического случая достаточно $p\mid a_0$.
3. Просеять кандидатов:
- Быстрое целочисленное подставление/синтетическое деление для оставшихся кандидатов.
- До точной проверки можно использовать модульное сито: выбрать несколько простых $p$ (не делящих $a_n,a_0$), редукция $P$ по модулю $p$ и проверка, является ли $\overline{\frac{p}{q}}$ корнем в ${\mathbb{F}}_p$. Отсев очень быстрый.
4. При нахождении корня выполнить деление многочлена, получить фактор меньшей степени и повторить.
5. Для кратных корней сначала вычислить $\gcd (P,P^{\prime })$ и разделить.
Когда кандидатов слишком много / большие $n$ - Если число делителей $a_0,a_n$ большое или $n$ велико, полный перебор неэффективен. Вместо этого применяют:
- Модульную факторизацию: факторизовать $\overline{P}$ в ${\mathbb{F}}_p[x]$ для нескольких простых, затем Hensel- lift и сборку факторов над $\mathbb{Z}[x]$.
- LLL-алгоритм (Lenstra–Lenstra–Lovász) для рекомбинации модульных факторов и обнаружения целочисленных/рациональных факторов.
- Численные методы + рациональная реконструкция: найти приближенный корень с высокой точностью, затем восстановить рациональное число методом непрерывных дробей/LLL (если корень действительно рационален и «мал»).
- Инструменты CAS (PARI/GP, Sage, Magma, Mathematica) используют сочетание модульной факторизации, Hensel- lifting и LLL и обычно эффективнее для больших степеней.
- Дополнительные фильтры: правило Декарта (количество положительных корней) и сторм-секвенции для локализации реальных корней и сокращения числа кандидатов.
Замечания по эффективности
- Для небольших степеней и небольших коэффициентов рациональная теорема + прямой перебор (с модульным ситом) обычно оптимальны.
- Для больших $n$ и/или больших коэффициентов предпочтительны модульная факторизация + Hensel + LLL; это стандартный подход в компьютерной алгебре.
- Всегда сначала убрать тривиальные случаи: общий множитель коэффициентов, моногоничность, деление на $\gcd (P,P^{\prime })$.
Краткая последовательность выбора метода
- Простые/маленькие входные данные: Rational Root Theorem + Cauchy + модульное сито + синтетическое деление.
- Большие $n$ / большие коэффициенты: модульная факторизация → Hensel → LLL / использование CAS.
Если нужно — могу привести пример реализации перебора кандидатов и модульного сита на псевдокоде.