GCDs for the polynomial ring over a Galois field.

Question

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!

Answer 1

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$.

Answer 2

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$