Matrix Multiplication, Finite Fields

Date: 07/13/2001 at 06:34:30
From: Saurabh Pal
Subject: Galois fields

What is matrix multiplication over the Galois field GF(2^8)?

Date: 07/13/2001 at 13:25:58
From: Doctor Rob
Subject: Re: Galois fields

Thanks for writing to Ask Dr. Math, Saurabh.

There are two concepts involved here: matrix multiplication and
Galois fields.

A matrix is a rectangular array of numbers chosen from some set. The 
set can be the complex numbers, real numbers, rational numbers, 
integers, or any "ring."  A ring is a set with two operations, 
addition [+] and multiplication [*], that obey the associative and
distributive laws, the commutative law of addition, has a 0 element, 
and has negatives. The entries of a matrix are often displayed in 
r rows and c columns, with some kind of parentheses or brackets around 
the array. For example, here is a 2-by-3 matrix of real numbers:

   [7   1/2    Pi   ]
   [0   -4   sqrt(2)].

Now two matrices can be multiplied if the one on the left has the same 
number of columns as the number of rows in the one on the right. That 
means you can multiply a k-by-m matrix times an m-by-n matrix. For 
example, you can multiply

   [7   1/2    Pi   ]   [-2/5  6   0  -1]
   [0   -4   sqrt(2)] * [  4  -2   4   3]
                        [  0  1/3  0   0],

because the left matrix has three columns and the right one has three 
rows. The result will be a k-by-n matrix (in the example, a 2-by-4 
matrix). If you consider a set of matrices with the same number of 
rows and columns, say 4-by-4 matrices, any of them can be multiplied 
by any other.

The way the matrix multiplication is done is as follows. Suppose the 
entry of the left matrix in the i-th row and j-th column is a(i,j), 
where 1 <= i <= k and 1 <= j <= m, and the entry of the right matrix 
in the j-th row and p-th column is b(j,p), where 1 <= j <= m and 
1 <= p <= n. Then the entry of the result in the i-th row and p-th 
column is given by the following expression:

    m
   SUM a(i,j)*b(j,p),  where 1 <= i <= k and 1 <= p <= n.
   j=1

This is just the dot-product of the i-th row of the a-matrix and the 
p-th column of the b-matrix. Thus the entry in the 2nd row and 3rd 
column of the product in the example above is given by

   0*0 + (-4)*4 + sqrt(2)*0 = -16.

In fact, the entire product is

   [-19/5   41-Pi/3      2  -11/2]
   [-16    8+sqrt(2)/3  -16  -12 ],

which was computed using the above rule.

A Galois field is a special kind of ring. It is a field (that is,
multiplication is commutative, it has a multiplicative identity 1,
and every element other than 0 has a reciprocal, or multiplicative
inverse). Furthermore, it has a finite number of elements. In your 
case, that finite number is 256. It turns out that the number of 
elements in any finite field must be a power p^k of a prime number p.  
256 = 2^8 satisfies that condition. Furthermore, if you don't worry 
about the names of the elements, it turns out that there is just one 
finite field with any given size. That justifies talking about *THE* 
finite field with p^k elements. This is denoted by GF(p^k).

One way to construct GF(2^8) is to start with GF(2). GF(2) can be
thought of as the set of integers reduced modulo 2 with modulo-2
addition and multiplication. Now look at the set of polynomials in the 
indeterminate x whose coefficients lie in GF(2). Find one whose degree 
is 8 and which is irreducible over GF(2), that is, one that cannot be 
factored into two polynomials of smaller degree with coefficients in 
GF(2), using coefficient arithmetic in GF(2). A polynomial that isn't 
irreducible is x^8 + 1, because

   (x^4 + 1)*(x^4 + 1) = x^4*x^4 + x^4*1 + 1*x^4 + 1*1,
                       = x^8 + x^4*(1+1) + 1,
                       = x^8 + 1

(because 1 + 1 = 0 in GF(2)). It turns out that there are 30 
irreducible polynomials from which to choose. One choice is
f(x) = x^8 + x^4 + x^3 + x + 1.

Now GF(2^8) is the set of all polynomials with coefficients in GF(2) 
whose degree is at most 7, together with the zero polynomial. Addition 
is done in the usual way, using GF(2) arithmetic on the coefficients.  
Multiplication is slightly more complicated. First the two factors are 
multiplied together using coefficient arithmetic in GF(2). That can 
give a polynomial whose degree can be as large as 14. Divide that 
product by f(x) above, finding a quotient and remainder, with the 
remainder either 0 or having degree at most 7. Do this using GF(2) 
arithmetic for the coefficients. Then the remainder is the result of 
the multiplication in GF(2^8).

Putting these ideas together, you can have matrices whose entries
are elements of GF(2^8). These can be multiplied using the same rule 
for matrix multiplication, with all the arithmetic being done in 
GF(2^8).

I hope this helps.  If you need further questions answered, write
again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/