Editing Finite field arithmetic (section)

== Primitive polynomials ==
There are many irreducible polynomials (sometimes called '''reducing polynomials''') that can be used to generate a finite field, but they do not all give rise to the same representation of the field.

A [[Monic polynomial|monic]] [[irreducible polynomial]] of degree {{math|''n''}} having coefficients in the finite field GF({{math|''q''}}), where {{math|1=''q'' = ''p''<sup>''t''</sup>}} for some prime {{mvar|p}} and positive integer {{mvar|t}}, is called a '''primitive polynomial''' if all of its roots are [[Primitive element (finite field)|primitive elements]] of GF({{math|''q<sup>n</sup>''}}).<ref>The roots of such a polynomial must lie in an [[extension field]] of GF({{mvar|q}}) since the polynomial is irreducible, and so, has no roots in GF({{mvar|q}}).</ref><ref>{{harvnb|Mullen|Panario|2013|loc=p. 17}}</ref> In the polynomial representation of the finite field, this implies that {{mvar|x}} is a primitive element. There is at least one irreducible polynomial for which {{mvar|x}} is a primitive element.<ref>{{Cite book|title=Design and Analysis of Experiments|date=August 8, 2005|publisher=John Wiley & Sons, Ltd|pages=716–720|doi=10.1002/0471709948.app1}}</ref> In other words, for a primitive polynomial, the powers of {{math|''x''}} generate every nonzero value in the field.

In the following examples it is best not to use the polynomial representation, as the meaning of {{math|''x''}} changes between the examples. The monic irreducible polynomial {{math|''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1}} over [[GF(2)]] is not primitive. Let {{math|''λ''}} be a root of this polynomial (in the polynomial representation this would be {{math|''x''}}), that is, {{math|1=''λ''<sup>8</sup> + ''λ''<sup>4</sup> + ''λ''<sup>3</sup> + ''λ'' + 1 = 0}}. Now {{math|1=''λ''<sup>51</sup> = 1}}, so {{math|''λ''}} is not a primitive element of GF(2<sup>8</sup>) and generates a multiplicative subgroup of order 51.<ref name=LN>{{harvnb|Lidl|Niederreiter|1983|loc=p. 553}}</ref> The monic irreducible polynomial {{math|''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + 1}} over [[GF(2)]] is primitive, and all 8 roots are generators of {{math|GF(2<sup>8</sup>)}}.

All GF(2<sup>8</sup>) have a total of 128 generators (see [[Primitive element (finite field)#Number of primitive elements|Number of primitive elements]]), and for a primitive polynomial, 8 of them are roots of the reducing polynomial. Having {{math|''x''}} as a generator for a finite field is beneficial for many computational mathematical operations.