Editing Finite field arithmetic (section)

==Effective polynomial representation==
The finite field with ''p''<sup>''n''</sup> elements is denoted GF(''p''<sup>''n''</sup>) and is also called the '''Galois field''' of order ''p''<sup>''n''</sup>, in honor of the founder of finite field theory, [[Évariste Galois]]. GF(''p''), where ''p'' is a prime number, is simply the [[ring (algebra)|ring]] of integers [[Modular arithmetic|modulo]] ''p''. That is, one can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulo ''p''. For instance, in GF(5), {{nowrap|1=4 + 3 = 7}} is reduced to 2 modulo 5. Division is multiplication by the inverse modulo ''p'', which may be computed using the [[extended Euclidean algorithm]].

A particular case is [[GF(2)]], where addition is [[XOR gate|exclusive OR]] (XOR) and multiplication is [[AND gate|AND]]. Since the only invertible element is 1, division is the [[identity function]].

Elements of GF(''p''<sup>''n''</sup>) may be represented as [[polynomial]]s of degree strictly less than ''n'' over GF(''p''). Operations are then performed modulo ''m(x)'' where ''m(x)'' is an [[irreducible polynomial]] of degree ''n'' over GF(''p''), for instance using [[polynomial long division]]. Addition is the usual addition of polynomials, but the coefficients are reduced modulo ''p''. Multiplication is also the usual multiplication of polynomials, but with coefficients multiplied modulo ''p'' and polynomials multiplied modulo the polynomial ''m(x)''.<ref>{{harvnb|Hankerson|Vanstone|Menezes|2004|loc=p. 28}}</ref> This representation in terms of polynomial coefficients is called a [[monomial basis]] (a.k.a. 'polynomial basis').

There are other representations of the elements of GF(''p''<sup>''n''</sup>); some are isomorphic to the polynomial representation above and others look quite different (for instance, using matrices). Using a [[normal basis]] may have advantages in some contexts.

When the prime is 2, it is conventional to express elements of GF(''p''<sup>''n''</sup>) as [[binary numeral system|binary numbers]], with the coefficient of each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "{" and "}" ) or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value gives the coefficients of a basis of a field, thus representing an element of the field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:

{| class="wikitable"
|-
! Polynomial
| ''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1
|-
! Binary
| {01010011}
|-
! Hexadecimal
| {53}
|}