Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are $8$ elements in $\frac{\mathbb Z_2[x]}{\langle x^3+x^2+1\rangle} = GF(8)$

and this generates the set $\{0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$

We're required to express $\alpha^1$ all the way up to $\alpha^7$ as linear combinations of $1, \alpha$ and $\alpha^2$

$\alpha^1 = \alpha$
$\alpha^2 = \alpha^2$
$\alpha^3 = \alpha^2 + 1$
$\alpha^4 = \alpha^2+\alpha+1$
$\alpha^5 = \alpha+1$
$\alpha^6 = \alpha^2+\alpha$
$\alpha^7 = 1$

I'm really not seeing where these combinations are coming from. Why is $\alpha^3 = \alpha^2+1$?

share|cite|improve this question
up vote 3 down vote accepted

If $\alpha$ is a root of $x^3+x^2+1$, then $\alpha^3+\alpha^2+1=0$, so $\alpha^3=\alpha^2+1$ (since $1=-1$ over $\mathbb{Z}_2$).
From here: $$\begin{array}{l} \alpha^4=\alpha\alpha^3=\alpha(\alpha^2+1)=\alpha^3+\alpha=\alpha^2+\alpha+1\\ \alpha^5=\alpha\alpha^4=\alpha^3+\alpha^2+\alpha=\alpha^2+1+\alpha^2+\alpha=\alpha+1\\ \alpha^6=\alpha\alpha^5=\alpha^2+\alpha\\ \alpha^7=\alpha\alpha^6=\alpha^3+\alpha^2=\alpha^2+1+\alpha^2=1 \end{array}$$ (using $1+1=0$ over $\mathbb{Z}_2$)

share|cite|improve this answer
ahh ok, it's actually just basic algebra now that I look at it that way. Thanks – Arvin Nov 10 '12 at 10:23

Perhaps simplest: use the recursion $\rm\ \alpha^{n+3}\! = \alpha^{n+2} + \alpha^n\ $ arising from $\,\alpha^n\,$ times $\:\alpha^3 = \alpha^2 + 1$.

Alternatively, more generally, one easily calculates the effect of multiplying by $\rm\,\alpha\,$ as follows

$$\begin{eqnarray}\rm \alpha^n &=\,&\rm a\,\ +\,\ b\, \alpha\ +\, c\, \alpha^2\\ \rm \Rightarrow\ \ \alpha^{n+1} &=\,&\rm a\, \alpha + b\, \alpha^2 + c (\alpha^2\! +\! 1)\ \ \ by\ \ \ \alpha^3 = \alpha^2+1 \\ &=\,&\rm c + a\, \alpha + (b\!+\!c)\,\alpha^2 \end{eqnarray}$$

So $\rm\:(a,b,c)\to (c,a,b\!+\!c),\:$ i.e. rotate right $\rm\:(a,b,c)\to (c,a,b)\:$ then add the first into the last.

The same ideas generalize to arbitrary degree.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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