Movatterモバイル変換

Jump to content

Finite field

From Wikipedia, the free encyclopedia

Algebraic structure

"Galois field" redirects here. For Galois field extensions, seeGalois extension.

This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(February 2015) (Learn how and when to remove this message)

Algebraic structures
Group-like Group Semigroup / Monoid Rack and quandle Quasigroup and loop Abelian group Magma Lie group Group theory
Ring-like Ring Rng Semiring Near-ring Commutative ring Domain Integral domain Field Division ring Lie ring Ring theory
Lattice-like Lattice Semilattice Complemented lattice Total order Heyting algebra Boolean algebra Map of lattices Lattice theory
Module-like Module Group with operators Vector space Linear algebra
Algebra-like Algebra Associative Non-associative Composition algebra Lie algebra Graded Bialgebra Hopf algebra
v t e

Inmathematics, afinite field orGalois field (so-named in honor ofÉvariste Galois) is afield that contains a finite number ofelements. As with any field, a finite field is aset 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 theintegers mod $p {\displaystyle p}$ when $p {\displaystyle p}$ is aprime number.

Theorder of a finite field is its number of elements, which is either a prime number or aprime power. For every prime number $p {\displaystyle p}$ and every positive integer $k {\displaystyle k}$ there are fields of order $p^{k}$ . All finite fields of a given order areisomorphic.

Finite fields are fundamental in a number of areas of mathematics andcomputer science, includingnumber theory,algebraic geometry,Galois theory,finite geometry,cryptography andcoding theory.

Properties

A finite field is a finite set that is afield; this means that multiplication, addition, subtraction and division (excluding division by zero) are defined and satisfy the rules of arithmetic known as thefield axioms.

The number of elements of a finite field is called itsorder or, sometimes, itssize. A finite field of order $q {\displaystyle q}$ exists if and only if $q {\displaystyle q}$ is aprime power $p^{k}$ (where $p {\displaystyle p}$ is a prime number and $k {\displaystyle k}$ is a positive integer). In a field of order $p^{k}$ , adding $p {\displaystyle p}$ copies of any element always results in zero; that is, thecharacteristic of the field is $p {\displaystyle p}$ .

For $q=p^{k}$ , all fields of order $q {\displaystyle q}$ areisomorphic (see§ Existence and uniqueness below).^[1] Moreover, a field cannot contain two different finitesubfields with the same order. One may therefore identify all finite fields with the same order, and they are unambiguously denoted $\mathbb {F} _{q}$ , $\mathbf {F} _{q}$ or $\mathrm {GF} (q)$ , where the letters GF stand for "Galois field".^[2]

In a finite field of order $q {\displaystyle q}$ , thepolynomial $X^{q}-X$ has all $q {\displaystyle q}$ elements of the finite field asroots. The non-zero elements of a finite field form amultiplicative group. This group iscyclic, so all non-zero elements can be expressed as powers of a single element called aprimitive element of the field. (In general there will be several primitive elements for a given field.)

The simplest examples of finite fields are the fields of prime order: for eachprime number $p {\displaystyle p}$ , theprime field of order $p {\displaystyle p}$ may be constructed as theintegers modulo $p {\displaystyle p}$ , $\mathbb {Z} /p\mathbb {Z}$ .

The elements of the prime field of order $p {\displaystyle p}$ may be represented by integers in the range $0,\ldots ,p-1$ . The sum, the difference and the product are theremainder of the division by $p {\displaystyle p}$ of the result of the corresponding integer operation. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm (seeExtended Euclidean algorithm § Modular integers).

Let $F {\displaystyle F}$ be a finite field. For any element $x {\displaystyle x}$ in $F {\displaystyle F}$ and anyinteger $n {\displaystyle n}$ , denote by $n\cdot x$ the sum of $n {\displaystyle n}$ copies of $x {\displaystyle x}$ . The least positive $n {\displaystyle n}$ such that $n\cdot 1=0$ is the characteristic $p {\displaystyle p}$ of the field. This allows defining a multiplication $(k,x)\mapsto k\cdot x$ of an element $k {\displaystyle k}$ of $\mathrm {GF} (p)$ by an element $x {\displaystyle x}$ of $F {\displaystyle F}$ by choosing an integer representative for $k {\displaystyle k}$ . This multiplication makes $F {\displaystyle F}$ into a $\mathrm {GF} (p)$ -vector space. It follows that the number of elements of $F {\displaystyle F}$ is $p^{n}$ for some integer $n {\displaystyle n}$ .

