  For any finite Galois field extension $\mathsf{K}/\mathsf{F}$, with Galois
group $G = \mathrm{Gal}(\mathsf{K}/\mathsf{F})$, there exists an element
$\alpha \in \mathsf{K}$ whose orbit $G\cdot\alpha$ forms an $\mathsf{F}$-basis
of $\mathsf{K}$. Such a $\alpha$ is called a normal element and $G\cdot\alpha$
is a normal basis. We introduce a probabilistic algorithm for testing whether a
given $\alpha \in \mathsf{K}$ is normal, when $G$ is either a finite abelian or
a metacyclic group. The algorithm is based on the fact that deciding whether
$\alpha$ is normal can be reduced to deciding whether $\sum_{g \in G}
g(\alpha)g \in \mathsf{K}[G]$ is invertible; it requires a slightly
subquadratic number of operations. Once we know that $\alpha$ is normal, we
show how to perform conversions between the power basis of
$\mathsf{K}/\mathsf{F}$ and the normal basis with the same asymptotic cost.
