GCDs for the polynomial ring over a Galois field. You can find many examples of computing the inverse of an element inside a Galois field. (For example here)
What happens if we look at the polynomial ring over a Galois field and would like to compute gcd of two elements? Since this is a euclidean domain the GCD should be well-defined.
Let's say we have $\mathbb{F}_8$ as the Galois field. Since $\mathbb{F}_8$ is isomorphic to $\mathbb{F}_2[X]/(X^3+X+1)$, I can think about the elements of $\mathbb{F}_8$ as the polynomials $aX^2+bX+c$ with $a,b,c \in \mathbb{F}_2$.
Now we look at the polynomial ring $\mathbb{F}_8[Y] \cong \mathbb{F}_2[X]/(X^3+X+1) [Y] \cong \mathbb{F}_2[X,Y]/(X^3+X+1)$. (Are these congruences correct?)
So elements of $\mathbb{F}_8[Y]$ are for example $Y^3+X+1$, or just $Y^2$ or $Y+X^2$. Does anybody knows a way (or references) to calculate the gcd of some of this elements?
Calculating $\gcd(Y^3+X+1, Y^2)$ I only came this far:
$$ Y^3 + X + 1 = Y \cdot Y^2 + X +1$$
$$Y^2 = ?_a \cdot (X+1) + ?_b$$
If I should guess I would say that $2 \geq \deg_y(?_a) > \deg_y(?_b)$ has to be fulfilled, but I think this is impossible.
Any help or any ideas are appreciated! Thanks!
 A: The $\gcd$ of $Y^3+X+1$ and $Y^2$ divides both, and hence divides
$$1\cdot(Y^3+X+1)-Y\cdot(Y^2)=X+1,$$
which is a unit in $\Bbb{F}_2[X]/(X^3+X+1)$. Hence the $\gcd$ divides a unit, which means the $\gcd$ equals $1$ because the $\gcd$ is defined to be monic.
In general, in a polynomial ring over a field the $\gcd$ can be computed by means of the Euclidean algorithm, as I have done above.
To answer your specific question; solving for $?_a$ and $?_b$ in
$$Y^2=?_a(X+1)+?_b,$$
is the same as dividing $Y^2$ by $X+1$ with remainder. Because $X+1$ is a unit in $\Bbb{F}_2[X]/(X^3+X+1)$, the remainder will certainly be $0$.  The inverse of $X+1$ in $\Bbb{F}_2[X]/(X^3+X+1)$ is $X^2+X$ and so
 $?_a:=(X^2+X)Y^2$ and $?_b=0$.
A: You ned rules for simplifying expressions in $\mathbf F_8$. With your setting, if you denote $\omega$ the congruence class of $X$ in $\mathbf F_2[X]/(X^3+X+1)$, you know that
$$\omega^3=\omega+1\qquad\text{(we're in characteristic }2),$$
so the last division is written as 
$$Y^2=(\omega+1)^{-1}Y^\cdot (\omega+1)+0.$$
Now, $\;\omega^3+\omega=1=\omega(\omega^2+1)=\omega(\omega+1)^2$, so $\;(\omega+1)^{-1}=\omega(\omega+1)$ and the last division is ultimately
$$Y^2=\bigl(\omega(\omega+1)Y^2\bigr)\cdot(\omega+1).$$
To answer your last questions, $\deg ?_a=0$, and $\:?_b=0$
