Computing in $\textrm {GF} (q)$

Abstract:

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.