Theidentity $(x+y)^{p}=x^{p}+y^{p}$ (sometimes called thefreshman's dream) is true in a field of characteristic $p {\displaystyle p}$ . This follows from thebinomial theorem, as eachbinomial coefficient of the expansion of $(x+y)^{p}$ , except the first and the last, is a multiple of $p {\displaystyle p}$ .

ByFermat's little theorem, if $p {\displaystyle p}$ is a prime number and $x {\displaystyle x}$ is in the field $\mathrm {GF} (p)$ then $x^{p}=x$ . This implies the equality $X^{p}-X=\prod _{a\in \mathrm {GF} (p)}(X-a)$ for polynomials over $\mathrm {GF} (p)$ . More generally, every element in $\mathrm {GF} (p^{n})$ satisfies the polynomial equation $x^{p^{n}}-x=0$ .

Any finitefield extension of a finite field isseparable and simple. That is, if $E {\displaystyle E}$ is a finite field and $F {\displaystyle F}$ is a subfield of $E {\displaystyle E}$ , then $E {\displaystyle E}$ is obtained from $F {\displaystyle F}$ by adjoining a single element whoseminimal polynomial isseparable. To use a piece of jargon, finite fields areperfect.

A more general algebraic structure that satisfies all the other axioms of a field, but whose multiplication is not required to be commutative, is called adivision ring (or sometimesskew field). ByWedderburn's little theorem, any finite division ring is commutative, and hence is a finite field.

Existence and uniqueness

Let $q=p^{n}$ be aprime power, and $F {\displaystyle F}$ be thesplitting field of the polynomial $P=X^{q}-X$ over the prime field $\mathrm {GF} (p)$ . This means that $F {\displaystyle F}$ is a finite field of lowest order, in which $P {\displaystyle P}$ has $q {\displaystyle q}$ distinct roots (theformal derivative of $P {\displaystyle P}$ is $P'=-1$ , implying that $\mathrm {gcd} (P,P')=1$ , which in general implies that the splitting field is aseparable extension of the original). Theabove identity shows that the sum and the product of two roots of $P {\displaystyle P}$ are roots of $P {\displaystyle P}$ , as well as the multiplicative inverse of a root of $P {\displaystyle P}$ . In other words, the roots of $P {\displaystyle P}$ form a field of order $q {\displaystyle q}$ , which is equal to $F {\displaystyle F}$ by the minimality of the splitting field.

The uniqueness up to isomorphism of splitting fields implies thus that all fields of order $q {\displaystyle q}$ are isomorphic. Also, if a field $F {\displaystyle F}$ has a field of order $q=p^{k}$ as a subfield, its elements are the $q {\displaystyle q}$ roots of $X^{q}-X$ , and $F {\displaystyle F}$ cannot contain another subfield of order $q {\displaystyle q}$ .

In summary, we have the following classification theorem first proved in 1893 byE. H. Moore:^[1]

The order of a finite field is a prime power. For every prime power $q {\displaystyle q}$ there are fields of order $q {\displaystyle q}$ , and they are all isomorphic. In these fields, every element satisfies $x^{q}=x,$ and the polynomial $X^{q}-X$ factors as $X^{q}-X=\prod _{a\in F}(X-a).$

It follows that $\mathrm {GF} (p^{n})$ contains a subfield isomorphic to $\mathrm {GF} (p^{m})$ if and only if $m {\displaystyle m}$ is a divisor of $n {\displaystyle n}$ ; in that case, this subfield is unique. In fact, the polynomial $X^{p^{m}}-X$ divides $X^{p^{n}}-X$ if and only if $m {\displaystyle m}$ is a divisor of $n {\displaystyle n}$ .

Explicit construction

Non-prime fields

Given a prime power $q=p^{n}$ with $p {\displaystyle p}$ prime and $n>1$ , the field $\mathrm {GF} (q)$ may be explicitly constructed in the following way. One first chooses anirreducible polynomial $P {\displaystyle P}$ in $\mathrm {GF} (p)[X]$ of degree $n {\displaystyle n}$ (such an irreducible polynomial always exists). Then thequotient ring $\mathrm {GF} (q)=\mathrm {GF} (p)[X]/(P)$ of the polynomial ring $\mathrm {GF} (p)[X]$ by the ideal generated by $P {\displaystyle P}$ is a field of order $q {\displaystyle q}$ .

More explicitly, the elements of $\mathrm {GF} (q)$ are the polynomials over $\mathrm {GF} (p)$ whose degree is strictly less than $n {\displaystyle n}$ . The addition and the subtraction are those of polynomials over $\mathrm {GF} (p)$ . The product of two elements is the remainder of theEuclidean division by $P {\displaystyle P}$ of the product in $\mathrm {GF} (q)[X]$ .The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm; seeExtended Euclidean algorithm § Simple algebraic field extensions.

However, with this representation, elements of $\mathrm {GF} (q)$ may be difficult to distinguish from the corresponding polynomials. Therefore, it is common to give a name, commonly $\alpha$ to the element of $\mathrm {GF} (q)$ that corresponds to the polynomial $X {\displaystyle X}$ . So, the elements of $\mathrm {GF} (q)$ become polynomials in $\alpha$ , where $P(\alpha )=0$ , and, when one encounters a polynomial in $\alpha$ of degree greater or equal to $n {\displaystyle n}$ (for example after a multiplication), one knows that one has to use the relation $P(\alpha )=0$ to reduce its degree (it is what Euclidean division is doing).

