Namespaces
Variants
Actions

Difference between revisions of "Galois field"

From Encyclopedia of Mathematics
Jump to: navigation, search
(LaTeX continued)
(LaTeX)
Line 10: Line 10:
 
$$
 
$$
 
where $\mu$ is the [[Möbius function|Möbius function]]. The additive group of the field $\mathrm{GF}(p^n)$ is naturally endowed with the structure of an $n$-dimensional vector space over $\mathrm{GF}(p)$. As a basis one may take $1,\alpha,\ldots,\alpha^{n-1}$. The non-zero elements of $\mathrm{GF}(p^n)$ form a multiplicative group, $\mathrm{GF}(p^n)^*$, of order $p^n-1$, i.e. each element of $\mathrm{GF}(p^n)^*$ is a root of the polynomial $X^{p^n-1}-1$. The group $\mathrm{GF}(p^n)^*$ is cyclic, and its generators are the primitive roots of unity of degree $p^n-1$, the number of which is $\phi(p^n-1)$, where $\phi$ is the [[Euler function|Euler function]]. Each primitive root of unity of degree $p^n-1$ is a primitive element of the extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$, but the converse is not true. More exactly, out of the
 
where $\mu$ is the [[Möbius function|Möbius function]]. The additive group of the field $\mathrm{GF}(p^n)$ is naturally endowed with the structure of an $n$-dimensional vector space over $\mathrm{GF}(p)$. As a basis one may take $1,\alpha,\ldots,\alpha^{n-1}$. The non-zero elements of $\mathrm{GF}(p^n)$ form a multiplicative group, $\mathrm{GF}(p^n)^*$, of order $p^n-1$, i.e. each element of $\mathrm{GF}(p^n)^*$ is a root of the polynomial $X^{p^n-1}-1$. The group $\mathrm{GF}(p^n)^*$ is cyclic, and its generators are the primitive roots of unity of degree $p^n-1$, the number of which is $\phi(p^n-1)$, where $\phi$ is the [[Euler function|Euler function]]. Each primitive root of unity of degree $p^n-1$ is a primitive element of the extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$, but the converse is not true. More exactly, out of the
 +
$$
 +
\frac{1}{n} \sum_{d|n} \mu(d) p^{n/d}
 +
$$
 +
irreducible unitary polynomials of degree $n$ over $\mathrm{GF}(p)$ there are $\phi(p^n-1)/n$ polynomials of which the roots are generators of $\mathrm{GF}(p^n)$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314050.png" /></td> </tr></table>
+
The set of elements of $\mathrm{GF}(p^n)$ coincides with the set of roots of the polynomial $X^{p^n} - X$ in $\Omega$, i.e. $\mathrm{GF}(p^n)$ is characterized as the subfield of elements from $\Omega$ that are invariant with respect to the automorphism $\tau : x \mapsto x^{p^n}$, which is known as the Frobenius automorphism. If $\mathrm{GF}(p^m) \supset \mathrm{GF}(p^n)$, the extension $\mathrm{GF}(p^m)/\mathrm{GF}(p^n)$ is normal (cf. [[Extension of a field|Extension of a field]]), and its [[Galois group|Galois group]] $\mathrm{Gal}\left({\mathrm{GF}(p^m)/\mathrm{GF}(p^n)}\right)$ is cyclic of order $m/n$. The automorphism $\tau$ may be taken as the generator of $\mathrm{Gal}\left({\mathrm{GF}(p^m)/\mathrm{GF}(p^n)}\right)$.
 
 
irreducible unitary polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314051.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314052.png" /> there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314053.png" /> polynomials of which the roots are generators of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314054.png" />.
 
 
 
