Ch 4: Finite Fields

Groups, Rings and Fields

A group is sometimes noted $$\{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

• Closure under addition
• Associativity of addition
• Additive identity
• Additive inverse

Abelian Group adds

• Commutativity of addition

Ring adds

• Closure under multiplication
• Associativity of multiplication
• Distributive laws

Commutative ring adds

• Commutativitiy of multiplication

Integral Domain

• Multiplicative Identity
• No zero divisors (note that by adding multiplication in a finite group, we automatically define the ability to divide because we can define division of a/b=c as b*c=a. What we don't know is if c exists. To get around the divide by zero problem we restrict the notion of division to exclude a divisor of zero.

Field adds

• Multiplicative inverse.

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 $$ (a~mod~n) = (b~mod~n) $$. This is written as $$a \equiv b (b~mod~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.

• An nth degree polynomial is said to be monic if $$a_n = 1$$.
• When someone says indeterminate they are just refering to x.

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 $$f(x)$$ is irreducible if and only if $$f(x)$$ cannot be expressed as a product of two polynomials, both over F, and both of degree lower than that of $$f(x)$$. An irreducible polynomial is called a PrimePolynomial.

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

1. the function $$c(x)$$ divides both $$a(x)$$ and $$b(x)$$, and
2. any divisor of $$a(x)$$ and $$b(x)$$ is also a divisor of $$c(x)$$.

Thus we can use EUCLIDS algorithm and state $$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 $$Z_p$$). There are a total of $$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 $$Z_p$$.

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

To find the GCD of two numbers in $$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 $$m(x)$$ is the non-reducible "prime" polynomial that we use for modulus. and $$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

Consider $$G(2^n)$$. We have seen that addition and subtraction can be done using the '''XOR''' operation. Multiplication was described above, but we can look at $$G(2^8)$$ 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 $$m(x) = x^8 + x^4 + x^3 + x+1 $$

Addition/subtraction is defined in terms of XOR and multiplication is defined as: $$$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 \\ (b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}0) \oplus (00011011) & if~~b_{7}=1 \\ \end{array} \right.$$$