Except in the construction of $\mathrm {GF} (4)$ , there are several possible choices for $P {\displaystyle P}$ , which produce isomorphic results. To simplify the Euclidean division, one commonly chooses for $P {\displaystyle P}$ a polynomial of the form $X^{n}+aX+b,$ which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic $2 {\displaystyle 2}$ , irreducible polynomials of the form $X^{n}+aX+b$ may not exist. In characteristic $2 {\displaystyle 2}$ , if the polynomial $X^{n}+X+1$ is reducible, it is recommended to choose $X^{n}+X^{k}+1$ with the lowest possible $k {\displaystyle k}$ that makes the polynomial irreducible. If all thesetrinomials are reducible, one chooses "pentanomials" $X^{n}+X^{a}+X^{b}+X^{c}+1$ , as polynomials of degree greater than $1 {\displaystyle 1}$ , with an even number of terms, are never irreducible in characteristic $2 {\displaystyle 2}$ , having $1 {\displaystyle 1}$ as a root.^[3]

A possible choice for such a polynomial is given byConway polynomials. They ensure a certain compatibility between the representation of a field and the representations of its subfields.

In the next sections, we will show how the general construction method outlined above works for small finite fields.

Field with four elements

The smallest non-prime field is the field with four elements, which is commonly denoted $\mathrm {GF} (4)$ or $\mathbb {F} _{4}.$ It consists of the four elements $0,1,\alpha ,1+\alpha$ such that $\alpha ^{2}=1+\alpha$ , $1\cdot \alpha =\alpha \cdot 1=\alpha$ , $x+x=0$ , and $x\cdot 0=0\cdot x=0$ , for every $x\in \mathrm {GF} (4)$ , the other operation results being easily deduced from thedistributive law. See below for the complete operation tables.

This may be deduced as follows from the results of the preceding section.

Over $\mathrm {GF} (2)$ , there is only oneirreducible polynomial of degree $2 {\displaystyle 2}$ : $X^{2}+X+1$ Therefore, for $\mathrm {GF} (4)$ the construction of the preceding section must involve this polynomial, and $\mathrm {GF} (4)=\mathrm {GF} (2)[X]/(X^{2}+X+1).$ Let $\alpha$ denote a root of this polynomial in $\mathrm {GF} (4)$ . This implies that $\alpha ^{2}=1+\alpha ,$ and that $\alpha$ and $1+\alpha$ are the elements of $\mathrm {GF} (4)$ that are not in $\mathrm {GF} (2)$ . The tables of the operations in $\mathrm {GF} (4)$ result from this, and are as follows:

Addition $x+y$
y x	0	1	α	1 +α
0	0	1	α	1 +α
1	1	0	1 +α	α
α	α	1 +α	0	1
1 +α	1 +α	α	1	0

Multiplication $x\cdot y$
y x	0	1	α	1 +α
0	0	0	0	0
1	0	1	α	1 +α
α	0	α	1 +α	1
1 +α	0	1 +α	1	α

Division $x\div y$
y x	1	α	1 +α
0	0	0	0
1	1	1 +α	α
α	α	1	1 +α
1 +α	1 +α	α	1

A table for subtraction is not given, because subtraction is identical to addition, as is the case for every field of characteristic 2.In the third table, for the division of $x {\displaystyle x}$ by $y {\displaystyle y}$ , the values of $x {\displaystyle x}$ must be read in the left column, and the values of $y {\displaystyle y}$ in the top row. (Because $0\cdot z=0$ for every $z {\displaystyle z}$ in everyring thedivision by 0 has to remain undefined.) From the tables, it can be seen that the additive structure of $\mathrm {GF} (4)$ is isomorphic to theKlein four-group, while the non-zero multiplicative structure is isomorphic to the group $Z_{3}$ .

The map $\varphi :x\mapsto x^{2}$ is the non-trivial field automorphism, called theFrobenius automorphism, which sends $\alpha$ into the second root $1+\alpha$ of the above-mentioned irreducible polynomial $X^{2}+X+1$ .

GF(p²) for an odd primep

For applying theabove general construction of finite fields in the case of $\mathrm {GF} (p^{2})$ , one has to find an irreducible polynomial of degree 2. For $p=2$ , this has been done in the preceding section. If $p {\displaystyle p}$ is an odd prime, there are always irreducible polynomials of the form $X^{2}-r$ , with $r {\displaystyle r}$ in $\mathrm {GF} (p)$ .

More precisely, the polynomial $X^{2}-r$ is irreducible over $\mathrm {GF} (p)$ if and only if $r {\displaystyle r}$ is aquadratic non-residue modulo $p {\displaystyle p}$ (this is almost the definition of a quadratic non-residue). There are ${\frac {p-1}{2}}$ quadratic non-residues modulo $p {\displaystyle p}$ . For example, $2 {\displaystyle 2}$ is a quadratic non-residue for $p=3,5,11,13,\ldots$ , and $3 {\displaystyle 3}$ is a quadratic non-residue for $p=5,7,17,\ldots$ . If $p\equiv 3\mod 4$ , that is $p=3,7,11,19,\ldots$ , one may choose $-1\equiv p-1$ as a quadratic non-residue, which allows us to have a very simple irreducible polynomial $X^{2}+1$ .

