multiplication over gf(16)

Question

Can some one show me how to do multiplication over gf(16) step by step

I found this example online, http://userpages.umbc.edu/~rcampbel/Math413Spr05/Notes/12-13_Finite_Fields.html#An_Example. An Example:

$x^4 = x+1$

$x^5 = x^2+x$

$(x^2+x+1) (x^3+x^2+1)$ $= x^5 + 2x^4 + 2x^3 + 2x^2 + x + 1$ $= x^2 + 1$

I know $x^4 = x+1$, because $x^4 mod (x^4 + x + 1)$, but how does $x^5 = x^2+x$?

Answer 1

By distributivity, all you actually In the general casehave to know is how to multiply $1, x,x^2,x^3$ with each other, i.e. express $x^4,x^5,x^6$. In the general case, here is how it goes: \begin{align*} x^4&=\color{red}{x+1} &x^5&=x\cdot x^4=x(x+1)=\color{red}{x^2+x}\\ x^6&=x\cdot x^5=\color{red}{x^3+x^2}&x^7&=x\cdot x^6=x^4+x^3=\color{red}{x^3+x+1} \\ x^8&=(x^4)^2=(x+1)^2=\color{red}{x^2+1}&&\&c. \end{align*}

Answer 2

A better way to do the multiplication (not necessarily more efficient, but a better way to think about it) is by using remainders of polynomial division. So for example, $x^{5} = x(x^{4}+x+1) + x + 1$, and since $x^{4}+x+1 = 0$, $x^{5} = x+1$. You really are looking at polynomials $\bmod{(x^{4}+x+1)}$.