# 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!

• The Euclidean algorithm works for a polynomial ring over any field. GCDs are normalized to be monic. In particular your unit gcd $= 1.$ – Bill Dubuque Feb 10 at 21:48
• @Bill So as long as my GCD does not contain any $Y$ it is 1? – Sqyuli Feb 10 at 22:04
• $c = X+1\in \Bbb F_8\,$ is a nonzero element of your coefficient field so it is a unit (invertible). The final step is $\, Y^2 = (c^{-1}Y^2)\, c + 0\$ so the gcd $= c$. Typically poly gcds are normalized to be monic (lead coef $= 1$), which normalizes constant gcds to be $1$, so the gcd $= 1.\ \$ – Bill Dubuque Feb 10 at 22:05
• @Bill Thanks a lot! I got it. So if I would try $gcd(Y^2, Y+X)$ the final step would be $-XY = -Y \cdot X + 0$ and since $X$ is the unit $gcd(Y^2, Y+X) = 1$. :) – Sqyuli Feb 10 at 22:16
• Right. Of course we don't actually need to do the final division by the unit. – Bill Dubuque Feb 10 at 22:25

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