Let $k$ be a finite field, $n$ a positive integer and $R := k[x_1,\ldots,x_n]$ the polynomial ring in $n$ variables. Let $f_1,\ldots,f_n\in R$ be polynomials with the following property: $f_i$ has only the variables $x_i,\ldots,x_n$ (so in particular $f_n$ is univariate with variable $x_n$).
Consider the ideal they generate: $I := \langle f_1,\ldots,f_n\rangle$, is it possible to recover the $f_i$'s given some polynomials in $I$ and the respective coefficients w.r.t. the basis?.
More precisely:
Given $h_1,\ldots,h_n, g_{11},\ldots,g_{1n},g_{21},\ldots,g_{2n},\ldots,g_{n1},\ldots,g_{nn}$ polynomials such that $$\left\{\begin{array}{ccccccc} g_{11}f_{1} & + & \cdots & + & g_{1n} f_{n} & = & h_1\\ g_{21}f_{1} & + & \cdots & + & g_{2n} f_{n} & = & h_2 \\ \vdots & & \ddots & & \vdots & & \vdots \\ g_{n1}f_{1} & + & \cdots & + & g_{nn} f_{n} & = & h_n \end{array}\right. $$ is it possible to find $f_1,\ldots,f_n$?.
It seems to me like a hard computational problem, but I'm actually not sure. I did my best and I couldn't break it.
NOTE
This idea comes precisely from what Groebner bases with lexicographic order are. If we compute a lex Groebner basis for $I$, then of course we get $f_1,\ldots,f_n$ (under certain assumptions, they themselves are the reduced lex Groebner basis!).
However, finding Groebner bases is a hard computational problem itself, so this does not count.
"Hard" in the sense that it is not feasible as $n$ grows. For instance, computing Groebner bases is exponential in $n$.
RECENT APPROACH
What I tried to do is to regard that system as a linear system over the field $k(x_1,\ldots,x_n)$ and then perform Gaussian elimination or that sort of things. However, I find it extremely impractical.