How to compute in the multiplicative group of finite field "economically" and efficiently Let $GF(p^n)$ be a finite field, then the additive group is isomorphic to $\mathbb Z / (p\mathbb Z)^n$, and it is simple to compute in that group. The multiplicative group is always cyclic (a standard result), so we have $GF(p^n)^{\times} \cong \mathbb Z/((p^n - 1)\mathbb Z$. But how to compute in the multiplicative group when the elements are named as in the additive group. For example for $GF(5)$ we see for example here that we could not take just the numbers, multiply them and take the modulos to $4$, but accidently the modulos to $5$ works in this example (a coincidence?). To compute modulo $4$ we had to identify $1$ with the residue class of $\overline 0$; $2$ with the residue class of $\overline 1$; $3$ with the class of $\overline 3$ and $4$ with the class of $\overline 2$.
I find this kinda unintuitive and cumbersome? How do you compute with finite fields in the multiplicative group; as shown above to bring in the "standard multiplication tables" everyone learns at school into play by residue calculus is error-prone as how the elements in the field are numbered need not represent the residue classes.
But maybe I have overlooked something all the years and in the end it is kinda easy to compute in the multiplicative group (as it is in the additive group, as they are just the elementary abelian groups written above)??
 A: If $f(X) = X^n + g(X)$ is a monic irreducible polynomial of degree $n$ over $GF(p)$, you can represent $GF(p^n)$ as polynomials $\sum_{j=0}^{n-1} x_j \alpha^j$ where 
$x_j \in GF(p)$ and $\alpha$ is a root of $f(X)$.
The addition works coordinatewise mod $p$.
For multiplication, expansion of
$\left(\sum_{j=0}^{n-1} x_j \alpha^j\right)\left(\sum_{j=0}^{n-1} y_j \alpha^j\right)$ gives an expression of the form 
$\sum_{j=0}^{2n-2} z_j \alpha^j$, which we can then reduce mod $f(\alpha)$.
Precompute the representations of $\alpha^j$ for $n \le j \le 2n-2$
recursively: if $\alpha^j = \sum_{k=0}^{n-1} c(j,k) \alpha^k$, then 
$$\alpha^{j+1} = \sum_{k=0}^{n-2} c(j,k) \alpha^{k+1} + c(j,n-1) \alpha^n
= \sum_{k=0}^{n-2} c(j,k) \alpha^{k+1} - c(j,n-1) g(\alpha)$$
(where the coordinatewise arithmetic is done mod $p$).
Then
$$ \sum_{j=0}^{2n-2} z_j \alpha^j = \sum_{j=0}^{n-1} z_j \alpha^j +
\sum_{j=n}^{2n-2} \sum_{k=0}^{n-1} z_j c(j,k) \alpha^k \mod p$$
which amounts to a vector-matrix multiplication and addition.
EDIT: For example, take $GF(5^3)$.  A suitable polynomial is 
$f(X) = X^3 + X + 1$.  We have 
$$ \eqalign{ \alpha^3 &= 4 \alpha + 4\cr
             \alpha^4 &= 4 \alpha^2 + 4 \alpha\cr}$$
And then, say,
$$ \eqalign{(\alpha^2 + 2 \alpha + 3)(\alpha^2 + 3 \alpha + 4) &= \alpha^4 + 3 \alpha^2 + 2 \alpha + 2\cr
&= (4 \alpha^2 + 4 \alpha) + 3 \alpha^2 + 2 \alpha + 2\cr
&= 2 \alpha^2 + \alpha + 2\cr}$$
