GF(2)
GF(2), also known as the Galois field of order 2, is the finite field consisting of the two elements {0, 1}, where addition and multiplication are performed using arithmetic modulo 2.[1] It is the unique (up to isomorphism) field of prime order 2 and serves as the prime field of characteristic 2.[1] As the smallest non-trivial finite field, GF(2) underpins much of abstract algebra and computer science, providing a foundational structure for binary operations.[2] The operations in GF(2) are straightforward and correspond directly to bitwise operations in computing. Addition is equivalent to the exclusive OR (XOR) function, with the following table: Multiplication aligns with the logical AND operation, as shown: These operations satisfy all field axioms, including commutativity, associativity, distributivity, and the existence of identities (0 for addition, 1 for multiplication) and inverses (each element is its own additive inverse, and 1 is the multiplicative inverse of itself).[3] GF(2) is isomorphic to the ring of integers modulo 2, ℤ/2ℤ, and its additive group is cyclic of order 2 while the multiplicative group consists solely of {1}.[3] GF(2) plays a central role in constructing larger finite fields of the form GF(2^n) for n > 1, which are built as quotient rings of polynomials over GF(2) modulo an irreducible polynomial of degree n.[2] These extensions are vital in applications such as error-correcting codes—for instance, binary Hamming codes operate as linear codes over GF(2), enabling single-error correction in data transmission.[4] In cryptography, GF(2) forms the basis for fields like GF(2^8) used in the Advanced Encryption Standard (AES) for efficient bitwise computations during encryption processes.[2] Additionally, vector spaces over GF(2) model binary linear algebra, with applications in combinatorial optimization, network coding, and digital signal processing.[5]Fundamentals
Definition
GF(2), also denoted \mathbb{F}_2, is the unique finite field of order 2, consisting of the elements \{[0](/page/0), [1](/page/1)\} with addition and multiplication performed modulo 2.[6] It serves as the prime field of characteristic 2, isomorphic to the quotient ring \mathbb{Z}/2\mathbb{Z}, where the integers are reduced modulo the prime 2.[6] Alternatively, GF(2) can be constructed as the splitting field of the polynomial x^2 - x over the prime field of characteristic 2, as both roots 0 and 1 lie within the field and satisfy t^2 = t for every element t \in \mathbb{F}_2.[6] To verify that GF(2) is a field, it must satisfy the field axioms: it forms a commutative ring with unity under addition and multiplication, every non-zero element is invertible, and the distributive law holds. The additive group is cyclic of order 2, with 0 as the identity and each element its own inverse (since $1 + 1 = [0](/page/0)). The multiplicative structure has 1 as the unity, and the non-zero element 1 is its own inverse ([1](/page/1) \cdot [1](/page/1) = [1](/page/1)). Commutativity, associativity, and distributivity follow directly from the corresponding properties in \mathbb{Z}/2\mathbb{Z}, verifiable by direct inspection of the two elements.[3][7] GF(2) is unique up to isomorphism: any field with exactly two elements must be isomorphic to it, as all finite fields of the same order p^n (here p=2, n=1) are isomorphic, determined by the existence and uniqueness of the splitting field of x^{p^n} - x over the prime field \mathbb{F}_p.[6][8]Arithmetic Operations
In GF(2), the field with two elements denoted as {0, 1}, addition is defined as the operation modulo 2, which corresponds to the bitwise exclusive OR (XOR) for binary values. Specifically, the addition table yields: $0 + 0 = 0, $0 + 1 = 1, $1 + 0 = 1, and $1 + 1 = 0.[1][3] Subtraction in GF(2) coincides with addition due to the field's characteristic of 2, where each element is its own additive inverse, so x - y = x + y for all x, y \in \{0, 1\}.[9][10] Multiplication in GF(2) follows the standard binary rules, equivalent to the logical AND operation: $0 \times 0 = 0, $0 \times 1 = 0, $1 \times 0 = 0, and $1 \times 1 = 1.[1][3] The additive identity is 0, satisfying x + 0 = x for all x \in GF(2), while the multiplicative identity is 1, with x \times 1 = x. Additionally, the additive inverse of any element x is x itself, as x + x = [0](/page/0).[1][10] For division, since the only non-zero element is 1 and $1^2 = 1, the multiplicative inverse of 1 is 1 itself, making division by a non-zero element y equivalent to multiplication by y, so x / y = x \times y for y \neq [0](/page/0). Division by 0 is undefined, consistent with field axioms.[9]Properties
Characteristic and Structure
The field GF(2) has characteristic 2, defined as the smallest positive integer k such that k \cdot 1 = 0, where 1 denotes the multiplicative identity; this immediately implies that $1 + 1 = 0.[11][12] As the prime field of characteristic 2, GF(2) is the smallest field with this property, consisting of the elements {0, 1} and generated additively and multiplicatively by 1, with no proper subfields.[13][12] The multiplicative group of nonzero elements, denoted GF(2)^\times, is trivial, comprising solely the element 1 and thus having order 1; this follows from the field's order being 2, making the group cyclic of order $2 - 1 = [1](/page/1).[11][13] As an integral domain (with no zero divisors, since every nonzero element has a multiplicative inverse), GF(2) exhibits further structural simplicity: every element is idempotent under multiplication, satisfying x^2 = x for x \in \{0, [1](/page/1)\}, a property characteristic of Boolean rings.[14][15] This idempotence and the field's characteristic 2 align GF(2) closely with Boolean algebra, where the addition operation corresponds to the logical XOR gate and multiplication to the AND gate, enabling direct isomorphism between the field's structure and two-element Boolean lattices in computational contexts.[11][14]Vector Spaces over GF(2)
A vector space over GF(2), the finite field with two elements {0, 1}, consists of vectors whose components are elements of GF(2), with scalar multiplication and vector addition defined using the field's arithmetic operations modulo 2.[16] This binary nature means that any vector can be represented as a string of 0s and 1s, where addition corresponds to bitwise XOR and scalar multiplication by 1 leaves the vector unchanged while multiplication by 0 yields the zero vector.[17] Due to the field's characteristic 2, as discussed in prior sections on field properties, addition is idempotent (adding a vector to itself results in zero), which simplifies many structural aspects compared to vector spaces over fields of characteristic not equal to 2.[16] The dimension of a vector space over GF(2) is the cardinality of a basis, and for an n-dimensional space, the total number of vectors is $2^n.[17] A canonical example is \mathbb{F}_2^n, the set of all n-tuples with entries in GF(2), which forms an n-dimensional vector space under componentwise addition and scalar multiplication.[16] For instance, in \mathbb{F}_2^2, a basis is \{(1,0), (0,1)\}, and the four elements are (0,0), (1,0), (0,1), and (1,1), interpretable as 2-bit binary strings.[17] Every vector in this space is uniquely expressed as a linear combination of basis vectors with coefficients in {0,1}, reflecting the field's binary structure.[16] Linear independence in a vector space over GF(2) requires that no vector in the set is equal to the sum (via XOR) of the others.[17] A set of vectors \{v_1, \dots, v_k\} is linearly dependent if there exist coefficients c_i \in \mathbb{F}_2, not all zero, such that \sum c_i v_i = 0, where the sum is modulo 2; otherwise, the set is independent.[16] The maximum size of a linearly independent set equals the dimension, and bases provide minimal spanning sets for the space.[17] The standard inner product on \mathbb{F}_2^n is defined as \langle x, y \rangle = \sum_{i=1}^n x_i y_i \pmod{2} for vectors x = (x_1, \dots, x_n) and y = (y_1, \dots, y_n).[17] Two vectors are orthogonal if their inner product is 0, which plays a key role in concepts like orthogonal complements and self-orthogonal subspaces over GF(2).[16] This bilinear form is symmetric due to the commutativity of multiplication in GF(2). In characteristic 2, it satisfies \langle x, x \rangle = \sum_{i=1}^n x_i \pmod{2}, the parity of the Hamming weight of x, distinguishing it from positive definite inner products over the reals.[17]Representations
As a Quotient Ring
The field GF(2) is isomorphic to the quotient ring \mathbb{Z}/2\mathbb{Z}, obtained by factoring out the principal ideal (2) generated by the prime number 2 from the ring of integers \mathbb{Z}.[18] This construction yields a field because the ideal (2) is maximal (equivalently, prime) in the principal ideal domain \mathbb{Z}, ensuring that the quotient has no zero divisors and every nonzero element is invertible.[18] The elements of this quotient ring are the residue classes {{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} = 2\mathbb{Z} and {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} = 1 + 2\mathbb{Z}, which are canonically identified with the set \{0, 1\}, where addition and multiplication are defined componentwise modulo 2.[18] As an integral domain of characteristic 2, GF(2) is already a field, so its field of fractions coincides with itself; there are no proper fractions beyond the elements already present, reflecting the finite nature of the structure.[19] This self-contained property underscores its role as the prime field of characteristic 2.[19] GF(2) can also be realized as a quotient of the polynomial ring \mathbb{Z} by the ideal generated by 2 and a suitable polynomial that enforces the field's structure, such as (2, x), which collapses to \mathbb{Z}/2\mathbb{Z} by setting x \equiv 0.[20] More generally, finite fields arise as quotients of polynomial rings over prime fields, but for GF(2) as the base case, the integer quotient provides the foundational construction.[20] The arithmetic underlying GF(2) was discovered implicitly through 19th-century developments in modular arithmetic, notably in Carl Friedrich Gauss's Disquisitiones Arithmeticae (1801), where congruences modulo primes laid the groundwork for finite structures, though the explicit field-theoretic interpretation emerged later with Évariste Galois's work around 1830.[21]Explicit Operation Tables
The operations in GF(2), the finite field with two elements {0, 1}, are defined modulo 2, making addition equivalent to the exclusive-or (XOR) operation and multiplication equivalent to the logical AND operation.[22] The addition table for GF(2) is as follows:| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |