# Introduction to Finite Fields

The Galois field is especially important in digital communications. The definition of a Galois field emerges from the essential mathematical characteristics of groups, rings and fields.

# Groups, Rings and Fields

A set S={a1,a2,a3...aN} is defined as having N elements. A finite set has a limited number of elements defined by a finite N.

A group is a set S along with an operation (e.g. "+") that acts on two elements {A,B} of the set and obeys the properties of:

1. Closure: the result of A + B is always an element of S.
2. Associative: A + (B + C) = (A + B) + C
3. Identity: There is an identity element I such that A + I = A for all A
4. Inverse: There is always some element B such that A + B = I for any A

The order of a group is the number of elements in the set S.

An Abelian group or commutative group is a group whose properties also include:

1. Commutative: (A+B) = (B+A)

An additive group is an Abelian group under "+" which may not be addition in the usual sense.

A multiplicative group is an Abelian group under "×" which may not be multiplication in the usual sense.

A ring is a additive group with a second operation (e.g. "×") that obeys the properties of associative and is distributive over addition.

A commutative ring is a ring whose multiplication properties also include commutative.

A field is a commutative ring whose properties also include a multiplicative inverse (for non-zero elements).

A Galois field is a finite field under specific "+" and "×" operations.

# Notes and Examples

• Not all common operations are commutative; for example, the "×" operation defined as "matrix multiplication" is not commutative.

• The set of non-negative integers S={0,1,2,3,...} is not a group under ordinary addition as there is no inverse B to give A+B=0 without negative integers. (inverse)

• The set of all integer multiples of n is an additive group. For example, with n=3, the set S={...,-9,-6,-3,0,+3,+6,+9,...} is an additive group.

• The set of all integer multiples of n is not a multiplicative group. For example, with n=3, the set S={...,-9,-6,-3,0,+3,+6,+9,...} has no identity element under multiplication.

• The set of all integers is an commutative ring under ordinary addition and multiplication. This set is not a field as it does not include a multiplicative inverse.

• The set of real numbers is a field under ordinary addition and multiplication. This suggests that the manipulation of Galois fields will follow many of the familiar rules of arithmetic.

# Prime Field

The finite set of positive integers S={0,1,2,3,4,5,6} is not a group under ordinary addition as there will be some A+B that is not an element of S. (closure)

By specifying a finite set and operations based on modulus arithmetic the same set S may be a field, depending on the specific modulus.

• Let the set be S={0,1,2,3,...,n-1} where n=7 in the above example.

• Let the "+" operation be defined as "addition modulo n" for integer n. The finite set S={0,1,2,3,...,n-1} is an additive group. Closure is ensured since (A+B) modulo n will always be an element of S. For example, with n=7 giving the set S={0,1,2,3,4,5,6}, the addition (3+6) modulo 7 = 2 which is an element of S. The identity element I=0 for addition. The additive inverse requires that for each element A, there is an B such that (A+B) modulo 7 = 0. With A=3, for example, then (3+4) modulo 7 = 0 and the same result can be found for all elements of S.

• Let the "×" operation be defined as "multiplication modulo n" for integer n. The finite set S={0,1,2,3,...,n-1} is a multiplicative group only if n is a prime integer. As with addition, closure is ensured for any n since (A×B) modulo n will always be an element of S. The identity element I=1 for multiplication. The multiplicative inverse requires that for each non-zero element A, there is an B such that (A×B) modulo 7 = 1. With A=3, for example, then (3×5) modulo 7 = 1 and the same result can be found for all elements of S as shown in the table below. This outcome emerges only when the modulus n is a prime. As a counterexample with modulus n=6, the calculation (3×B) modulo 6 can only equal 0 or 3 whatever the value of B and will never equal I.

Using MATLAB, the modulo 7 multiplication table below shows that for each non-zero element A there is an inverse element B such that A×B=1.

```>> AxB = mod((1:6)'*(1:6),7)

AxB =

1     2     3     4     5     6
2     4     6     1     3     5
3     6     2     5     1     4
4     1     5     2     6     3
5     3     1     6     4     2
6     5     4     3     2     1
```

• In summary, the ring of integers modulo n is a finite field only if n is a prime p (or the power pm). The resulting Galois field is labeled GF(pm) and has pm elements.

Reference: Encyclopedia of Mathematics : Galois Field

# Primitive Root

The non-zero elements of the integer field {0,1,2,3,4,5,6} modulo 7 are found in the terms {an} provided that the element a is a primitive root of 7.

Specificially, let a=3 then successive powers of 3n describe all the non-zero field elements {1,3,2,6,4,5} for n= 0 to 5. For example, 33=6 in this sytem.

Using MATLAB, these terms are found as:

```>> mod(3.^(0:5), 7)

ans =

1     3     2     6     4     5
```

The terms repeat periodically for larger n. This result is not obtained for a=2; however, a=5 also generates these elements (in a different order). The only primitive roots of this field are {3,5}.

It follows that if A = 3n then the operation log3(A) = n exists as the discrete logarithm of A for this particular field. In general, the direct computation of such logarithms is not straightforward and the use of a lookup table is one possible approach.

The above finite field is written as GF(7) and is defined on modulo 7 addition ('+') and multiplication ('×') operations. The fields of specific interest in digital communications are those finite fields of the form GF(2m) in which the arithmetic operations differ from ordinary addition and multiplication. The simplest of these is GF(2).