Проверка полиномиальных множителей на линейные

Позволять $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ быть полиномом, заданным арифметической схемой $C$ размера $s$, Данный$C$ в качестве входных данных, есть ли детерминированный алгоритм, чтобы проверить, все ли неприводимые факторы $f$ в $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$такое линейные формы? На связанной ноте, учитывая линейную форму$l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$можем ли мы проверить детерминистически $l$ является фактором $f$, Конечно, мы хотим, чтобы время выполнения было полиномиальным в обоих случаях. Под размером мы подразумеваем общий размер бита. Кроме того, можно предположить, что степень$f$ является полиномом в $n$,

Насколько я знаю, лучший алгоритм, который мы имеем в настоящее время, чтобы проверить, если $f$(заданный арифметической схемой) может быть разложен на линейные факторы с помощью рандомизированного алгоритма Кальтофена (PDF), который фактически производит черные ящики для всех неприводимых факторов$f$и работает над любым достаточно большим полем. Фактически, эта проблема полиномиальной факторизации для общих цепей была недавно показана Коппарти, Сарафом и Шпилкой эквивалентной проблеме черного ящика-PIT для общих цепей.

Как уже упоминалось Бруно, если вы заинтересованы в проверке, данная схема делится на данную $\ell$, то это сводится к конкретной проблеме PIT. Мы не знаем, как сделать это детерминистически в целом, но я знаю один особый случай, когда мы знаем, как сделать это ЯМ. Существует детерминированный многополосный алгоритм (PDF), чтобы проверить, является ли данный$\ell$ делит данный разреженный полином $f$,

(Еще один банальный особый случай, когда $f$задается ограниченным верхним трехконтурным вентилятором. Там,$f \bmod \ell$ это также ограниченная трехконтурная схема с глубиной вентилятора, и мы знаем, как сделать PIT за детерминированное полиномиальное время.)