Finite field arithmetic


In mathematics, finite field arithmetic is arithmetic in a finite field as opposed to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
While no finite field is infinite, 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 encryption algorithm, in tournament scheduling, and in the design of experiments.

Effective polynomial representation

The finite field with pn elements is denoted GF and is also called the Galois field, in honor of the founder of finite field theory, Évariste Galois. GF, where p is a prime number, is simply the ring of integers modulo p. That is, one can perform operations using the usual operation on integers, followed by reduction modulo p. For instance, in GF, 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, where addition is exclusive OR and multiplication is AND. Since the only invertible element is 1, division is the identity function.
Elements of GF may be represented as polynomials of degree strictly less than n over GF. Operations are then performed modulo R where R is an irreducible polynomial of degree n over GF, 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.
There are other representations of the elements of GF, some are isomorphic to the polynomial representation above and others which look quite different.
When the prime is 2, it is conventional to express elements of GF as binary numbers, with each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value is an element of a field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:
Polynomialx6 + x4 + x + 1
Binary
Hexadecimal

Primitive polynomials

There are many irreducible 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 is not primitive. Let be a root of this polynomial, that is,. Now, so is not a primitive element of GF and generates a multiplicative subgroup of order 51. However, is a primitive polynomial. Consider the field element . Now. As all the roots of this primitive polynomial are primitive elements, is a primitive element of GF. GF has 128 generators. 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.
In a finite field with characteristic 2, addition modulo 2, subtraction modulo 2, and XOR are identical. Thus,
Polynomial + = x7 + x4 + x3 + 1
Binary + =
Hexadecimal + =

Under regular addition of polynomials, the sum would contain a term 2x6. This term becomes 0x6 and is dropped when the answer is reduced modulo 2.
Here is a table with both the normal algebraic sum and the characteristic 2 finite field sum of a few polynomials:
In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF Galois fields, making these fields especially popular choices for applications.

Multiplication

Multiplication in a finite field is multiplication modulo an irreducible reducing polynomial used to define the finite field. The symbol "•" may be used to denote multiplication in a finite field.

Rijndael's (AES) finite field

uses the characteristic 2 finite field with 256 elements, which can also be called the Galois field GF. It employs the following reducing polynomial for multiplication:
For example, • = in Rijndael's field because
and
The latter can be demonstrated through long division :

11111101111110 100011011
^100011011
01110000011110
^100011011
0110110101110
^100011011
010101110110
^100011011
00100011010
^100011011
000000001
Multiplication in this particular finite field can also be done using a modified version of the "peasant's algorithm". Each polynomial is represented using the same binary notation as above. Eight bits is sufficient because only degrees 0 to 7 are possible in the terms of each polynomial.
This algorithm uses three variables, each holding an eight-bit representation. a and b are initialized with the multiplicands; p accumulates the product and must be initialized to 0.
At the start and end of the algorithm, and the start and end of each iteration, this invariant is true: a b + p is the product. This is obviously true when the algorithm starts. When the algorithm terminates, a or b will be zero so p will contain the product.
This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths of a, b, and p and the value 0x1b appropriately.

Multiplicative inverse

See also Itoh–Tsujii inversion algorithm.
The multiplicative inverse for an element a of a finite field can be calculated a number of different ways:

Generator based tables

When developing algorithms for Galois field computation on small Galois fields, a common performance optimization approach is to find a generator g and use the identity:
to implement multiplication as a sequence of table look ups for the logg and gy functions and an integer addition operation. This exploits the property that every finite field contains generators. In the Rijndael field example, the polynomial is one such generator. A necessary but not sufficient condition for a polynomial to be a generator is to be irreducible.
This same strategy can be used to determine the multiplicative inverse with the identity:
Here, the order of the generator,, is the number of non-zero elements of the field. In the case of GF this is. That is to say, for the Rijndael example:. So this can be performed with two look up tables and an integer subtract. Using this idea for exponentiation also derives benefit:
This requires two table look ups, an integer multiplication and an integer modulo operation.
However, in cryptographic implementations, one has to be careful with such implementations since the cache architecture of many microprocessors leads to variable timing for memory access. This can lead to implementations that are vulnerable to a timing attack.

Carryless multiply

For binary fields GF, field multiplication can be implemented using a carryless multiply such as CLMUL_instruction_set, which is good for n <= 64. A multiplication uses one carryless multiply to produce a product, another carryless multiply of a pre-computed inverse of the field polynomial to produce a quotient = ⌊ product / ⌋, a multiply of the quotient by the field polynomial, then an xor: result = product ⊕ ⌊ product /. The last 3 steps are used in the Barrett reduction step for fast computation of CRC using the X86 pclmulqdq instruction.

Composite field

When is a composite number, there will exist isomorphisms from a binary field GF to an extension field of one of its subfields, that is, GF where. Utilizing one of these isomorphisms can simplify the mathematical considerations as the degree of the extension is smaller with the trade off that the elements are now represented over a larger subfield. To reduce gate count for hardware implementations, the process may involve multiple nesting, such as mapping from GF to GF2).. There is an implementation constraint, the operations in the two representations must be compatible, so explicit use of the isomorphism is needed. More precisely, the isomorphism will be denoted by map, it is a bijection that maps an element of GF to GF, satisfying: map = map + map and map = map map, where the operations on the left side occur in GF before mapping and the operations on the right side occur in GF after mapping. The isomorphism is usually implemented with a k by k bit matrix, used to perform a matrix multiply over GF of an element of GF treated as a k by 1 matrix. Define α as a primitive element of GF, and β as a primitive element of GF. Then βj = map and αj = map−1. The values of α and β determine the mapping matrix and its inverse. Since the actual math is performed in GF, the reducing polynomial for GF is usually primitive and β = x in GF. In order to meet the compatibility constraint for addition and multiplication, a search is done to choose any primitive element α of GF that will meet the constraint. Mapping to a composite field can be generalized to map GF to a composite field such as GF, for p a prime number greater than 2, but such fields are not commonly used in practice.

Program examples

C programming example

Here is some C code which will add and multiply numbers in the characteristic 2 finite field of order 28, used for example by Rijndael algorithm or Reed–Solomon, using the Russian Peasant Multiplication algorithm:

/* Add two numbers in the GF finite field */
uint8_t gadd
/* Multiply two numbers in the GF finite field defined
* by the polynomial x^8 + x^4 + x^3 + x + 1 = 0
* using the Russian Peasant Multiplication algorithm
*
*/
uint8_t gmul

This example has cache, timing, and branch prediction side-channel leaks, and is not suitable for use in cryptography.

D programming example

This D program will multiply numbers in Rijndael's finite field and generate a PGM image:

/**
Multiply two numbers in the GF finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
  • /
ubyte gMul pure nothrow
void main
This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.