Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ with each $\deg(P_i) \leq \Delta_i$ such that for all $x \in \mathbb{F}_p^n$, $$P(x) = \Gamma(P_1(x), P_2(x), \dots, P_k(x)).$$
For instance, an $n$-variate polynomial over the field $\mathbb{F}_p$ of total degree $d$ factors nontrivially exactly when it is $(2, (d-1,d-1), prod)$-structured where $prod(a,b) = a\cdot b$.

We show that if $p>d$, then for *any* fixed $k, {\bf \Delta}, \Gamma$, we can decide whether a given polynomial $P(x_1, x_2, \dots, x_n)$ of degree $d$ is $(k, {\bf \Delta}, \Gamma)$-structured and if so, find a witnessing decomposition. The algorithm takes poly(n) time. Our approach is based on higher-order Fourier analysis.