GF(2)

Last updated November 26, 2023

$GF(2)$ (also denoted $\mathbb {F} _{2}$ , $Z /2 Z$ or $\mathbb {Z} /2\mathbb {Z}$ ) is the finite field with two elements^[1] (GF is the initialism of Galois field, another name for finite fields). Notations $Z 2$ and $\mathbb {Z} _{2}$ may be encountered although they can be confused with the notation of 2-adic integers.

Definition

GF(2) is the unique field with two elements with its additive and multiplicative identities respectively denoted 0 and 1.

Its addition is defined as the usual addition of integers but modulo 2 and corresponds to the table below:

+	0	1
0	0	1
1	1	0

If the elements of GF(2) are seen as boolean values, then the addition is the same as that of the logical XOR operation. Since each element equals its opposite, subtraction is thus the same operation as addition.

The multiplication of GF(2) is again the usual multiplication modulo 2 (see the table below), and on boolean variables corresponds to the logical AND operation.

×	0	1
0	0	0
1	0	1

GF(2) can be identified with the field of the integers modulo 2, that is, the quotient ring of the ring of integers Z by the ideal 2Z of all even numbers: GF(2) = Z/2Z.

Properties

Because GF(2) is a field, many of the familiar properties of number systems such as the rational numbers and real numbers are retained:

addition has an identity element (0) and an inverse for every element;
multiplication has an identity element (1) and an inverse for every element but 0;
addition and multiplication are commutative and associative;
multiplication is distributive over addition.

Properties that are not familiar from the real numbers include:

every element x of GF(2) satisfies $x + x = 0$ and therefore $- x = x$ ; this means that the characteristic of GF(2) is 2;
every element x of GF(2) satisfies $x 2 = x$ (i.e. is idempotent with respect to multiplication); this is an instance of Fermat's little theorem. GF(2) is the only field with this property (Proof: if $x 2 = x$ , then either $x = 0$ or $x \neq 0$ . In the latter case, x must have a multiplicative inverse, in which case dividing both sides by x gives $x = 1$ . All larger fields contain elements other than 0 and 1, and those elements cannot satisfy this property).

Applications

Because of the algebraic properties above, many familiar and powerful tools of mathematics work in GF(2) just as well as other fields. For example, matrix operations, including matrix inversion, can be applied to matrices with elements in GF(2) (see matrix ring).

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(2) in a natural fashion, by defining 0v = 0 and 1v = v for all v in V. This vector space will have a basis, implying that the number of elements of V must be a power of 2 (or infinite).

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(2). The addition of this vector space is the bitwise operation called XOR (exclusive or). 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(2ⁿ), 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(2) modulo a irreducible polynomial (as for instance for the field GF(2⁸) in the description of the Advanced Encryption Standard cipher).

Vector spaces and polynomial rings over GF(2) are widely used in coding theory, and in particular in error correcting codes and modern cryptography. For example, many common error correcting codes (such as BCH codes) are linear codes over GF(2) (codes defined from vector spaces over GF(2)), or polynomial codes (codes defined as quotients of polynomial rings over GF(2)).

Algebraic closure

Like any field, GF(2) has an algebraic closure. This is a field F which contains GF(2) as a subfield, which is algebraic over GF(2) (i.e. every element of F is a root of a polynomial with coefficients in GF(2)), and which is algebraically closed (any non-constant polynomial with coefficients in F has a root in F). The field F is uniquely determined by these properties, up to a field automorphism (i.e. essentially up to the notation of its elements).

F is countable and contains a single copy of each of the finite fields GF(2ⁿ); the copy of GF(2ⁿ) is contained in the copy of GF(2^m) if and only if n divides m. The field F is countable and is the union of all these finite fields.

Conway realized that F can be identified with the ordinal number $\omega ^{\omega ^{\omega }}$ , where the addition and multiplication operations are defined in a natural manner by transfinite induction (these operations are however different from the standard addition and multiplication of ordinal numbers).^[2] The addition in this field is simple to perform and is akin to Nim-addition; Lenstra has shown that the multiplication can also be performed efficiently.^[3]

