GF(2)


GF is the Galois field of two elements. It is the smallest field.

Definition

The two elements are nearly always called 0 and 1, being the additive and multiplicative identities, respectively.
The field's addition operation is given by the table below, which corresponds to the logical XOR operation.
The field's multiplication operation corresponds to the logical AND operation.
One may also define GF as the quotient ring of the ring of integers Z by the ideal 2Z of all even numbers: GF = Z/2Z.

Properties

Because GF is a field, many of the familiar properties of number systems such as the rational numbers and real numbers are retained:
Properties that are not familiar from the real numbers include:
Because of the algebraic properties above, many familiar and powerful tools of mathematics work in GF just as well as other fields. For example, matrix operations, including matrix inversion, can be applied to matrices with elements in GF.
Any group V with the property v + v = 0 for every v in V is necessarily abelian and can be turned into a vector space over GF in a natural fashion, by defining 0v = 0 and 1v = v. This vector space will have a basis, implying that the number of elements of V must be a power of 2.
In modern computers, data are represented with bit strings of a fixed length, called machine words. These are endowed with the structure of a vector space over GF. The addition of this vector space is the bitwise operation called XOR. The bitwise AND is another operation on this vector space, which makes it a Boolean algebra, a structure that underlies all computer science. These spaces can also be augmented with a multiplication operation that makes them into a field GF, but the multiplication operation cannot be a bitwise operation. When n is itself a power of two, the multiplication operation can be nim-multiplication; alternatively, for any n, one can use multiplication of polynomials over GF modulo a primitive polynomial.