Can anyone point me in the right direction with the following problem?

Given that $$GF(8)=\frac{Z_{2}}{x^3+x^2+1}= \frac{Z_{2}}{x^3+x+1}$$

Find $\beta$ as a function of $\alpha$ , where $\alpha$ is a root of $x^3+x+1$ and $\beta$ is a root of $x^3+x^2+1$


Brief answer:

As one polynomial is just the reverse of the other, the roots of one are the inverses of the roots of the other. Hence we may take $\beta=\alpha^{-1}$

Here is the complete story:

One can find the three possibilities this way.

Neither $0$ nor $1$ is a root of either $X^3+X^2+1$ or $X^3+X+1$; and it is trivial to see that these polynomials are coprime and so have no common root.

The order of the multiplicative group of $\mathbb{F}_8$ is seven and so is cyclic of that order.

If $\alpha$ is a root of $X^3+X^2+1$ so is $\alpha^2$ since $\alpha^6+\alpha^4+1=(\alpha^3+\alpha^2+1)^2=0$. Hence the roots of this polynomial are $\alpha, \alpha^2, \alpha^4(=(\alpha^{2})^2)$ and these are distinct as the multiplicative order of $\alpha$ is $7$.

In the same way the roots of $X^3+X+1$ are $\beta,\beta^2,\beta^4$. That accounts for all the elements of $\mathbb{F}_8$.

Therefore $\beta,\beta^2,\beta^4$ must be the "missing" powers of $\alpha$, namely $\alpha^3,\alpha^5,\alpha^6$: or more elegantly $\alpha^{-1}, \alpha^{-2}, \alpha^{-4}$.

So $\beta$ is one of $\alpha^{-1}, \alpha^{-2}, \alpha^{-4}$.


Let $\alpha$ be a root of $x^3+x+1$. Then a general element of $GF(8)$ has the form $a+b\alpha + c\alpha^2$ for some $a,b,c \in GF(2)$. Need to solve for for $a,b,c$ in $(a+b\alpha + c\alpha^2)^3+(a+b\alpha + c\alpha^2)^2+1 = 0$ Recall that $u^2=u$ for any $u \in GF(2)$ and $2u=0$ for any $u \in GF(8)$. After simplifying you'll find $$ (1+b+c+bc) + (b+c+ab+ac)\alpha + (b+ab)\alpha^2 = 0$$ from which you can determine that $\beta$ can be taken to be $1+\alpha, 1+\alpha^2, $ or $1+\alpha+\alpha^2$

  • $\begingroup$ Wouldn't it just be $x(x-1)$ ? I am not entirely comfortable with modular polynomial arithmetic. $\endgroup$ – Chezky Steiner May 22 '17 at 2:25
  • $\begingroup$ $(\alpha -1)^3 +(\alpha -1)^2 + 1 = (\alpha^3 + \alpha^2 + \alpha + 1) +(\alpha^2 + 1) + 1 = \alpha^3 + \alpha + 1 = 0$ will work. $\endgroup$ – sharding4 May 22 '17 at 2:28
  • $\begingroup$ So $\beta = \alpha -1$. That does answer my original question, but I would like to understand the process by which you found that. Sorry if it seems obvious, I don't have such a strong handle on the related concepts. $\endgroup$ – Chezky Steiner May 22 '17 at 2:32
  • $\begingroup$ Sorry. My previous answer was based on an invalid method. There may be some slicker approach, but all I could find was to just grunge through the computations in $GF(8)$. $\endgroup$ – sharding4 May 22 '17 at 15:29

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.