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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.