1
$\begingroup$

I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$ defined on the quotient ring $GF(2)[x]/\langle x^3+x+1\rangle$. I have done the Euclidean algorithm but I am stuck in the forward process to get the inverse. Please explain how to do it from reverse.

$\endgroup$
8
  • $\begingroup$ Do it this way - much less painful and less error-prone. $\endgroup$ Commented Nov 15, 2018 at 0:25
  • $\begingroup$ Normally $x$ stands for an indeterminate, when $x^3+x+1$ is a polynomial. Polynomials don't have inverses in a finite field. If, as I suspect, $x$ stands for some element of $GF(8)$ you need to tell us which element. Or at least, tell us its minimal polynomial. You see, very often the field $GF(8)$ is defined as the quotient ring $GF(2)[x]/\langle x^3+x+1\rangle$. But, in that field the coset of $x^3+x+1$ is equal to zero. Again implying that it has no inverse (can't divide by zero). $\endgroup$ Commented Nov 15, 2018 at 4:14
  • $\begingroup$ The (only) other alternative is to have defined $GF(8)$ as the quotien $GF(2)[x]/\langle x^3+x^2+1\rangle$. In that case the coset of $x^3+x+1$ equals the coset of $x^2+x$ (because $(x^3+x+1)-(x^3+x^2+1)=x^2+x$). You can find the inverse of that by the usual process involving extended Euclid. You see, to positively id an element of the quotient ring we customarily reduce them by the polynomial defining the field. $\endgroup$ Commented Nov 15, 2018 at 4:17
  • 1
    $\begingroup$ But, Mariam, the polynomial $x^8+x^4+x^3+x+1$ defines the version of the field $GF(2^8)=GF(256)=GF(2)[x]/\langle x^8+x^4+x^3+x+1\rangle$ IIRC used in AES cryptosystem (among other things). $\endgroup$ Commented Nov 15, 2018 at 20:10
  • 1
    $\begingroup$ Here I spell out what $GF(8)$, also known as $\Bbb{F}_8$, looks like. If I were to use $GF(256)$ in a computer program I would build a similar logarithm table for $GF(256)$ and use it calculate inverses. $\endgroup$ Commented Nov 15, 2018 at 20:15

1 Answer 1

0
$\begingroup$

Hint: The field $GF(8)$ is isomorphic to $GF(2)[x]/\langle x^3+x+1\rangle$ or to $GF(2)[x]/\langle x^3+x^2+1\rangle$. The polynomials $x^3+x+1$ and $x^3+x^2+1$ are the only irreducible polynomials over $GF(2)$ (and they are conjugate). The elements of $GF(8)$ are the residue classes of the polynomials $ax^2+bx+c$, where $a,b,c\in GF(2)$. So maybe you should rethink about your question.

$\endgroup$
2
  • $\begingroup$ What do you mean by those polynomials being conjugate? $\endgroup$ Commented Nov 23, 2018 at 21:50
  • 1
    $\begingroup$ The comment thread under the question sounds a lot like the OP didn't actually mean $GF(8)$ but $GF(2^8)$, represented using the primitive polynomial $x^8+x^4+x^3+x+1$. $\endgroup$ Commented Nov 23, 2018 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .