Comprobando si un polinomio se convierte en factores lineales

Sea un polinomio dado por un circuito aritmético C de tamaño s . Dado C como entrada, ¿existe un algoritmo determinista para verificar si todos los factores irreducibles de f en Q [ x 1 , x 2 , ... , x n ] son formas lineales? En una nota relacionada, dada una forma lineal l = ∑ n i $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}$, ¿podemos verificar de manera determinista si$l$es factor de$f$. Por supuesto, queremos que el tiempo de ejecución sea polinómico en ambos casos. Por tamaño, nos referimos al tamaño total de bits. Además, se puede suponer que el grado de$f$es polinomial en$n$.

$f$$f$

$\ell$$\ell$$f$

$f$$f \bmod \ell$