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

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

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

Csce877Ch4Notes (last edited 2020-01-23 22:28:39 by scot)