Related Research Articles

In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel.

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers do. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics.

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

In mathematics, particularly in algebra, a field extension is a pair of fields $such that the operations of K are those of L restricted to K . In this case, L is an extension field of K and K is a subfield of L . For example, under the usual notions of addition and multiplication, the complex numbers are an extension field of the real numbers; the real numbers are a subfield of the complex numbers.$

<span class="mw-page-title-main">Isomorphism</span> In mathematics, invertible homomorphism

In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".

In mathematics, a group is a set with an operation that satisfies the following constraints: the operation is associative, has an identity element, and every element of the set has an inverse element.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. Informally, a ring is a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers. Ring elements may be numbers such as integers or complex numbers, but they may also be non-numerical objects such as polynomials, square matrices, functions, and power series.

In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not specific to commutative rings. This distinction results from the high number of fundamental properties of commutative rings that do not extend to noncommutative rings.

In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space in linear algebra. It is a specific example of a quotient, as viewed from the general setting of universal algebra. Starting with a ring $R$ and a two-sided ideal $I$ in $R$ , a new ring, the quotient ring $R / I$ , is constructed, whose elements are the cosets of $I$ in $R$ subject to special $+$ and $\cdot$ operations.

In mathematics, an algebra over a field is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition and scalar multiplication by elements of a field and satisfying the axioms implied by "vector space" and "bilinear".

In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subset such that every element of the group can be uniquely expressed as an integer combination of finitely many basis elements. For instance the two-dimensional integer lattice forms a free abelian group, with coordinatewise addition as its operation, and with the two points (1,0) and (0,1) as its basis. Free abelian groups have properties which make them similar to vector spaces, and may equivalently be called free $-modules,$ the free modules over the integers. Lattice theory studies free abelian subgroups of real vector spaces. In algebraic topology, free abelian groups are used to define chain groups, and in algebraic geometry they are used to define divisors.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

In algebra, a unit or invertible element of a ring is an invertible element for the multiplication of the ring. That is, an element $u$ of a ring $R$ is a unit if there exists $v$ in $R$ such that

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.

In mathematics, a square is the result of multiplying a number by itself. The verb "to square" is used to denote this operation. Squaring is the same as raising to the power 2, and is denoted by a superscript 2; for instance, the square of 3 may be written as 3², which is the number 9. In some cases when superscripts are not available, as for instance in programming languages or plain text files, the notations x^2 (caret) or x**2 may be used in place of x². The adjective which corresponds to squaring is quadratic.

In mathematics, the characteristic of a ring $R$ , often denoted $char(R)$ , is defined to be the smallest positive number of copies of the ring's multiplicative identity ( $1$ ) that will sum to the additive identity ( $0$ ). If no such number exists, the ring is said to have characteristic zero.

In mathematics, specifically in group theory, an elementary abelian group is an abelian group in which all elements other than the identity have the same order. This common order must be a prime number, and the elementary abelian groups in which the common order is p are a particular kind of p-group. A group for which p = 2 is sometimes called a Boolean group.

In mathematics, an algebraic number field is an extension field $of the field of rational numbers such that the field extension has finite degree . Thus is a field that contains and has finite dimension when considered as a vector space over .$

References

↑ Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields . Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069.
↑ Conway, John H. (2000). On Numbers and Games (2nd ed.). Wellesley, Mass. p. 61. ISBN 978-1-56881-127-7.{{cite book}}: CS1 maint: location missing publisher (link)
↑ Lenstra, Hendrik (1977). "On the Algebraic Closure of Two" (PDF). Indagationes Mathematicae (Proceedings). 80 (5).

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields . Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069.

[2] Conway, John H. (2000). On Numbers and Games (2nd ed.). Wellesley, Mass. p. 61. ISBN 978-1-56881-127-7.{{cite book}}: CS1 maint: location missing publisher (link)

[3] Lenstra, Hendrik (1977). "On the Algebraic Closure of Two" (PDF). Indagationes Mathematicae (Proceedings). 80 (5).

[1]

[2]

[3]