(Last Mod: *
27 November 2010 21:38:01
)*

In most applications where a Galois field is employed it is of the form GF(2* ^{n}*).
The main reason is convenience. Since math on the polynomial coefficients is
done in GF(2), the operations can be converted to binary logic circuits very
readily. Furthermore, since there are exactly 2

It is assumed that the you have either worked through the page on
Polynomial Arithmetic in GF(p^{n}) or
you will be doing so in parallel with this page. To make this easier, this page
is laid in a similar fashion.

Recall from the discussion of finite fields, that a finite field is an algebra consisting of a set of elements and two operators that act on those elements. We are free to define the elements and the operators in any way we choose provided the properties required of a finite field are satisfied. Those requirements are:

- The set must be an abelian group with respect to the first operator.
- The set, less the identity element for the first operator, must be an abelian group with respect to the second operator.
- The second operator must be distributive over the first operator.

Further recall that to be an abelian group, the following properties must hold with respect to the operator:

- The set must be closed.
- The set must be commutative.
- The set must be associative.
- The set must possess an identity element.
- The set must possess an inverse for every element in the set.

There are nine symbols in GF(3^{2}) which we can represent as the
following polynomials:

Elementary Polynomials in GF(3^{2})

Symbol |
Polynomial |

00 | 0 |

01 | 1 |

02 | 2 |

10 | D |

11 | D+1 |

12 | D+2 |

20 | 2D |

21 | 2D+1 |

22 | 2D+2 |

We also need a "primitive polynomial" which, for GF(*p ^{n}*) is a
polynomial of order

Since primitive polynomials must be irreducible, the high order coefficient
must be one and the constant coefficient must be non-zero. In GF(3^{2})
this leaves us with only the following six candidates.

Candidate Primitive Polynomials in GF(3^{2})

Symbol |
Polynomial |

101 | D^{2} + 1 |

102 | D^{2} + 2 |

111 | D^{2} + D+1 |

112 | D^{2} + D+2 |

121 | D^{2} + 2D+1 |

122 | D^{2} + 2D+2 |

We could examine each of the candidate polynomials in turn and divide it by each of the potentially irreducible polynomials of order less than n, of which there are only two.

Lower Order Irreducible Polynomials <2 in GF(3^{2})

Symbol |
Polynomial |

11 | D+1 |

12 | D+2 |

With so few candidates for primitive polynomials and so few lower order irreducible polynomials to work with, an exhaustive search of the space is very straightforward. We will examine three candidates using this approach before turning to the other approach.

## Example: Is 101 (

D^{2}+ 1) a primitive polynomial in GF(3^{2})

- Dividing
D^{2}+ 1 byD+ 1 yieldsD+ 2 with a remainder of 2.- Dividing
D^{2}+ 1 byD+ 2 yieldsD+ 1 with a remainder of 2.Since both have non-zero remainders,

D^{2}+ 1 is an irreducible polynomial.The question now is whether

D^{2}+ 1 is primitive.One way to show this is that the smallest value for which

D^{2}+ 1 evenly dividesD- 1 is^{m}m=p- 1 = 8.^{n}A comparable way is to show that

Dgenerates all of the polynomials in the set. We will pursue this latter course.^{k}

kD^{k}PolynomialSymbol0 D ^{0}1 01 1 D ^{1}D 10 2 D ^{2}2 02 3 D ^{3}2D 20 4 D ^{4}1 01 5 D ^{5}D 10 6 D ^{6}2 02 7 D ^{7}2D 20 8 D ^{8}1 01 As can be seen, not all of the polynomials in the set are generated as evidenced by

D^{4}generating 1 again and hence creating a cycle of generated polynomials with period of 4. So, whileD^{2}+ 1 dividesD^{8}- 1, also also dividesD^{4}- 1.Therefore, 101 (

D^{2}+1) is not a primitive polynomial in GF(3^{2}).

## Example: Is 102 (

D^{2}+ 2) a primitive polynomial in GF(3^{2})

- Dividing
D^{2}+ 2 byD+ 1 yieldsD+ 2 with no remainder.Hence

D^{2}+ 2 is reducible and need not be explored further.Therefore, 102 (

D^{2}+ 2) is not a primitive polynomial in GF(3^{2}).

## Example: Is 112 (

D^{2}+D+ 1) a primitive polynomial in GF(3^{2})

- Dividing
D^{2}+D+ 2 byD+ 1 yieldsDwith a remainder of 2.- Dividing
D^{2}+D+ 2 byD+ 2 yieldsD+ 2 with a remainder of 1.Since both have non-zero remainders,

D^{2}+D+ 2 is an irreducible polynomial.The question now is whether

D^{2}+D+ 2 is primitive. As before, we will see ifDgenerates the entire set under this modulus.^{k}

kD^{k}PolynomialSymbol0 D ^{0}1 01 1 D ^{1}D 10 2 D ^{2}2D + 1 21 3 D ^{3}2D + 2 22 4 D ^{4}2 02 5 D ^{5}2D 20 6 D ^{6}1D + 2 12 7 D ^{7}D + 1 11 8 D ^{8}1 01 As can be seen, all of the polynomials in the set are generated, as evidenced by

D^{8}being the first time (afterD^{0}) that 1 is generated.Therefore, 112 (

D^{2}+D+ 2) is a primitive polynomial in GF(3^{2}).

