Editing Finite field (section)

== Multiplicative structure ==

The set of non-zero elements in <math>\mathrm{GF}(q)</math> is an [[abelian group]] under the multiplication, of order <math>q-1</math>. By [[Lagrange's theorem (group theory)|Lagrange's theorem]], there exists a divisor <math>k</math> of <math>q-1</math> such that <math>x^k=1</math> for every non-zero <math>x</math> in <math>\mathrm{GF}(q)</math>. As the equation <math>x^k=1</math> has at most <math>k</math> solutions in any field, <math>q-1</math> is the lowest possible value for <math>k</math>.
The [[Abelian group#Classification|structure theorem of finite abelian groups]] implies that this multiplicative group is [[cyclic group|cyclic]], that is, all non-zero elements are powers of a single element. In summary:

{{block indent | em = 1.5 | text = ''The multiplicative group of the non-zero elements in'' <math>\mathrm{GF}(q)</math> ''is cyclic, i.e.,  there exists an element'' <math>a</math>, ''such that the'' <math>q-1</math> ''non-zero elements of'' <math>\mathrm{GF}(q)</math> ''are'' <math>a,a^2,\ldots,a^{q-2},a^{q-1}=1</math>.}}

Such an element <math>a</math> is called a [[primitive element (finite field)|primitive element]] of <math>\mathrm{GF}(q)</math>. Unless <math>q=2,3</math>, the primitive element is not unique. The number of primitive elements is <math>\phi(q-1)</math> where <math>\phi</math> is [[Euler's totient function]].

The result above implies that <math>x^q=x</math> for every <math>x</math> in <math>\mathrm{GF}(q)</math>. The particular case where <math>q</math> is prime is [[Fermat's little theorem]].

=== Discrete logarithm ===

If <math>a</math> is a primitive element in <math>\mathrm{GF}(q)</math>, then for any non-zero element <math>x</math> in <math>F</math>, there is a unique integer <math>n</math> with <math>0 \le n \le q-2</math> such that <math>x=a^n</math>.
This integer <math>n</math> is called the [[discrete logarithm]] of <math>x</math> to the base <math>a</math>.

While <math>a^n</math> can be computed very quickly, for example using [[exponentiation by squaring]], there is no known efficient algorithm for computing the inverse operation, the discrete logarithm. This has been used in various [[cryptographic protocol]]s, see ''[[Discrete logarithm]]'' for details.

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

Zech's logarithms are useful for large computations, such as [[linear 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 a [[root of unity]], as <math>x^{q-1}=1</math> for every nonzero element of <math>\mathrm{GF}(q)</math>.

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

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

In a field of characteristic <math>p</math>, every <math>np</math>th root of unity is also a <math>n</math>th root of unity. It follows that primitive <math>np</math>th roots of unity never exist in a field of characteristic <math>p</math>.

On the other hand, if <math>n</math> is [[coprime]] to <math>p</math>, the roots of the <math>n</math>th [[cyclotomic polynomial]] are distinct in every field of characteristic <math>p</math>, as this polynomial is a divisor of <math>X^n-1</math>, whose [[discriminant]] <math>n^n</math> is nonzero modulo <math>p</math>. It follows that the <math>n</math>th [[cyclotomic polynomial]] factors over <math>\mathrm{GF}(q)</math> into distinct irreducible polynomials that have all the same degree, say <math>d</math>, and that <math>\mathrm{GF}(p^d)</math> is the smallest field of characteristic <math>p</math> that contains the <math>n</math>th primitive roots of unity.

When computing [[Modular representation theory|Brauer characters]], one uses the map <math>\alpha^k \mapsto \exp(2\pi i k / (q-1))</math> to map eigenvalues of a representation matrix to the complex numbers. Under this mapping, the base subfield <math>\mathrm{GF}(p)</math> consists of evenly spaced points around the unit circle (omitting zero).

[[File:Finite field with 25 elements and base subfield of five elements.jpg|thumb|300px|Finite field F_25 under map to complex roots of unity. Base subfield F_5 in red.]]

=== Example: GF(64) ===
The field <math>\mathrm{GF}(64)</math> 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 with [[Minimal polynomial (field theory)|minimal polynomial]] of degree <math>6</math> over <math>\mathrm{GF}(2)</math>) are primitive elements; and the primitive elements are not all conjugate under the [[Galois group]].

The order of this field being {{math|2<sup>6</sup>}}, and the divisors of {{math|6}} being {{math|1, 2, 3, 6}}, the subfields of {{math|GF(64)}} are {{math|GF(2)}}, {{math|1=GF(2<sup>2</sup>) = GF(4)}}, {{math|1=GF(2<sup>3</sup>) = GF(8)}}, and {{math|GF(64)}} itself. As {{math|2}} and {{math|3}} are [[coprime]], the intersection of {{math|GF(4)}} and {{math|GF(8)}} in {{math|GF(64)}} is the prime field {{math|GF(2)}}.

The union of {{math|GF(4)}} and {{math|GF(8)}} has thus {{math|10}} elements. The remaining {{math|54}} elements of {{math|GF(64)}} generate {{math|GF(64)}} in the sense that no other subfield contains any of them. It follows that they are roots of irreducible polynomials of degree {{math|6}} over {{math|GF(2)}}. This implies that, over {{math|GF(2)}}, there are exactly {{math|1=9 = {{sfrac|54|6}}}} irreducible [[monic polynomial]]s of degree {{math|6}}. This may be verified by factoring {{math|''X''<sup>64</sup> − ''X''}} over {{math|GF(2)}}.

The elements of {{math|GF(64)}} are primitive <math>n</math>th roots of unity for some <math>n</math> dividing <math>63</math>. As the 3rd and the 7th roots of unity belong to {{math|GF(4)}} and {{math|GF(8)}}, respectively, the {{math|54}} generators are primitive {{math|''n''}}th roots of unity for some {{math|''n''}} in {{math|{9, 21, 63}<nowiki/>}}. [[Euler's totient function]] shows that there are {{math|6}} primitive {{math|9}}th roots of unity, <math>12</math> primitive <math>21</math>st roots of unity, and <math>36</math> primitive {{math|63}}rd roots of unity. Summing these numbers, one finds again <math>54</math> elements.

By factoring the [[cyclotomic polynomial]]s over <math>\mathrm{GF}(2)</math>, one finds that:
* The six primitive <math>9</math>th roots of unity are roots of <math display="block">X^6+X^3+1,</math> and are all conjugate under the action of the Galois group.
* The twelve primitive <math>21</math>st roots of unity are roots of <math display="block">(X^6+X^4+X^2+X+1)(X^6+X^5+X^4+X^2+1).</math> They form two orbits under the action of the Galois group. As the two factors are [[reciprocal polynomial|reciprocal]] to each other, a root and its (multiplicative) inverse do not belong to the same orbit.
* The <math>36</math> primitive elements of <math>\mathrm{GF}(64)</math> are the roots of <math display="block">(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).</math> They split into six orbits of six elements each under the action of the Galois group.

This shows that the best choice to construct <math>\mathrm{GF}(64)</math> is to define it as {{math|GF(2)[''X''] / (''X''<sup>6</sup> + ''X'' + 1)}}. In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.