Finite field
A finite field, also known as a Galois field, is an algebraic structure that consists of a finite set of elements equipped with addition and multiplication operations satisfying the field axioms, including commutativity, associativity, distributivity, the existence of additive and multiplicative identities, additive inverses, and multiplicative inverses for nonzero elements.[1] The number of elements in a finite field, referred to as its order, is always a power of a prime number, denoted as p^n where p is a prime and n is a positive integer.[1] For every prime p and positive integer n, there exists a finite field of order p^n, and any two such fields are unique up to isomorphism, meaning they have essentially the same structure regardless of how they are presented.[2] This uniqueness follows from the fact that all finite fields of the same order are isomorphic extensions of the prime field \mathbb{F}_p, the field of integers modulo p.[3] The characteristic of a finite field is the prime p, which determines the smallest number of times the multiplicative identity must be added to itself to yield zero, and it divides the order of the field.[4] Finite fields are typically constructed as quotient rings of the polynomial ring over \mathbb{F}_p by an irreducible polynomial of degree n, such as \mathbb{F}_{p^n} \cong \mathbb{F}_p / (f(x)) where f(x) is irreducible.[5] Key structural properties include the multiplicative group of nonzero elements forming a cyclic group of order p^n - 1, enabling the existence of primitive elements (generators) that can represent all nonzero elements as powers. The additive structure is a vector space over \mathbb{F}_p of dimension n.[3] Finite fields play a crucial role in numerous applications, including error-correcting codes in digital communications, cryptographic protocols such as elliptic curve cryptography and the Advanced Encryption Standard, and combinatorial designs in computer science and engineering.[6] They also underpin advanced topics in number theory, such as the proof of quadratic reciprocity via Gauss sums, and algebraic geometry over finite fields.Definition and Properties
Definition
A finite field is a field with a finite number of elements. It is an algebraic structure consisting of a set equipped with two binary operations, addition and multiplication, that satisfy the field axioms: the set forms an abelian group under addition (with an additive identity 0 and additive inverses for each element), multiplication is commutative, associative and distributive over addition, there is a multiplicative identity 1 distinct from 0, and every nonzero element has a multiplicative inverse.[2][1] Finite fields are denoted by \mathbb{F}_q or GF(q), where q is the number of elements in the field, known as its order. The order q must be a prime power, specifically q = p^n for some prime p and positive integer n \geq 1. This distinguishes finite fields from infinite fields like the rational numbers \mathbb{Q}.[1][4] The concept of finite fields originated from Évariste Galois's work on the theory of equations in 1830, where he implicitly constructed such structures while studying solvability by radicals. The term "Galois field" was coined by Leonard Eugene Dickson in his 1901 monograph Linear Groups, with an Exposition of the Galois Field Theory, which systematized their theory and introduced the notation GF(p^n).[7][1] The smallest finite field is \mathbb{F}_2, with elements \{[0](/page/0), [1](/page/1)\} and operations defined modulo 2: addition is $0 + 0 = [0](/page/0), $0 + 1 = [1](/page/1), $1 + 1 = [0](/page/0); multiplication is $0 \cdot [0](/page/0) = [0](/page/0), $0 \cdot [1](/page/1) = [0](/page/0), [1](/page/1) \cdot [1](/page/1) = [1](/page/1). The additive inverse of 0 is 0, of 1 is 1, and the multiplicative inverse of 1 is 1.[1][2]Basic properties
Every finite field F of order q has prime characteristic p and is a vector space over its prime subfield \mathbb{F}_p of dimension n, where q = p^n.[8][4] This vector space structure arises because the prime subfield \mathbb{F}_p embeds naturally into F, and scalar multiplication by elements of \mathbb{F}_p is compatible with the field operations in F.[9] The dimension n determines the size of F as a vector space, with \{1, \alpha, \alpha^2, \dots, \alpha^{n-1}\} forming a basis for some element \alpha \in F.[10] As a field, F contains no zero divisors, meaning that if ab = 0 for a, b \in F, then either a = 0 or b = 0.[11] Furthermore, every non-zero element of F has a multiplicative inverse: for any a \in F with a \neq 0, there exists b \in F such that ab = 1. This property ensures that division is possible for non-zero elements, distinguishing fields from more general rings.[12] The non-zero elements of F form the multiplicative group F^\times of order q-1. By Lagrange's theorem applied to this finite abelian group, the order of any subgroup of F^\times divides q-1.[11] This divisibility condition has implications for the structure of subgroups and the existence of elements of specific orders within F^\times.[13]Characteristic and prime subfield
In a finite field F, the characteristic is the smallest positive integer p such that p \cdot 1 = 0, where $1 denotes the multiplicative identity, and this p must be a prime number.[2] This follows from the fact that the additive order of $1 divides the order of any element in the field, and the characteristic cannot be composite without violating the field axioms.[14] The characteristic p divides the order q of the finite field F, so q = p^n for some positive integer n \geq 1.[5] This structure ensures that F is a vector space of dimension n over the field of p elements, though the focus here is on the foundational role of the characteristic in determining the field's arithmetic.[15] The prime subfield of F is the smallest subfield, generated by repeated addition and multiplication of the identity element $1.[16] Specifically, it consists of the elements \{0, 1, 2 \cdot 1, \dots, (p-1) \cdot 1\}, where addition and multiplication are performed in F, and this subfield is isomorphic to \mathbb{Z}/p\mathbb{Z}, the integers modulo p.[5] Every finite field contains exactly one such prime subfield, which serves as the unique embedding of \mathbb{F}_p within F.[17] This uniqueness arises because any subfield must contain the multiples of $1 and be closed under the field operations, leading to the intersection of all subfields being precisely this prime subfield.[18]Existence and Uniqueness
Fields of prime order
A finite field of prime order p, where p is a prime number, exists and is explicitly constructed as the quotient ring \mathbb{Z}/p\mathbb{Z}, the integers modulo p.[11] The elements of this field, denoted \mathbb{F}_p, are the residue classes {{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}}, {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}, \dots, [p-1], with the operations of addition and multiplication defined by performing the usual integer operations and then reducing modulo p.[5] Because p is prime, \mathbb{Z}/p\mathbb{Z} is an integral domain with every nonzero element possessing a multiplicative inverse, thereby forming a field.[16] In \mathbb{F}_p, the characteristic is p, and every element a satisfies a^p = a.[19] This equation holds for all a \in \mathbb{F}_p as a direct consequence of Fermat's Little Theorem applied in the integers modulo p. Consequently, the polynomial x^p - x has every element of \mathbb{F}_p as a root.[11] The polynomial x^p - x factors completely over \mathbb{F}_p as x^p - x = \prod_{a \in \mathbb{F}_p} (x - a), with all roots distinct, making \mathbb{F}_p the splitting field of x^p - x over itself.[11] This factorization arises from the Freshman's dream in characteristic p, where (x + y)^p = x^p + y^p, allowing the polynomial to be expressed as a product of linear terms corresponding to the field elements.[14] Since the order p is prime, \mathbb{F}_p admits no proper subfields: any subfield would have order dividing p, so either 1 or p, but a field cannot have exactly one element.[2] Up to isomorphism, there is a unique field of order p.[11]Uniqueness theorem
The uniqueness theorem for finite fields asserts that for every prime power q = p^n, where p is a prime and n is a positive integer, there exists exactly one field of order q up to isomorphism. To establish this, first note that in any field F of order q, every element \alpha \in F satisfies the equation \alpha^q = \alpha. This follows because the multiplicative group F^\times has order q-1, so by Lagrange's theorem, \alpha^{q-1} = 1 for \alpha \neq 0, implying \alpha^q = \alpha; the case \alpha = 0 holds trivially. Thus, F is contained in the splitting field of the polynomial x^q - x over the prime subfield \mathbb{F}_p. Moreover, x^q - x is separable over \mathbb{F}_p because its derivative q x^{q-1} - 1 = -1 (since q = 0 in characteristic p) is a nonzero constant, ensuring no multiple roots. The set of roots of x^q - x in an algebraic closure of \mathbb{F}_p consists of q distinct elements and forms a subfield, as it is closed under addition ((\alpha + \beta)^q = \alpha^q + \beta^q = \alpha + \beta), multiplication, and additive/multiplicative inverses (the latter following from the group structure). Thus, this subfield has order q and is the splitting field of x^q - x over \mathbb{F}_p, proving the existence of a field of order q.[2] Any two such splitting fields are isomorphic over \mathbb{F}_p by the uniqueness of splitting fields for separable polynomials. Therefore, any two finite fields of order q are isomorphic as extensions of \mathbb{F}_p, and hence as fields. The multiplicative groups of both fields are cyclic of order q-1, providing an additional structural confirmation, though the splitting field argument suffices for isomorphism.Constructions
Prime fields
The prime fields, also known as fields of prime order, are the simplest finite fields and serve as the foundational building blocks for more complex constructions. For a prime number p, the prime field \mathbb{F}_p is constructed as the quotient ring \mathbb{Z}/p\mathbb{Z}, consisting of the residue classes of the integers modulo p, represented by the elements \{0, 1, 2, \dots, p-1\}.[20] This ring is equipped with the standard operations of addition and multiplication inherited from the integers, performed modulo p: for a, b \in \mathbb{Z}, the sum is (a + b) \mod p and the product is (a \cdot b) \mod p.[21] Since p is prime, \mathbb{Z}/p\mathbb{Z} has no zero divisors, meaning that if ab \equiv 0 \pmod{p} for a, b \in \mathbb{Z}/p\mathbb{Z}, then either a \equiv 0 \pmod{p} or b \equiv 0 \pmod{p}. This property, combined with the existence of additive and multiplicative inverses for every nonzero element (by Bézout's identity, as \gcd(k, p) = 1 for $1 \leq k < p), ensures that \mathbb{F}_p is indeed a field.[11] The additive inverse of a is -a \mod p, and the multiplicative inverse of a nonzero a is the unique b such that ab \equiv 1 \pmod{p}.[16] A concrete example is the field \mathbb{F}_3 = \{0, 1, 2\}, where addition and multiplication are modulo 3. Here, $2 + 1 \equiv 0 \pmod{3} and $2 \cdot 2 \equiv 1 \pmod{3}, illustrating how the operations wrap around the prime modulus to form a closed algebraic structure.[22] Up to isomorphism, \mathbb{F}_p is the unique field of order p.[23]Polynomial extensions
Finite fields of order p^n for a prime p and integer n > 1 are constructed as quotient rings of the polynomial ring over the prime field. Specifically, \mathbb{F}_{p^n} is isomorphic to \mathbb{F}_p / (f(x)), where f(x) is a monic irreducible polynomial of degree n over \mathbb{F}_p.[22] This construction leverages the fact that the ideal generated by an irreducible polynomial is maximal in the polynomial ring, ensuring the quotient is a field.[22] The elements of \mathbb{F}_{p^n} are represented as residue classes of polynomials in \mathbb{F}_p with degree strictly less than n, typically written in the form a_0 + a_1 \alpha + \cdots + a_{n-1} \alpha^{n-1}, where each a_i \in \mathbb{F}_p and \alpha is the image of x in the quotient (a root of f(x)).[22] There are precisely p^n such elements, as each of the n coefficients can take p possible values.[22] Addition of two elements is performed by adding their corresponding polynomials coefficient-wise, with coefficients reduced modulo p.[24] Multiplication proceeds by first multiplying the representing polynomials in the usual manner and then reducing the result modulo f(x) to obtain a polynomial of degree less than n.[24] This reduction step uses the relation f(\alpha) = 0, allowing powers of \alpha of degree n or higher to be expressed as linear combinations of lower powers via the coefficients of f(x).[24] For example, if f(x) = x^n + c_{n-1} x^{n-1} + \cdots + c_0, then \alpha^n = -c_{n-1} \alpha^{n-1} - \cdots - c_0.[22] The isomorphism \mathbb{F}_{p^n} \cong \mathbb{F}_p / (f(x)) holds for any choice of monic irreducible f(x) of degree n, and all such quotients are isomorphic to each other as fields.[22] Thus, the structure of \mathbb{F}_{p^n} is independent of the specific irreducible polynomial selected for the construction.[22]Small finite field examples
One of the smallest non-prime finite fields is \mathbb{F}_4, constructed as the quotient \mathbb{F}_2/(p(x)) where p(x) = x^2 + x + 1 is the unique monic irreducible polynomial of degree 2 over \mathbb{F}_2.[25] Let \omega denote a root of p(x), satisfying \omega^2 = \omega + 1. The elements of \mathbb{F}_4 are then \{0, [1](/page/1), \omega, \omega + 1\}, forming a 2-dimensional vector space over \mathbb{F}_2 with basis \{[1](/page/1), \omega\}.[26] Addition in \mathbb{F}_4 is componentwise modulo 2, while multiplication uses the relation \omega^2 = \omega + [1](/page/1) and reduces higher powers accordingly. The following tables illustrate these operations: Addition table:| + | 0 | 1 | \omega | \omega + [1](/page/1) |
|---|---|---|---|---|
| 0 | 0 | 1 | \omega | \omega + [1](/page/1) |
| 1 | 1 | 0 | \omega + [1](/page/1) | \omega |
| \omega | \omega | \omega + [1](/page/1) | 0 | 1 |
| \omega + [1](/page/1) | \omega + [1](/page/1) | \omega | 1 | 0 |
| \cdot | 0 | 1 | \omega | \omega + 1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | \omega | \omega + 1 |
| \omega | 0 | \omega | \omega + 1 | 1 |
| \omega + 1 | 0 | \omega + 1 | 1 | \omega |