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 |
|---|---|
ADDITION = symmetric matrices |
Saves the addition table of the field |
MULTIPLICATION = symmetric matrices |
Saves the field’s multiplication table |
PRIMITIVE = variates |
Saves the primitive irreducible polynomial |
ERROR = scalars |
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 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.
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.
See also
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
GALOIS [METHOD=minimal] 8; ADDITION=Add8; MULT=Mult8
PRINT [SERIAL=yes] Add8[]; FIELD=3; DECIMALS=0
& Mult8[]; FIELD=3; DECIMALS=0