Having chosen a quadratic non-residue $r {\displaystyle r}$ , let $\alpha$ be a symbolic square root of $r {\displaystyle r}$ , that is, a symbol that has the property $\alpha ^{2}=r$ , in the same way that the complex number $i {\displaystyle i}$ is a symbolic square root of $-1$ . Then, the elements of $\mathrm {GF} (p^{2})$ are all the linear expressions $a+b\alpha ,$ with $a {\displaystyle a}$ and $b {\displaystyle b}$ in $\mathrm {GF} (p)$ . The operations on $\mathrm {GF} (p^{2})$ are defined as follows (the operations between elements of $\mathrm {GF} (p)$ represented by Latin letters are the operations in $\mathrm {GF} (p)$ ): ${\begin{aligned}-(a+b\alpha )&=-a+(-b)\alpha \\(a+b\alpha )+(c+d\alpha )&=(a+c)+(b+d)\alpha \\(a+b\alpha )(c+d\alpha )&=(ac+rbd)+(ad+bc)\alpha \\(a+b\alpha )^{-1}&=a(a^{2}-rb^{2})^{-1}+(-b)(a^{2}-rb^{2})^{-1}\alpha \end{aligned}}$

GF(8) and GF(27)

The polynomial $X^{3}-X-1$ is irreducible over $\mathrm {GF} (2)$ and $\mathrm {GF} (3)$ , that is, it is irreduciblemodulo $2 {\displaystyle 2}$ and $3 {\displaystyle 3}$ (to show this, it suffices to show that it has no root in $\mathrm {GF} (2)$ nor in $\mathrm {GF} (3)$ ). It follows that the elements of $\mathrm {GF} (8)$ and $\mathrm {GF} (27)$ may be represented byexpressions $a+b\alpha +c\alpha ^{2},$ where $a, b, c {\displaystyle a,b,c}$ are elements of $\mathrm {GF} (2)$ or $\mathrm {GF} (3)$ (respectively), and $\alpha$ is a symbol such that $\alpha ^{3}=\alpha +1.$

The addition, additive inverse and multiplication on $\mathrm {GF} (8)$ and $\mathrm {GF} (27)$ may thus be defined as follows; in following formulas, the operations between elements of $\mathrm {GF} (2)$ or $\mathrm {GF} (3)$ , represented by Latin letters, are the operations in $\mathrm {GF} (2)$ or $\mathrm {GF} (3)$ , respectively: ${\begin{aligned}-(a+b\alpha +c\alpha ^{2})&=-a+(-b)\alpha +(-c)\alpha ^{2}\qquad {\text{(for }}\mathrm {GF} (8),{\text{this operation is the identity)}}\\(a+b\alpha +c\alpha ^{2})+(d+e\alpha +f\alpha ^{2})&=(a+d)+(b+e)\alpha +(c+f)\alpha ^{2}\\(a+b\alpha +c\alpha ^{2})(d+e\alpha +f\alpha ^{2})&=(ad+bf+ce)+(ae+bd+bf+ce+cf)\alpha +(af+be+cd+cf)\alpha ^{2}\end{aligned}}$

GF(16)

