Ch 4: Finite Fields

Groups, Rings and Fields

A group is sometimes noted latex2($\{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 latex2($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 is normal addition and multiplication modulo p.

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

EXTENDED EUCLID(m,b)
a1 = 1
a2 = 0
a3 = m
b1 = 0
b2 = 1
b3 = b
While b3 != 0 {
  if b3 = 1 return b2 mod m.
  q = floor(a3/b3)
  t1 = a1 - q*b1
  t2 = a2 - q*b2   // t = a = q*b
  t3 = a3 - q*b3

  a1 = b1
  a2 = b2          // a = b
  a3 = b3

  b1 = t1
  b2 = t2          // b = t
  b3 = t3
}
return "no inverse"

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 latex2($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 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.

Finite Fields of the form GF(2^n)