1
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ The Euclidean algorithm works for a polynomial ring over any field. GCDs are normalized to be monic. In particular your unit gcd $= 1.$ $\endgroup$ – Bill Dubuque Feb 10 at 21:48
  • $\begingroup$ @Bill So as long as my GCD does not contain any $Y$ it is 1? $\endgroup$ – Sqyuli Feb 10 at 22:04
  • 2
    $\begingroup$ $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.\ \ $ $\endgroup$ – Bill Dubuque Feb 10 at 22:05
  • $\begingroup$ @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$. :) $\endgroup$ – Sqyuli Feb 10 at 22:16
  • 1
    $\begingroup$ Right. Of course we don't actually need to do the final division by the unit. $\endgroup$ – Bill Dubuque Feb 10 at 22:25
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.