The other approach is to finding the irreducible polynomials is to first
produce a list of all of the candidate degree-n primitive polynomials and then
multiply all of the lower degree polynomials together to produce all of the
non-irreducible polynomials of degree *n* and eliminate these from the
list. The initial list is the same as in the previous approach, namely:

Candidate Primitive Polynomials in GF(3^{2})

Symbol |
Polynomial |

101 | D^{2} + 1 |

102 | D^{2} + 2 |

111 | D^{2} + D+1 |

112 | D^{2} + D+2 |

121 | D^{2} + 2D+1 |

122 | D^{2} + 2D+2 |

In the case of *n*=2, the polynomials of degree less than *n* can be written in
the form

aD + b

Multiplying two such polynomials together, our candidate primitive polynomials may be written in the form

P = (aD + b)(cD + d)

P = (ac)D^{2} + (ad+bc)D + (bd)

If we were to approach this blindly, we would have to examine 81
possibilities. However, we note that since primitive polynomials must be of order *
n*, that neither *a* nor *c* may be zero. This immediately reduces
the search space to 36. We also know that the order *n* coefficient must be
exactly 1 which means that a and c must be multiplicative inverses of each other
in GF(3). But we have also established that if the high order coefficient is
anything greater than 1 that the polynomial is reducible, hence we can restrict
our examination to lower order polynomials having an high order coefficient of
1. This means that a and c must both be exactly 1 which simplifies the form of
our primitive polynomials to:

P = (D + b)(D + d)

P = D^{2} + (d+b)D + (bd)

This collapses our search space to only 9 entries and if we impose the requirement that primitive polynomials must have a non-zero constant term then we have reduced it to 4. While this is already quite manageable, we can reduce it even further my nothing that multiplication in any field is commutative and therefore if we order the elements of our set (in any way we choose) then we can limit ourselves to only evaluating those expressions in which the second factor is greater than or equal to the first factor. The result is that we now only have to evaluate 3 expressions. Notice that a little bit of thought up front has saved us 96% of the work.

Candidate Primitive Polynomials that are Reducible in GF(3^{2})

b |
d |
b+d |
bd |
P |
symbol |

1 | 1 | 2 | 1 | D^{2}+2D+1 |
121 |

1 | 2 | 0 | 2 | D^{2}+2 |
102 |

2 | 2 | 1 | 1 | D^{2}+D+1 |
111 |

After eliminating these from the original list, we now have the complete list
of polynomials of degree *n* that are irreducible. There are now only three remainingcandidates for being primitive
polynomials in GF(3^{2}):

Irreducible Candidates for Primitive Polynomials in GF(3^{2})

Symbol |
Polynomial |

101 | D^{2} + 1 |

112 | D^{2} + D+2 |

122 | D^{2} + 2D+2 |

The only remaining task is to see which of these three is/are actually
primitive. We have the same tools as with the prior approach and might as well
note that two of the three (101 and 112) were evaluated previously with the
result that 101 is not primitive while 112 is. At this point we could either go
ahead and check 122 to see if it is primitive or we could check how many
primitive polynomials there are in GF(3^{2}) and let that guide us.
Let's do both.

In GF(32), the number of primitive polynomials is exactly given by

N = totient(p^{n}-1)/n = 2

Since there are exactly two primitive polynomials and since we have identified only one and have only one candidate remaining, we can conclude that 122 should be a primitive polynomial; iif it isn't, then we know we have made an error somewhere. We will now verify that 122 is, indeed, primitive by seeing if it generates the entire set of polynomials under this modulus.

k |
D^{k} |
Polynomial |
Symbol |

0 | D^{0} |
1 | 01 |

1 | D^{1} |
D | 10 |

2 | D^{2} |
D + 1 | 11 |

3 | D^{3} |
2D + 1 | 21 |

4 | D^{4} |
2 | 02 |

5 | D^{5} |
2D | 20 |

6 | D^{6} |
2D + 2 | 22 |

7 | D^{7} |
D + 2 | 12 |

8 | D^{8} |
1 | 01 |

Now that we have found at least one primitive polynomial with which to define multiplication in our finite field, let us turn our attention to determining the multiplicative inverses of each non-zero element in our set. For convenience, since the table is directly above, let's use 122 as our primitive polynomial.

Since each polynomial maps to an integer power of D and since D^{8}
is 1, we can use the fact that two polynomials are multiplicative inverses if
the exponents in their exponential representations add to 8. Hence

Multiplicative Inverses in GF(3^{2}) mod 112

k |
D^{k} |
Polynomial |
Symbol |
(D)^{k}^{-1} |
Polynomial |
Symbol |

0 | D^{0} |
1 | 01 | D^{8} |
1 | 01 |

1 | D^{1} |
D | 10 | D^{7} |
D + 2 | 12 |

2 | D^{2} |
D + 1 | 11 | D^{6} |
2D + 2 | 22 |

3 | D^{3} |
2D + 1 | 21 | D^{5} |
2D | 20 |

4 | D^{4} |
2 | 02 | D^{4} |
2 | 02 |

5 | D^{5} |
2D | 20 | D^{3} |
2D + 1 | 21 |

6 | D^{6} |
2D + 2 | 22 | D^{2} |
D + 1 | 11 |

7 | D^{7} |
D + 2 | 12 | D^{1} |
D | 10 |