I'm trying to understand how to apply Lagrangian interpolation for a function $F : GF(2^k) \to GF(2^k)$, but am having some difficulty. Suppose I have a function $F : GF(2^2) \to GF(2^2)$ given by the following mapping $F$ (where every element is in the field $GF(2^2)$ defined by the only irreducible polynomial $p(x) = x^2 + x + 1$):
$0 \to 1$
$1 \to x$
$x \to x + 1$
$x + 1 \to 0$
Now suppose I want to find some polynomial $q(x)$ such that $q(x) = F(x)$. Do I simply apply the interpolation formula: $q(x) = \sum_{i = 1}^4y_i\prod_{1 \leq j \leq 4, j \not= i}^{4} \frac{x - x_j}{x_i - x_j}$? If so, can someone try and walk me through how this is done? My calculations did not yield a valid polynomial $q(x)$.
Let's denote $GF(4)=\{0,1,\alpha,\alpha+1\}$ with $\alpha^2=\alpha+1$, so that $x$ is freed as an indeterminate.
Let $z\in GF(4)$. The Lagrange interpolation needs polynomials $f_z(x)$ with the property $f_z(z)=1$ and $f_z(y)=0$, if $y\in GF(4)$ is $\neq z$. Let's find $f_0(x)$. To that end we first construct the polynomial $$ g(x)=(x-1)(x-\alpha)(x-(\alpha+1)) $$ that vanishes whenever $x\in GF(4)\setminus\{0\}$. Then $f_0(x)=g(x)/g(0)$ will work. But here $$ g(0)=(0-1)(0-\alpha)(0-(\alpha+1))=1\cdot\alpha\cdot(\alpha+1)=\alpha^2+\alpha=1, $$ so we actually get $f_0(x)=g(x)$. Expanding the polynomial $g(x)$ actually gives something simple (leaving this to you as an exercise), namely $$ g(x)=1+x^3. $$ With a little bit of experience you could have seen this right away. After all, all the non-zero elements of $GF(4)$ are third roots of unity so the polynomial $x^3$ takes value $1$ whenever $x\in GF(4)^*$. Anyway, we know that $f_0(x)=1+x^3$.
What about the other polynomials $f_z(x)$, $z\neq0$. We can either do the same thing, or we can use linear substitutions. The latter approach gives us the recipe $$ f_z(x)=f_0(x-z). $$ Why does this work? If we plug in $x=z$ we get $f_z(z)=f_0(z-z)=f_0(0)=1$. OTOH if we plug in $x=y\in GF(4),y\neq z$ we get $f_z(y)=f_0(y-z)=0$, because here $y-z\neq0$ and $f_0$ vanishes at the non-zero elements of $GF(4)$.
Finally we are well placed to do Lagrange interpolation. Let $F:GF(4)\to GF(4)$ be any function. We can write it as a polynomial $$ q(x)=F(0)f_0(x)+F(1)f_1(x)+F(\alpha) f_\alpha(x)+F(\alpha+1) f_{\alpha+1}(x). $$ All that is left to do is to plug in the values and expand it out.