Vérifier si un polynôme se transforme en facteurs linéaires

Soit un polynôme donné par un circuit arithmétique C de taille s . Étant donné C comme entrée, existe-t-il un algorithme déterministe pour vérifier si tous les facteurs irréductibles de f dans Q [ x 1 , x 2 , … , x n ] sont des formes linéaires? Sur une note connexe, étant donné une forme linéaire 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}]$, peut-on vérifier de façon déterministe silest facteur def. Bien sûr, nous voulons que le temps d'exécution soit polynomial dans les deux cas. Par taille, nous entendons la taille totale des bits. De plus, on peut supposer que le degré defest polynomial dansn.$l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$$l$$f$$f$$n$

$f$$f$

$\ell$$\ell$$f$

$f$$f \bmod \ell$