Are all functions on vectors in $GF(2^n)$ representable as polynomial functions? In $GF(2)$, any function from an n-dimensional vector to a number is equal to a polynomial function of n variables.  (See proof below.)  
Question: Is this true for other $GF$, especially $GF(2^8)$? Is there a constructive alogrithm for this?
If so: Does this show that finding the inverse of any invertible function on $GF$ vectors is equivalent to solving a system of nonlinear equations?

Proof: Polynomial funcs are a subset but have same cardinality, since $2^{2^n} = 2^{\sum{nCj}}$.
Constructive Proof: Represent any function as  decision tree.  In $GF(2)$, "if x then y else z" equals $xy + xz + z$.  Recursively replace each branch of decision tree with that expression.
 A: I am assuming that the question is about whether any function $F:GF(2^n)^k\to GF(2^n)$ can be represented as a polynomial $G(x_1,x_2,\cdots, x_k)$ in $k$ variables and with coefficients in $GF(2^n)$. The answer is well known to be affirmative. We can be more precise and say that the degree of the polynomial is at most $2^n-1$ in any one of the variables.
The proof is based on the following
Lemma. Let $a\in GF(2^n)$ be any element. Then there is a polynomial $f_a(x)\in GF(2^n)[x]$ of degree $2^n-1$ such that $f_a(a)=1$ and $f_a(y)=0$ for all $y\in GF(2^n), y\neq a$.
Proof (of Lemma). Let 
$$
g_a(x)=\prod_{y\in GF(2^n),y\neq a} (x-y).
$$
Then 
$$
f_a(x)=\frac1{g_a(a)} g_a(x)
$$
works as prescribed. Q.E.D.
[Edit: In fact here $g_a(a)$ is the product of non-zero elements of the field. This is easily seen to be $=1$ in the case of $GF(2^n)$ and $=-1$ for finite fields of odd characteristic.]
Let us then turn our attention to the main problem. Let $\vec{a}=(a_1,a_2,\ldots,a_k)$ be any vector from $GF(2^n)^k$. Then the polynomial
$$
F_{\vec{a}}(x_1,x_2,\ldots,x_k)=f_{a_1}(x_1) f_{a_2}(x_2)\cdots f_{a_k}(x_k)
$$
has the value $1$, when $\vec{x}=(x_1,x_2,\ldots,x_k)=\vec{a}$, but $F(\vec{x})=0$ whenever
$\vec{x}$ is any other vector in $GF(2^n)^k$.
Therefore we can constructively answer the question by stating that the polynomial
$$
G(x_1,x_2,\ldots,x_k)=\sum_{\vec{a}\in GF(2^n)} F(\vec{a})\cdot F_{\vec{a}}(x_1,x_2,\ldots,x_k)
$$
satisfies the equation $G(\vec{a})=F(\vec{a})$ for all $\vec{a}\in GF(2^n)^k$. Furthermore, $G$ is a polynomial of the prescribed type.
It is nice to be able to sum over all the points in your universe.