The set of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314055.png" /> coincides with the set of roots of the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314056.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314057.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314058.png" /> is characterized as the subfield of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314059.png" /> that are invariant with respect to the automorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314060.png" />, which is known as the Frobenius automorphism. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314061.png" />, the extension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314062.png" /> is normal (cf. [[Extension of a field|Extension of a field]]), and its [[Galois group|Galois group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314063.png" /> is cyclic of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314064.png" />. The automorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314065.png" /> may be taken as the generator of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043140/g04314066.png" />.
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E. Galois,  "Écrits et mémoires d'E. Galois" , Gauthier-Villars  (1962)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  B.L. van der Waerden,  "Algebra" , '''1–2''' , Springer  (1967–1971)  (Translated from German)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.G. [N.G. Chebotarev] Tschebotaröw,  "Grundzüge der Galois'schen Theorie" , Noordhoff  (1950)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N. Bourbaki,  "Algebra" , ''Elements of mathematics'' , '''1''' , Springer  (1989)  pp. Chapt. 1–3  (Translated from French)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E. Galois,  "Écrits et mémoires d'E. Galois" , Gauthier-Villars  (1962)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  B.L. van der Waerden,  "Algebra" , '''1–2''' , Springer  (1967–1971)  (Translated from German)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.G. [N.G. Chebotarev] Tschebotaröw,  "Grundzüge der Galois'schen Theorie" , Noordhoff  (1950)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N. Bourbaki,  "Algebra" , ''Elements of mathematics'' , '''1''' , Springer  (1989)  pp. Chapt. 1–3  (Translated from French)</TD></TR></table>

Revision as of 21:40, 11 October 2014

finite field

A field with a finite number of elements. First considered by E. Galois [1].

The number of elements of any finite field is a power $p^n$ of a prime number $p$, which is the characteristic of this field. For any prime number $p$ and any natural number $n$ there exists a (unique up to an isomorphism) field of $p^n$ elements. It is denoted by $\mathrm{GF}(p^n)$ or by $\mathbb{F}_{p^n}$. The field $\mathrm{GF}(p^m)$ contains the field $\mathrm{GF}(p^n)$ as a subfield if and only if $m$ is divisible by $n$. In particular, any field $\mathrm{GF}(p^n)$ contains the field $\mathrm{GF}(p)$, which is called the prime field of characteristic $p$. The field $\mathrm{GF}(p)$ is isomorphic to the field $\mathbb{Z}/p\mathbb{Z}$ of residue classes of the ring of integers modulo $p$. In any fixed algebraic closure $\Omega$ of $\mathrm{GF}(p)$ there exists exactly one subfield $\mathrm{GF}(p^n)$ for each $n$. The correspondence $n \leftrightarrow \mathrm{GF}(p^n)$ is an isomorphism between the lattice of natural numbers with respect to division and the lattice of finite algebraic extensions (in $\Omega$) of $\mathrm{GF}(p)$ with respect to inclusion. The lattice of finite algebraic extensions of any Galois field within its fixed algebraic closure is such a lattice.

The algebraic extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$ is simple, i.e. there exists a primitive element $\alpha \in \mathrm{GF}(p^n)$ such that $\mathrm{GF}(p^n) = \mathrm{GF}(p)(\alpha)$. Such an $\alpha$ will be any root of any irreducible polynomial of degree $n$ from the ring $\mathrm{GF}(p)[X]$. The number of primitive elements of the extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$ equals $$ \sum_{d|n} \mu(d) p^{n/d} $$ where $\mu$ is the Möbius function. The additive group of the field $\mathrm{GF}(p^n)$ is naturally endowed with the structure of an $n$-dimensional vector space over $\mathrm{GF}(p)$. As a basis one may take $1,\alpha,\ldots,\alpha^{n-1}$. The non-zero elements of $\mathrm{GF}(p^n)$ form a multiplicative group, $\mathrm{GF}(p^n)^*$, of order $p^n-1$, i.e. each element of $\mathrm{GF}(p^n)^*$ is a root of the polynomial $X^{p^n-1}-1$. The group $\mathrm{GF}(p^n)^*$ is cyclic, and its generators are the primitive roots of unity of degree $p^n-1$, the number of which is $\phi(p^n-1)$, where $\phi$ is the Euler function. Each primitive root of unity of degree $p^n-1$ is a primitive element of the extension $\mathrm{GF}(p^n)/\mathrm{GF}(p)$, but the converse is not true. More exactly, out of the $$ \frac{1}{n} \sum_{d|n} \mu(d) p^{n/d} $$ irreducible unitary polynomials of degree $n$ over $\mathrm{GF}(p)$ there are $\phi(p^n-1)/n$ polynomials of which the roots are generators of $\mathrm{GF}(p^n)$.

The set of elements of $\mathrm{GF}(p^n)$ coincides with the set of roots of the polynomial $X^{p^n} - X$ in $\Omega$, i.e. $\mathrm{GF}(p^n)$ is characterized as the subfield of elements from $\Omega$ that are invariant with respect to the automorphism $\tau : x \mapsto x^{p^n}$, which is known as the Frobenius automorphism. If $\mathrm{GF}(p^m) \supset \mathrm{GF}(p^n)$, the extension $\mathrm{GF}(p^m)/\mathrm{GF}(p^n)$ is normal (cf. Extension of a field), and its Galois group $\mathrm{Gal}\left({\mathrm{GF}(p^m)/\mathrm{GF}(p^n)}\right)$ is cyclic of order $m/n$. The automorphism $\tau$ may be taken as the generator of $\mathrm{Gal}\left({\mathrm{GF}(p^m)/\mathrm{GF}(p^n)}\right)$.

References

[1] E. Galois, "Écrits et mémoires d'E. Galois" , Gauthier-Villars (1962)
[2] B.L. van der Waerden, "Algebra" , 1–2 , Springer (1967–1971) (Translated from German)
[3] N.G. [N.G. Chebotarev] Tschebotaröw, "Grundzüge der Galois'schen Theorie" , Noordhoff (1950) (Translated from Russian)
[4] N. Bourbaki, "Algebra" , Elements of mathematics , 1 , Springer (1989) pp. Chapt. 1–3 (Translated from French)
How to Cite This Entry:
Galois field. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Galois_field&oldid=33555
This article was adapted from an original article by A.I. Skopin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article