The polynomial $X^{4}+X+1$ is irreducible over $\mathrm {GF} (2)$ , that is, it is irreducible modulo $2 {\displaystyle 2}$ . It follows that the elements of $\mathrm {GF} (16)$ may be represented byexpressions $a+b\alpha +c\alpha ^{2}+d\alpha ^{3},$ where $a, b, c, d {\displaystyle a,b,c,d}$ are either $0 {\displaystyle 0}$ or $1 {\displaystyle 1}$ (elements of $\mathrm {GF} (2)$ ), and $\alpha$ is a symbol such that $\alpha ^{4}=\alpha +1$ (that is, $\alpha$ is defined as a root of the given irreducible polynomial). As the characteristic of $\mathrm {GF} (2)$ is $2 {\displaystyle 2}$ , each element is its additive inverse in $\mathrm {GF} (16)$ . The addition and multiplication on $\mathrm {GF} (16)$ may be defined as follows; in following formulas, the operations between elements of $\mathrm {GF} (2)$ , represented by Latin letters are the operations in $\mathrm {GF} (2)$ . ${\begin{aligned}(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})+(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(a+e)+(b+f)\alpha +(c+g)\alpha ^{2}+(d+h)\alpha ^{3}\\(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(ae+bh+cg+df)+(af+be+bh+cg+df+ch+dg)\alpha \;+\\&\quad \;(ag+bf+ce+ch+dg+dh)\alpha ^{2}+(ah+bg+cf+de+dh)\alpha ^{3}\end{aligned}}$

The field $\mathrm {GF} (16)$ has eightprimitive elements (the elements that have all nonzero elements of $\mathrm {GF} (16)$ as integer powers). These elements are the four roots of $X^{4}+X+1$ and theirmultiplicative inverses. In particular, $\alpha$ is a primitive element, and the primitive elements are $\alpha ^{m}$ with $m {\displaystyle m}$ less than andcoprime with $15 {\displaystyle 15}$ (that is, 1, 2, 4, 7, 8, 11, 13, 14).

Multiplicative structure

The set of non-zero elements in $\mathrm {GF} (q)$ is anabelian group under the multiplication, of order $q-1$ . ByLagrange's theorem, there exists a divisor $k {\displaystyle k}$ of $q-1$ such that $x^{k}=1$ for every non-zero $x {\displaystyle x}$ in $\mathrm {GF} (q)$ . As the equation $x^{k}=1$ has at most $k {\displaystyle k}$ solutions in any field, $q-1$ is the lowest possible value for $k {\displaystyle k}$ .Thestructure theorem of finite abelian groups implies that this multiplicative group iscyclic, that is, all non-zero elements are powers of a single element. In summary:

The multiplicative group of the non-zero elements in

\mathrm {GF} (q)

is cyclic, i.e., there exists an element

a {\displaystyle a}

,such that the

q-1

non-zero elements of

\mathrm {GF} (q)

are

a,a^{2},\ldots ,a^{q-2},a^{q-1}=1

.

Such an element $a {\displaystyle a}$ is called aprimitive element of $\mathrm {GF} (q)$ . Unless $q=2,3$ , the primitive element is not unique. The number of primitive elements is $\phi (q-1)$ where $\phi$ isEuler's totient function.

The result above implies that $x^{q}=x$ for every $x {\displaystyle x}$ in $\mathrm {GF} (q)$ . The particular case where $q {\displaystyle q}$ is prime isFermat's little theorem.

Discrete logarithm

If $a {\displaystyle a}$ is a primitive element in $\mathrm {GF} (q)$ , then for any non-zero element $x {\displaystyle x}$ in $F {\displaystyle F}$ , there is a unique integer $n {\displaystyle n}$ with $0\leq n\leq q-2$ such that $x=a^{n}$ .This integer $n {\displaystyle n}$ is called thediscrete logarithm of $x {\displaystyle x}$ to the base $a {\displaystyle a}$ .

While $a^{n}$ can be computed very quickly, for example usingexponentiation by squaring, there is no known efficient algorithm for computing the inverse operation, the discrete logarithm. This has been used in variouscryptographic protocols, seeDiscrete logarithm for details.

When the nonzero elements of $\mathrm {GF} (q)$ are represented by their discrete logarithms, multiplication and division are easy, as they reduce to addition and subtraction modulo $q-1$ . However, addition amounts to computing the discrete logarithm of $a^{m}+a^{n}$ . The identity $a^{m}+a^{n}=a^{n}\left(a^{m-n}+1\right)$ allows one to solve this problem by constructing the table of the discrete logarithms of $a^{n}+1$ , calledZech's logarithms, for $n=0,\ldots ,q-2$ (it is convenient to define the discrete logarithm of zero as being $-\infty$ ).

Zech's logarithms are useful for large computations, such aslinear algebra over medium-sized fields, that is, fields that are sufficiently large for making natural algorithms inefficient, but not too large, as one has to pre-compute a table of the same size as the order of the field.

Roots of unity

Every nonzero element of a finite field is aroot of unity, as $x^{q-1}=1$ for every nonzero element of $\mathrm {GF} (q)$ .

If $n {\displaystyle n}$ is a positive integer, an $n {\displaystyle n}$ thprimitive root of unity is a solution of the equation $x^{n}=1$ that is not a solution of the equation $x^{m}=1$ for any positive integer $m<n$ . If $a {\displaystyle a}$ is a $n {\displaystyle n}$ th primitive root of unity in a field $F {\displaystyle F}$ , then $F {\displaystyle F}$ contains all the $n {\displaystyle n}$ roots of unity, which are $1,a,a^{2},\ldots ,a^{n-1}$ .

The field $\mathrm {GF} (q)$ contains a $n {\displaystyle n}$ th primitive root of unity if and only if $n {\displaystyle n}$ is a divisor of $q-1$ ; if $n {\displaystyle n}$ is a divisor of $q-1$ , then the number of primitive $n {\displaystyle n}$ th roots of unity in $\mathrm {GF} (q)$ is $\phi (n)$ (Euler's totient function). The number of $n {\displaystyle n}$ th roots of unity in $\mathrm {GF} (q)$ is $\mathrm {gcd} (n,q-1)$ .

In a field of characteristic $p {\displaystyle p}$ , every $n p {\displaystyle np}$ th root of unity is also a $n {\displaystyle n}$ th root of unity. It follows that primitive $n p {\displaystyle np}$ th roots of unity never exist in a field of characteristic $p {\displaystyle p}$ .

On the other hand, if $n {\displaystyle n}$ iscoprime to $p {\displaystyle p}$ , the roots of the $n {\displaystyle n}$ thcyclotomic polynomial are distinct in every field of characteristic $p {\displaystyle p}$ , as this polynomial is a divisor of $X^{n}-1$ , whosediscriminant $n^{n}$ is nonzero modulo $p {\displaystyle p}$ . It follows that the $n {\displaystyle n}$ thcyclotomic polynomial factors over $\mathrm {GF} (q)$ into distinct irreducible polynomials that have all the same degree, say $d {\displaystyle d}$ , and that $\mathrm {GF} (p^{d})$ is the smallest field of characteristic $p {\displaystyle p}$ that contains the $n {\displaystyle n}$ th primitive roots of unity.

When computingBrauer characters, one uses the map $\alpha ^{k}\mapsto \exp(2\pi ik/(q-1))$ to map eigenvalues of a representation matrix to the complex numbers. Under this mapping, the base subfield $\mathrm {GF} (p)$ consists of evenly spaced points around the unit circle (omitting zero).

Finite field F_25 under map to complex roots of unity. Base subfield F_5 in red.

Example: GF(64)

The field $\mathrm {GF} (64)$ has several interesting properties that smaller fields do not share: it has two subfields such that neither is contained in the other; not all generators (elements withminimal polynomial of degree $6 {\displaystyle 6}$ over $\mathrm {GF} (2)$ ) are primitive elements; and the primitive elements are not all conjugate under theGalois group.

The order of this field being2⁶, and the divisors of6 being1, 2, 3, 6, the subfields ofGF(64) areGF(2),GF(2²) = GF(4),GF(2³) = GF(8), andGF(64) itself. As2 and3 arecoprime, the intersection ofGF(4) andGF(8) inGF(64) is the prime fieldGF(2).

The union ofGF(4) andGF(8) has thus10 elements. The remaining54 elements ofGF(64) generateGF(64) in the sense that no other subfield contains any of them. It follows that they are roots of irreducible polynomials of degree6 overGF(2). This implies that, overGF(2), there are exactly9 =⁠54/6⁠ irreduciblemonic polynomials of degree6. This may be verified by factoringX⁶⁴ −X overGF(2).

The elements ofGF(64) are primitive $n {\displaystyle n}$ th roots of unity for some $n {\displaystyle n}$ dividing $63 {\displaystyle 63}$ . As the 3rd and the 7th roots of unity belong toGF(4) andGF(8), respectively, the54 generators are primitiventh roots of unity for somen in{9, 21, 63}.Euler's totient function shows that there are6 primitive9th roots of unity, $12 {\displaystyle 12}$ primitive $21 {\displaystyle 21}$ st roots of unity, and $36 {\displaystyle 36}$ primitive63rd roots of unity. Summing these numbers, one finds again $54 {\displaystyle 54}$ elements.

By factoring thecyclotomic polynomials over $\mathrm {GF} (2)$ , one finds that:

The six primitive $9 {\displaystyle 9}$ th roots of unity are roots of $X^{6}+X^{3}+1,$ and are all conjugate under the action of the Galois group.
The twelve primitive $21 {\displaystyle 21}$ st roots of unity are roots of $(X^{6}+X^{4}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X^{2}+1).$ They form two orbits under the action of the Galois group. As the two factors arereciprocal to each other, a root and its (multiplicative) inverse do not belong to the same orbit.
The $36 {\displaystyle 36}$ primitive elements of $\mathrm {GF} (64)$ are the roots of $(X^{6}+X^{4}+X^{3}+X+1)(X^{6}+X+1)(X^{6}+X^{5}+1)(X^{6}+X^{5}+X^{3}+X^{2}+1)(X^{6}+X^{5}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X+1).$ They split into six orbits of six elements each under the action of the Galois group.

This shows that the best choice to construct $\mathrm {GF} (64)$ is to define it asGF(2)[X] / (X⁶ +X + 1). In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.

Frobenius automorphism and Galois theory

In this section, $p {\displaystyle p}$ is a prime number, and $q=p^{n}$ is a power of $p {\displaystyle p}$ .

In $\mathrm {GF} (q)$ , the identity(x +y)^p =x^p +y^p implies that the map $\varphi :x\mapsto x^{p}$ is a $\mathrm {GF} (p)$ -linear endomorphism and afield automorphism of $\mathrm {GF} (q)$ , which fixes every element of the subfield $\mathrm {GF} (p)$ . It is called theFrobenius automorphism, afterFerdinand Georg Frobenius.

Denoting byφ^k thecomposition ofφ with itselfk times, we have $\varphi ^{k}:x\mapsto x^{p^{k}}.$ It has been shown in the preceding section thatφⁿ is the identity. For0 <k <n, the automorphismφ^k is not the identity, as, otherwise, the polynomial $X^{p^{k}}-X$ would have more thanp^k roots.

There are no otherGF(p)-automorphisms ofGF(q). In other words,GF(pⁿ) has exactlynGF(p)-automorphisms, which are $\mathrm {Id} =\varphi ^{0},\varphi ,\varphi ^{2},\ldots ,\varphi ^{n-1}.$

In terms ofGalois theory, this means thatGF(pⁿ) is aGalois extension ofGF(p), which has acyclic Galois group.

The fact that the Frobenius map is surjective implies that every finite field isperfect.

Polynomial factorization

Main article:Factorization of polynomials over finite fields

IfF is a finite field, a non-constantmonic polynomial with coefficients inF isirreducible overF, if it is not the product of two non-constant monic polynomials, with coefficients inF.

As everypolynomial ring over a field is aunique factorization domain, every monic polynomial over a finite field may be factored in a unique way (up to the order of the factors) into a product of irreducible monic polynomials.

There are efficient algorithms for testing polynomial irreducibility and factoring polynomials over finite fields. They are a key step for factoring polynomials over the integers or therational numbers. At least for this reason, everycomputer algebra system has functions for factoring polynomials over finite fields, or, at least, over finite prime fields.

Irreducible polynomials of a given degree

The polynomial $X^{q}-X$ factors into linear factors over a field of orderq. More precisely, this polynomial is the product of all monic polynomials of degree one over a field of orderq.

This implies that, ifq =pⁿ thenX^q −X is the product of all monic irreducible polynomials overGF(p), whose degree dividesn. In fact, ifP is an irreducible factor overGF(p) ofX^q −X, its degree dividesn, as itssplitting field is contained inGF(pⁿ). Conversely, ifP is an irreducible monic polynomial overGF(p) of degreed dividingn, it defines a field extension of degreed, which is contained inGF(pⁿ), and all roots ofP belong toGF(pⁿ), and are roots ofX^q −X; thusP dividesX^q −X. AsX^q −X does not have any multiple factor, it is thus the product of all the irreducible monic polynomials that divide it.

This property is used to compute the product of the irreducible factors of each degree of polynomials overGF(p); seeDistinct degree factorization.

Number of monic irreducible polynomials of a given degree over a finite field

The numberN(q,n) of monic irreducible polynomials of degreen overGF(q) is given by^[4] $N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{n/d},$ whereμ is theMöbius function. This formula is an immediate consequence of the property ofX^q −X above and theMöbius inversion formula.

By the above formula, the number of irreducible (not necessarily monic) polynomials of degreen overGF(q) is(q − 1)N(q,n).

The exact formula implies the inequality $N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{\ell \mid n,\ \ell {\text{ prime}}}q^{n/\ell }\right);$ this is sharp if and only ifn is a power of some prime.For everyq and everyn, the right hand side is positive, so there is at least one irreducible polynomial of degreen overGF(q).

Applications

Incryptography, the difficulty of thediscrete logarithm problem in finite fields or inelliptic curves is the basis of several widely used protocols, such as theDiffie–Hellman protocol. For example, in 2014, a secure internet connection to Wikipedia involved the elliptic curve Diffie–Hellman protocol (ECDHE) over a large finite field.^[5] Incoding theory, many codes are constructed assubspaces ofvector spaces over finite fields.

Finite fields are used by manyerror correction codes, such asReed–Solomon error correction code orBCH code. The finite field almost always has characteristic of2, since computer data is stored in binary. For example, a byte of data can be interpreted as an element ofGF(2⁸). One exception isPDF417 bar code, which isGF(929). Some CPUs have special instructions that can be useful for finite fields of characteristic2, generally variations ofcarry-less product.

Finite fields are widely used innumber theory, as many problems over the integers may be solved by reducing themmodulo one or severalprime numbers. For example, the fastest known algorithms forpolynomial factorization andlinear algebra over the field ofrational numbers proceed by reduction modulo one or several primes, and then reconstruction of the solution by usingChinese remainder theorem,Hensel lifting or theLLL algorithm.

Similarly many theoretical problems in number theory can be solved by considering their reductions modulo some or all prime numbers. See, for example,Hasse principle. Many recent developments ofalgebraic geometry were motivated by the need to enlarge the power of these modular methods.Wiles' proof of Fermat's Last Theorem is an example of a deep result involving many mathematical tools, including finite fields.

TheWeil conjectures concern the number of points onalgebraic varieties over finite fields and the theory has many applications includingexponential andcharacter sum estimates.

Finite fields have widespread application incombinatorics, two well known examples being the definition ofPaley Graphs and the related construction forHadamard Matrices. Inarithmetic combinatorics finite fields^[6] and finite field models^[7]^[8] are used extensively, such as inSzemerédi's theorem on arithmetic progressions.

Extensions

Wedderburn's little theorem

Adivision ring is a generalization of field. Division rings are not assumed to be commutative. There are no non-commutative finite division rings:Wedderburn's little theorem states that all finitedivision rings are commutative, and hence are finite fields. This result holds even if we relax theassociativity axiom toalternativity, that is, all finitealternative division rings are finite fields, by theArtin–Zorn theorem.^[9]

Algebraic closure

A finite field $F {\displaystyle F}$ is not algebraically closed: the polynomial $f(T)=1+\prod _{\alpha \in F}(T-\alpha ),$ has no roots in $F {\displaystyle F}$ , sincef (α) = 1 for all $\alpha$ in $F {\displaystyle F}$ .

Given a prime numberp, let ${\overline {\mathbb {F} }}_{p}$ be an algebraic closure of $\mathbb {F} _{p}.$ It is not only uniqueup to an isomorphism, as do all algebraic closures, but contrarily to the general case, all its subfield are fixed by all its automorphisms, and it is also the algebraic closure of all finite fields of the same characteristicp.

This property results mainly from the fact that the elements of $\mathbb {F} _{p^{n}}$ are exactly the roots of $x^{p^{n}}-x,$ and this defines an inclusion $\mathbb {\mathbb {F} } _{p^{n}}\subset \mathbb {F} _{p^{nm}}$ for $m>1.$ These inclusions allow writing informally ${\overline {\mathbb {F} }}_{p}=\bigcup _{n\geq 1}\mathbb {F} _{p^{n}}.$ The formal validation of this notation results from the fact that the above field inclusions form adirected set of fields; Itsdirect limit is ${\overline {\mathbb {F} }}_{p},$ which may thus be considered as "directed union".

Primitive elements in the algebraic closure

Given aprimitive element $g_{mn}$ of $\mathbb {F} _{q^{mn}},$ then $g_{mn}^{m}$ is a primitive element of $\mathbb {F} _{q^{n}}.$

For explicit computations, it may be useful to have a coherent choice of the primitive elements for all finite fields; that is, to choose the primitive element $g_{n}$ of $\mathbb {F} _{q^{n}}$ in order that, whenever $n=mh,$ one has $g_{m}=g_{n}^{h},$ where $g_{m}$ is the primitive element already chosen for $\mathbb {F} _{q^{m}}.$

Such a construction may be obtained byConway polynomials.

Quasi-algebraic closure

Although finite fields are not algebraically closed, they arequasi-algebraically closed, which means that everyhomogeneous polynomial over a finite field has a non-trivial zero whose components are in the field if the number of its variables is more than its degree. This was a conjecture ofArtin andDickson proved byChevalley (seeChevalley–Warning theorem).

See also

Notes

^^a ^bMoore, E. H. (1896), "A doubly-infinite system of simple groups", in E. H. Moore; et al. (eds.),Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition, Macmillan & Co., pp. 208–242
^This latter notation was introduced byE. H. Moore in an address given in 1893 at the International Mathematical Congress held in ChicagoMullen & Panario 2013, p. 10.
^Recommended Elliptic Curves for Government Use(PDF),National Institute of Standards and Technology, July 1999, p. 3,archived(PDF) from the original on 2008-07-19
^Jacobson 2009, §4.13
^This can be verified by looking at the information on the page provided by the browser.
^Shparlinski, Igor E. (2013), "Additive Combinatorics over Finite Fields: New Results and Applications",Finite Fields and Their Applications, DE GRUYTER, pp. 233–272,doi:10.1515/9783110283600.233,ISBN 9783110283600
^Green, Ben (2005), "Finite field models in additive combinatorics",Surveys in Combinatorics 2005, Cambridge University Press, pp. 1–28,arXiv:math/0409420,doi:10.1017/cbo9780511734885.002,ISBN 9780511734885,S2CID 28297089
^Wolf, J. (March 2015)."Finite field models in arithmetic combinatorics – ten years on".Finite Fields and Their Applications.32:233–274.doi:10.1016/j.ffa.2014.11.003.hdl:1983/d340f853-0584-49c8-a463-ea16ee51ce0f.ISSN 1071-5797.
^Shult, Ernest E. (2011).Points and lines. Characterizing the classical geometries. Universitext. Berlin:Springer-Verlag. p. 123.ISBN 978-3-642-15626-7.Zbl 1213.51001.

References

W. H. Bussey (1905) "Galois field tables forpⁿ ≤ 169",Bulletin of the American Mathematical Society 12(1): 22–38,doi:10.1090/S0002-9904-1905-01284-2
W. H. Bussey (1910) "Tables of Galois fields of order < 1000",Bulletin of the American Mathematical Society 16(4): 188–206,doi:10.1090/S0002-9904-1910-01888-7
Jacobson, Nathan (2009) [1985],Basic algebra I (Second ed.), Dover Publications,ISBN 978-0-486-47189-1
Mullen, Gary L.; Mummert, Carl (2007),Finite Fields and Applications I, Student Mathematical Library (AMS),ISBN 978-0-8218-4418-2
Mullen, Gary L.; Panario, Daniel (2013),Handbook of Finite Fields, CRC Press,ISBN 978-1-4398-7378-6
Lidl, Rudolf;Niederreiter, Harald (1997),Finite Fields (2nd ed.),Cambridge University Press,ISBN 0-521-39231-4
Skopin, A. I. (2001) [1994],"Galois field",Encyclopedia of Mathematics,EMS Press

External links

Finite Fields at Wolfram research.
Finite Fields and Their Applications, Science Direct, (Open Access Journal).

Retrieved from "https://en.wikipedia.org/w/index.php?title=Finite_field&oldid=1278699878"

Finite fields

Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp