Computing in ${\rm GF}\,(q)$

This paper gives an elementary deterministic algorithm for completely factoring any polynomial over ${\text{GF}}(q),q = {p^d}$, criteria for the identification of three types of primitive polynomials, an exponential representation for ${\text{GF}}(q)$ which permits direct rational calculations in ${\text{GF}}(q)$ as opposed to modular arithmetic over ${\text{GF}}[p,x]$, and a matrix representation for $\overline {{\text{GF}}} (p)$ which admits computer computations. The third type of primitive polynomial examined permits the given representation of ${\text{GF}}(q)$ to display a primitive normal basis over ${\text{GF}}(p)$. The techniques developed require only the usual addition and multiplication of square matrices over ${\text{GF}}(p)$. Partial tables from computer programs based on certain of these results will appear in later papers.