In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
There are infinitely many different finite fields. Their number of elements is necessarily of the form pn where p is a prime number and n is a positive integer, and two finite fields of the same size are isomorphic. The prime p is called the characteristic of the field, and the positive integer n is called the dimension of the field over its prime field.
Finite fields are used in a variety of applications, including in classical coding theory in linear block codes such as BCH codes and Reed–Solomon error correction, in cryptography algorithms such as the Rijndael (AES) encryption algorithm, in tournament scheduling, and in the design of experiments.
Effective polynomial representation
The finite field with pn elements is denoted GF(pn) and is also called the Galois field of order pn, in honor of the founder of finite field theory, Évariste Galois. GF(p), where p is a prime number, is simply the ring of integers modulo p. That is, one can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulo p. For instance, in GF(5), is reduced to 2 modulo 5. Division is multiplication by the inverse modulo p, which may be computed using the extended Euclidean algorithm.
A particular case is GF(2), where addition is exclusive OR (XOR) and multiplication is AND. Since the only invertible element is 1, division is the identity function.
Elements of GF(pn) may be represented as polynomials of degree strictly less than n over GF(p). Operations are then performed modulo R where R is an irreducible polynomial of degree n over GF(p), for instance using polynomial long division. The addition of two polynomials P and Q is done as usual; multiplication may be done as follows: compute as usual, then compute the remainder modulo R. This representation in terms of polynomial coefficients is called a monomial basis (a.k.a. 'polynomial basis').
There are other representations of the elements of GF(pn); some are isomorphic to the polynomial representation above and others look quite different (for instance, using matrices). Using a normal basis may have advantages in some contexts.
When the prime is 2, it is conventional to express elements of GF(pn) as binary numbers, with the coefficient of each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "{ " and "}" ) or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value gives the coefficients of a basis of a field, thus representing an element of the field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:
Primitive polynomials
There are many irreducible polynomials (sometimes called reducing polynomials) that can be used to generate a finite field, but they do not all give rise to the same representation of the field.
A monic irreducible polynomial of degree having coefficients in the finite field GF(), where for some prime and positive integer , is called a primitive polynomial if all of its roots are primitive elements of GF(). In the polynomial representation of the finite field, this implies that is a primitive element. There is at least one irreducible polynomial for which is a primitive element. In other words, for a primitive polynomial, the powers of generate every nonzero value in the field.
In the following examples it is best not to use the polynomial representation, as the meaning of changes between the examples. The monic irreducible polynomial over GF(2) is not primitive. Let be a root of this polynomial (in the polynomial representation this would be ), that is, . Now , so is not a primitive element of GF(28) and generates a multiplicative subgroup of order 51. Consider the field element (in the polynomial representation this would be ). Now . As all the roots of this primitive polynomial are primitive elements, is a primitive element of GF(28) ( and no smaller power does). GF(28) has 128 generators (see Number of primitive elements). Having as a generator for a finite field is beneficial for many computational mathematical operations.
Addition and subtraction
Addition and subtraction are performed by adding or subtracting two of these polynomials together, and reducing the result modulo the characteristic.