1. Home
2. GALOIS procedure

# GALOIS procedure

Forms addition and multiplication tables for a Galois finite field (I. Wakeling & R.W. Payne).

### Option

`METHOD` = string token 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 (`minimal`, `random`); default `rand`

### Parameters

`ORDER` = scalars 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

### Description

Procedure `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 `ADDITION` and `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 xn1 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.

Option: `METHOD`.

Parameters: `ORDER`, `ADDITION`, `MULTIPLICATION`, `PRIMITIVE`, `ERROR`.

### Method

Procedure `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).

### References

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.

Procedures: `AGLATIN`, `FHADAMARDMATRIX`, `PRIMEPOWER`.

Commands for: Calculations and manipulation, Design of experiments.

### Example

```CAPTION 'GALOIS example',\
'Addition and multiplication tables for the field of order 8.';\
STYLE=meta,plain