Diff for "Csce877Ch4Notes"

= 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

Finite Fields of the form GF(2^n)