Editing Finite field (section)

=== 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.