Finite Fields, Math in a Finite Field

Math in a Finite Field

If F is a finite field and K is a subfield, F is K(b), where b generates F^*, the nonzero elements of F. Thus F/K is a simple extension. Remember that b is associated with an irreducible polynomial q(x) in K, such that q(b) = 0. Usually K is set to Z_p, and the polynomial q(x) allows us to perform mathematics in the field F.

As an example, consider the field of order 9. This is an extension of the integers mod 3. Since 2 has no square root mod 3, x²+1 is an irreducible polynomial. Thus the field of order 9 consists of expressions ax+b, where a and b are integers mod 3. How can we do arithmetic in this field? Perform polynomial addition and multiplication as usual, but replace x² with 1 whenever it appears.

Of course, finding q(x) could be tricky when p and n are large. This is addressed elsewhere.