The Uses of Finite Fields

The paper is tutorial in nature, although some of the results are new. It reviews some of the elementary facts about the structure and construction of finite fields and hypothesizes a computer whose fundamental instruction set consists of the Galois field operations. Each total function is shown to be defined by a unique polynomial and this normal representation is also the minimal polynomial representation. A method is presented, due to Newton, for constructing the coefficients of the defining polynomial using divided differences. It is shown that under certain circumstances a total function may be more efficiently evaluated by a rational form with non-zero denominator. Finally a rational form representation is shown to be a natural representation for each partial function. In the light of these considerations the process of producing code for the hypothetical machine is almost entirely automated.