I wonder is there any easy way to evaluate elements of GF$(256)$: meaning that I would like to know what $\alpha^{32}$ or $\alpha^{200}$ is in polynomial form? I am assuming that the primitive polynomial is $D^8+D^4+D^3+D^2+1$. For example for GF$(8)$ what we do is as follow to calculate $\alpha^3$ is divide it by $\alpha^3+\alpha+1$ and we get $\alpha+1$ but here in GF$(256)$ this will be really tedious so I would like to know is there any way to calculate above expressions or similar expressions like $\alpha^{100}$ in GF$(256)$.
Thanks.
Best Answer
GF$(256)$ is small enough that you should construct an antilog table for it and save it for later reference rather than compute the polynomial form of $\alpha^{32}$ or $\alpha^{100}$ on the fly each time you need it. The computer version of the antilog table is an array that stores the polynomial forms for $1 (= \alpha^0), \alpha, \alpha^2, \cdots, \alpha^{254}$ in locations $0, 1, 2, \cdots, 254$. For human use, the table is constructed with two columns and looks something like this $$\begin{array}{r|l} \hline\\ i & \alpha^i \text{ equals}\\ \hline\\ 0 & 00000001\\ 1 & 00000010\\ 2 & 00000100\\ 3 & 00001000\\ 4 & 00010000\\ 5 & 00100000\\ 6 & 01000000\\ 7 & 10000000\\ 8 & 00011101\\ 9 & 00111010\\ 10 & 01110100\\ 11 & 11101000\\ 12 & 11001101\\ \vdots & \vdots\quad \vdots \quad \vdots\\ 254 & 10001110\\ \hline \end{array}$$ The $i$-th entry in the second column is the polynomial representation of $\alpha^i$ in abbreviated format. For example, $\alpha^8$ is stated to be equal to $00011101$ which is shorthand for $\alpha^4+\alpha^3+\alpha^2+1$. The entry for $\alpha^i$ is obtained by shifting the entry immediately above by one place to the left (inserting a $0$ on the right) and if there is an $\alpha^8$ term thus formed, removing it and adding $\alpha^4+\alpha^3+\alpha^2+1$ (i.e. XORing $00011101$) into the rightmost $8$ bits. This process is easy to mechanize to produce the antilog table by computer rather than by hand (which can be tedious and mistake-prone).