<s>[INST] multiplication over gf(16) 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$?
 [/INST] 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)}$.
</s>