Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search