Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.