Ecuații de câmp ascuns - existența zerourilor

Lăsa $\mathbb{F}_q$ să fie un câmp finit de dimensiune $q$ (prim), și $\mathbb{F}_{q^n}$ fii o diplomă-$n$ extensia algebrică a $\mathbb{F}_q$.

Lăsa $F$ să fie o funcție polinomială $\mathbb{F}_{q^n} \la \mathbb{F}_{q^n}$ a formei $$ \sum_{i, j \in I_A} A_{i,j} X^{q^i + q^j} + \sum_{i\in I_B} B_i X^{q^i} + C $$ Unde $A_{i,j}, B_i,$ și $C$ sunt niște constante în $\mathbb{F}_{q^n}$.

Dată la întâmplare $D \in \mathbb{F}_{q^n}$, trebuie să găsim o soluție $X$ pentru $F(X) = D$.

Întrebarea mea este: de ce există o astfel de soluție? Are gama de $F$ acoperi $\mathbb{F}_\mathbb{q^n}$? Cum verificăm?

O astfel de soluție nu există neapărat decât dacă $F(X)$ este o polinom de permutare peste $\mathbb F_{q^n}$.

Polinoamele de permutare sunt tocmai acelea a căror gamă acoperă întregul câmp.

Hârtia Recunoașterea funcțiilor de permutare în timp polinomial (de Neeraj Kayal, unul dintre autorii testului de primalitate a timpului polinomial AKS) oferă un test de timp polinomial.