0
$\begingroup$

I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$. 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$
  • $\begingroup$ Do it this way - much less painful and less error-prone. $\endgroup$ – Gone Nov 15 '18 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$ – Jyrki Lahtonen Nov 15 '18 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$ – Jyrki Lahtonen Nov 15 '18 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$ – Jyrki Lahtonen Nov 15 '18 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$ – Jyrki Lahtonen Nov 15 '18 at 20:15
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by those polynomials being conjugate? $\endgroup$ – Tobias Kildetoft Nov 23 '18 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$ – hmakholm left over Monica Nov 23 '18 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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