Ch 4: Finite Fields

Groups, Rings and Fields

A group is sometimes noted <<latex($\{G, \cdot\}$)>>. Where G is the set of elements and the dot is a binary operator. A group can also be an abelian group, ring, commutative ring, integral domain or field, each of which has additional restrictions. Here we give those restrictions:

Group

Abelian Group adds

Ring adds

Commutative ring adds

Integral Domain

Field adds

Modular Arithmetic

You should know about ModularArithmetic by now. If not research it and submit something for the topic. We only give one notation sample. We say that two integers a and b are said to be congruent modulo n, if <<latex($(a mod n) = (b mod n)$)>>. This is written as <<latex($a \equiv b (\bmod n)$)>>

Euclid's Algorithm

Euclid's algorithm is used to find the GCD of two numbers 

EUCLID(a,b)
While b!=0 {
   r = a mod b
   a = b
   b = a
}
return a

Finite Fields of the form GF(p)

GF stands for Galois Field and p is a prime number.

If you have a field with p elements 0..p-1 and define + and * modulo p, then you have a field. Everything in this field uses normal addition and multiplication modulo p.

We can use an extended EUCLID(m,b) to find the both the GCD and the inverse in the GF(p). 

EXTENDED EUCLIDS[m,b]
A = [1,0,m]
B = [0,1,b]
while (B[3]>1) {
  q = quotient(A[3]/B[3])
  T = A-qB
  A = B
  B = T
}
if B[3] = 0 return (gcd=A[3]) and ("No inverse")
if B[3] = 1 return (gcd=B[3]) and (inverse = " + B[2])

Polynomial Arithmetic

You should already know how to do PolynomialArithmetic, but if you don't study up and put it in the link above. We give just a few terms related to Section 4.5.

Polynomial Arithmetic with Coefficients in Z_P

Addition and subtraction are easy because we are just doing modular addition 

   x^3 + x^2 +   + 2
  +      x^2 - x + 3
   -----------------
   x^3 +2x^2 - x + 5   In Z_2 is x^3+x+1

Subtraction, multiplication and division are very similar except you may add P to the negative value to get a number in Z_p and then add for addition. Multiplication requires a possible table lookup or calculation, and division requires the knowledge of inverses which will also require a table look up.

Definition: A polynomial latex2($f(x)$) is irreducible if and only if latex2($f(x)$) cannot be expressed as a product of two polynomials, both over F, and both of degree lower than that of latex2($f(x)$). An irreducible polynomial is called a PrimePolynomial.

Definition: The polynomial latex2($c(x)$) is said to be the greatest common divisor of latex2($a(x)$) and latex2($b(x)$) if:

  1. the function latex2($c(x)$) divides both latex2($a(x)$) and latex2($b(x)$), and

  2. any divisor of latex2($a(x)$) and latex2($b(x)$) is also a divisor of latex2($c(x)$).

Thus we can use EUCLIDS algorithm and state latex2($gcd[a(x),b(x)]=gcd[b(x),a(x)\bmod b(x)])$). And we state the algorithm as: 

EUCLID[a(x),b(x)] //for polinomials a and b.
while (b(x) != 0) {
  r(x)=a(x) mod b(x)
  b(x)=r(x)
}
return a(x)

Finite Fields of the form GF(2^n)

Here we are not dealing with the number 0 to 2^n-1 but the bit patterns represented by 00..0 to 11..1. These are elements of the set in the field. And we define addition subtraction etc to form a field.

Modular Plynomial Arithmetic

Consider the set S of polynomials of degree n-1 or less over the field latex2($Z_p$). There are a total of latex2($p^n$) different polynomials in S. With appropriate definitions of arithmetic operations, each such set S is a finite field. In fact it will be a Galios Field.

  1. Arithmetic follows the ordinary rules of polynomial arithmetic with the following two refinements.

  2. Arithmetic on the coefficients is performed modulo p. That is, we use the rules of arithmetic for the finite field latex2($Z_p$).

  3. If multiplication results in a polynomial of degree greater than n-1, then the polynomial is reduced modulo some irreducible polynomial latex2($m(x)$) of degree n. For a polynomial latex2($f(x)$), the remainder is expressed as latex2($r(x) = f(x) \bmod m(x)$).

To find the GCD of two numbers in latex2($G\left( 2^n \right)$), we can use EUCLIDS algorithm: 

EUCLIDS[a(x), b(x)]
while (a(x) != 0)
  r(x) = a(x) mod b(x)
  a(x)=b(x)
  b(x)=r(x)
return gcd=A(x).

To find the inverse (and the gcd) we use Euclid's extended algorithm where latex2($m(x)$) is the non-reducible "prime" polynomial that we use for modulus. and latex2($b(x)$) is the polynomial we wish to find the inverse for. Let a = [a1,a2,a3], and b = [b1,b2,b3] 

EXTENDED EUCLIDS[m(x),b(x)]
a = [1,0,m(x)]
b = [0,1,b(x)]
while (b.b3>1) {
  q = quotient(a.a3/b.b3)
  t = a-qb
  a = b
  b = t
}
if b.b3 = 0 return [gcd=a.a3] and ["No inverse"]
if b.b3 = 1 return [gcd=b.b3] and ["inverse = " + b.b2]

Computational Considerations

In a latex2($G\left(2^n\right)$), We have seen that addition (and subtraction) can be done using the XOR operation. Multiplication was described above, but we can look at latex2($G\left(2^8\right)$) and define multiplication as follows.

Let the Galois field be defined by the set of polynomials of degree of 7 using a prime polynomial of latex2($m(x)=x^8 + x^4 + x^3 + x + 1$). Addition/subtraction is defined in terms of XOR and multiplication is defined as: 

\begin{equation}
x\times f(x)=\left\{
\begin{array}{ll}
b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0 & if~~b_{7}=0 \\
\left( b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0\right) \oplus \left(
00011011\right)  & if~~b_{7}=1
\end{array}
\right.
\end{equation}