Forms addition and multiplication tables for a Galois finite field (I. Wakeling & R.W. Payne).
||Whether to choose the primitive polynomial to generate the Galois field with the least number of higher terms or whether to make a random choice (
||Order of the required Galois field|
||Saves the addition table of the field|
||Saves the field’s multiplication table|
||Saves the primitive irreducible polynomial|
||Returns 0 or 1 according to whether or not the tables have been formed successfully|
GALOIS generates the addition and multiplication tables for a Galois finite field. The order of the field, pn, is specified by the
ORDER parameter and must be a power of a prime number p. If n>1, the elements of the field can be considered as polynomials of degree (n-1) whose coefficients can be any residue modulo p. The multiplication and addition tables can be saved using the
MULTIPLICATION parameters. These return pointers to n symmetric matrices containing the coefficients for the polynomials. (The first element of the pointer is the constant term, the last element is the xn–1 term). In order to construct the field, a primitive polynomial of degree n is needed (see the Method section for more details). The coefficients of this polynomial can be saved using the
PRIMITIVE parameter. Again the first element corresponds to the constant term and the last element to the highest power. The final parameter,
ERROR, can be set to a scalar which will return the value one if it has not been possible to form the tables, for example, because
ORDER is not a valid prime power. If the tables have been formed successfully,
ERROR is set to zero.
PRIMEPOWER is used to decompose
ORDER into prime powers (pn). For prime values of
ORDER, i.e. when the exponent n is one, the finite field is equivalent to the operations of addition and multiplication modulo p; in which case the solution is trivial. Otherwise, when
ORDER is a prime power (n>1 and p prime), a solution is found by representing the elements of the field by ordered n-tuples of integers modulo p, For example the order 4 field has elements (00, 01, 10, 11) which may alternatively be thought of as polynomials e.g. (10) as x+0 and (11) as x+1. The method first generates a list of these elements and then forms all possible pairwise products between the polynomials (reducing by modulo p where necessary). All polynomials formed in this way may therefore be factorized over an order p field. By elimination, a list of polynomials of degree n that may not be factorized is created. These are said to be irreducible and have been tabulated in the mathematical literature (Williams 1996, Section 2.8). The standard method of construction of the field is to select one of these irreducible polynomials f(x), which is also primitive; meaning that the non-zero elements of the field form a cyclic group under multiplication. See Williams (1996) Section 2.9 for a table of primitive polynomials.
GALOIS either chooses f(x) randomly from the set of all possible primitive polynomials (
METHOD=random), or chooses the polynomial having the minimal number of higher terms (
METHOD=minimal). The final choice of f(x) is made available to the user through the parameter
PRIMITIVE. For further information on finite fields in a statistical context the reader should consult Street & Street (1987).
Street, A.P. & Street, D.J. (1987). The Combinatorics of Experimental Design. Clarenden Press, Oxford.
Williams, H. (1996). Number theory and finite fields. In: The CRC Handbook of Combinatorial Designs, (ed. C.J. Colburn & J.H. Dinitz), 615-644. CRC Press, Boca Raton, Florida.
CAPTION 'GALOIS example',\ 'Addition and multiplication tables for the field of order 8.';\ STYLE=meta,plain GALOIS [METHOD=minimal] 8; ADDITION=Add8; MULT=Mult8 PRINT [SERIAL=yes] Add8; FIELD=3; DECIMALS=0 & Mult8; FIELD=3; DECIMALS=0