Fix a prime p. Given a positive integer k, a vector of positive integers =(12k) and a function :Fkp\Fp, we say that a function P:FnpFp is (k) -structured if there exist polynomials P1P2Pk:FnpFp with each deg(Pi)i such that for all xFnp, P(x)=(P1(x)P2(x)Pk(x)) For instance, an n-variate polynomial over the field Fp of total degree d factors nontrivially exactly when it is (2(d−1d−1)prod) -structured where prod(ab)=ab .

We show that if d">pd, then for *any* fixed k , we can decide whether a given polynomial P(x1x2xn) of degree d is (k) -structured and if so, find a witnessing decomposition. The algorithm takes poly(n) time. Our approach is based on higher-order Fourier analysis.