Editing Finite field (section)

== Explicit construction ==

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

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

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

Except in the construction of <math>\mathrm{GF}(4)</math>, there are several possible choices for <math>P</math>, which produce isomorphic results. To simplify the Euclidean division, one commonly chooses for <math>P</math> a polynomial of the form 
<math display="block">X^n + aX + b,</math>
which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic <math>2</math>, irreducible polynomials of the form <math>X^n+aX+b</math> may not exist. In characteristic <math>2</math>, if the polynomial <math>X^n+X+1</math> is reducible, it is recommended to choose <math>X^n+X^k+1</math> with the lowest possible <math>k</math> that makes the polynomial irreducible. If all these [[trinomial]]s are reducible, one chooses "pentanomials" <math>X^n+X^a+X^b+X^c+1</math>, as polynomials of degree greater than <math>1</math>, with an even number of terms, are never irreducible in characteristic <math>2</math>, having <math>1</math> as a root.<ref>{{citation|publisher=[[National Institute of Standards and Technology]]|url=http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |archive-url=https://web.archive.org/web/20080719074906/http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |archive-date=2008-07-19 |url-status=live|title=Recommended Elliptic Curves for Government Use|pages=3|date=July 1999}}</ref>

A possible choice for such a polynomial is given by [[Conway polynomial (finite fields)|Conway 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 <math>\mathrm{GF}(4)</math> or <math>\mathbb{F}_4.</math> It consists of the four elements <math>0, 1, \alpha, 1 + \alpha</math> such that <math>\alpha^2=1+\alpha</math>, <math>1 \cdot \alpha = \alpha \cdot 1 = \alpha</math>, <math>x+x=0</math>, and <math>x \cdot 0 = 0 \cdot x = 0</math>, for every <math>x \in \mathrm{GF}(4)</math>, the other operation results being easily deduced from the [[distributive law]]. See below for the complete operation tables.

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

Over <math>\mathrm{GF}(2)</math>, there is only one [[irreducible polynomial]] of degree <math>2</math>:
<math display="block">X^2+X+1</math>
Therefore, for <math>\mathrm{GF}(4)</math> the construction of the preceding section must involve this polynomial, and
<math display="block">\mathrm{GF}(4) = \mathrm{GF}(2)[X]/(X^2+X+1).</math>
Let <math>\alpha</math> denote a root of this polynomial in <math>\mathrm{GF}(4)</math>. This implies that
<math display="block">\alpha^2 = 1 + \alpha,</math>
and that <math>\alpha</math> and <math>1+\alpha</math> are the elements of <math>\mathrm{GF}(4)</math> that are not in <math>\mathrm{GF}(2)</math>. The tables of the operations in <math>\mathrm{GF}(4)</math> result from this, and are as follows:
{| style="border-spacing:1.7em 0"
|
{| class="wikitable"
|+ Addition <math>x + y</math>
|-
! style="width:24%;" {{diagonal split header|{{math|''x''}}|{{math|''y''}}}} !! style="width:20%;"| {{math|0}} !! style="width:20%;"| {{math|1}} !! style="width:20%;"| {{math|''α''}} !! style="width:20%;"| {{math|1 + ''α''}}
|-
!style="text-align:left"| {{math|0}}
| {{math|0}}
| {{math|1}}
| {{math|''α''}}
| {{math|1 + ''α''}}
|-
!style="text-align:left"| {{math|1}}
| {{math|1}}
| {{math|0}}
| {{math|1 + ''α''}}
| {{math|''α''}}
|-
!style="text-align:left"| {{math|''α''}}
|| {{math|''α''}}
| {{math|1 + ''α''}}
| {{math|0}}
| {{math|1}}
|-
!style="text-align:left"| {{math|1 + ''α''}}
| {{math|1 + ''α''}}
| {{math|''α''}}
| {{math|1}}
| {{math|0}}
|}
|
{| class="wikitable"
|+ Multiplication <math>x \cdot y</math>
|-
! style="width:28%;" {{diagonal split header|{{math|''x''}}|{{math|''y''}}}} !! style="width:12%;"| {{math|0}} !! style="width:20%;"| {{math|1}} !! style="width:20%;"| {{math|''α''}} !! style="width:20%;"| {{math|1 + ''α''}}
|-
!style="text-align:left"| {{math|0}}
| {{math|0}}
| {{math|0}}
|| {{math|0}}
|| {{math|0}}
|-
!style="text-align:left"| {{math|1}}
| {{math|0}}
| {{math|1}}
|| {{math|''α''}}
|| {{math|1 + ''α''}}
|-
!style="text-align:left"| {{math|''α''}}
|| {{math|0}}
|| {{math|''α''}}
|| {{math|1 + ''α''}}
|| {{math|1}}
|-
!style="text-align:left"| {{math|1 + ''α''}}
|| {{math|0}}
|| {{math|1 + ''α''}}
|| {{math|1}}
|| {{math|''α''}}
|}
|
{| class="wikitable"
|+ Division <math>x \div y</math>
|-
! style="width:24%;" {{diagonal split header|{{math|''x''}}|{{math|''y''}}}} !! style="width:20%;"| {{math|1}} !! style="width:20%;"| {{math|''α''}} !! style="width:20%;"| {{math|1 + ''α''}}
|-
!style="text-align:left"| {{math|0}}
| {{math|0}}
|| {{math|0}}
|| {{math|0}}
|-
!style="text-align:left"| {{math|1}}
| {{math|1}}
|| {{math|1 + ''α''}}
|| {{math|''α''}}
|-
!style="text-align:left"| {{math|''α''}}
|| {{math|''α''}}
|| {{math|1}}
|| {{math|1 + ''α''}}
|-
!style="text-align:left"| {{math|1 + ''α''}}
|| {{math|1 + ''α''}}
|| {{math|''α''}}
|| {{math|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 <math>x</math> by <math>y</math>, the values of <math>x</math> must be read in the left column, and the values of <math>y</math> in the top row. (Because <math>0 \cdot z = 0</math> for every <math>z</math> in every [[Ring (mathematics)|ring]] the [[division by 0]] has to remain undefined.) From the tables, it can be seen that the additive structure of <math>\mathrm{GF}(4)</math> is isomorphic to the [[Klein four-group]], while the non-zero multiplicative structure is isomorphic to the group <math>Z_3</math>.

The map
<math display="block"> \varphi:x \mapsto x^2</math>
is the non-trivial field automorphism, called the [[#Frobenius automorphism and Galois theory|Frobenius automorphism]], which sends <math>\alpha</math> into the second root <math>1+\alpha</math> of the above-mentioned irreducible polynomial <math>X^2+X+1</math>.

=== GF(''p''<sup>2</sup>) for an odd prime ''p'' ===
For applying the [[#Non-prime fields|above general construction]] of finite fields in the case of <math>\mathrm{GF}(p^2)</math>, one has to find an irreducible polynomial of degree 2. For <math>p=2</math>, this has been done in the preceding section. If <math>p</math> is an odd prime, there are always irreducible polynomials of the form <math>X^2-r</math>, with <math>r</math> in <math>\mathrm{GF}(p)</math>.

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

Having chosen a quadratic non-residue <math>r</math>, let <math>\alpha</math> be a symbolic square root of <math>r</math>, that is, a symbol that has the property <math>\alpha^2=r</math>, in the same way that the complex number <math>i</math> is a symbolic square root of <math>-1</math>. Then, the elements of <math>\mathrm{GF}(p^2)</math> are all the linear expressions
<math display="block">a+b\alpha,</math>
with <math>a</math> and <math>b</math> in <math>\mathrm{GF}(p)</math>. The operations on <math>\mathrm{GF}(p^2)</math> are defined as follows (the operations between elements of <math>\mathrm{GF}(p)</math> represented by Latin letters are the operations in <math>\mathrm{GF}(p)</math>):
<math display="block">\begin{align}
-(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{align}</math>

=== GF(8) and GF(27) ===
The polynomial
<math display="block">X^3-X-1</math>
is irreducible over <math>\mathrm{GF}(2)</math> and <math>\mathrm{GF}(3)</math>, that is, it is irreducible [[modulo]] <math>2</math> and <math>3</math> (to show this, it suffices to show that it has no root in <math>\mathrm{GF}(2)</math> nor in <math>\mathrm{GF}(3)</math>). It follows that the elements of <math>\mathrm{GF}(8)</math> and <math>\mathrm{GF}(27)</math> may be represented by [[expression (mathematics)|expressions]]
<math display="block">a+b\alpha+c\alpha^2,</math>
where <math>a, b, c</math> are elements of <math>\mathrm{GF}(2)</math> or <math>\mathrm{GF}(3)</math> (respectively), and <math>\alpha</math> is a symbol such that 
<math display="block">\alpha^3=\alpha+1.</math>

The addition, additive inverse and multiplication on <math>\mathrm{GF}(8)</math> and <math>\mathrm{GF}(27)</math> may thus be defined as follows; in following formulas, the operations between elements of <math>\mathrm{GF}(2)</math> or <math>\mathrm{GF}(3)</math>, represented by Latin letters, are the operations in <math>\mathrm{GF}(2)</math> or <math>\mathrm{GF}(3)</math>, respectively:
<math display="block">
\begin{align}
-(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{align}
</math>

=== GF(16) ===
The polynomial
<math display="block">X^4+X+1</math>
is irreducible over <math>\mathrm{GF}(2)</math>, that is, it is irreducible modulo <math>2</math>. It follows that the elements of <math>\mathrm{GF}(16)</math> may be represented by [[expression (mathematics)|expressions]]
<math display="block">a+b\alpha+c\alpha^2+d\alpha^3,</math>
where <math>a,b,c,d</math> are either <math>0</math> or <math>1</math> (elements of <math>\mathrm{GF}(2)</math>), and <math>\alpha</math> is a symbol such that 
<math display="block">\alpha^4=\alpha+1</math>
(that is, <math>\alpha</math> is defined as a root of the given irreducible polynomial).  As the characteristic of <math>\mathrm{GF}(2)</math> is <math>2</math>, each element is its additive inverse in <math>\mathrm{GF}(16)</math>.  The addition and multiplication on <math>\mathrm{GF}(16)</math> may be defined as follows; in following formulas, the operations between elements of <math>\mathrm{GF}(2)</math>, represented by Latin letters are the operations in <math>\mathrm{GF}(2)</math>.
<math display="block">
\begin{align}
(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{align}
</math>

The field <math>\mathrm{GF}(16)</math> has eight [[primitive element (finite field)|primitive elements]] (the elements that have all nonzero elements of <math>\mathrm{GF}(16)</math> as integer powers). These elements are the four roots of <math>X^4+X+1</math> and their [[multiplicative inverse]]s. In particular, <math>\alpha</math> is a primitive element, and the primitive elements are <math>\alpha^m</math> with <math>m</math> less than and [[coprime]] with <math>15</math> (that is, 1, 2, 4, 7, 8, 11, 13, 14).