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

### Inverses in the Field GF(2^8)

```
Date: 11/07/2000 at 07:12:20
From: mmcl
Subject: Multiplicative Inverse in GF(2^8)

I have a 4x4 matrix of bytes:

[B0  B4  B8   B12]
[B1  B5  B9   B13]
[B2  B6  B10  B14]
[B3  B7  B11  B15]

I need to get the multiplicative inverse of this matrix in GF(2^8). Is
this the same as obtaining the inverse of a 4x4 matrix?
```

```
Date: 11/07/2000 at 13:40:17
From: Doctor Rob
Subject: Re: Multiplicative Inverse in GF(2^8)

Thanks for writing to Ask Dr. Math.

It is just the same, as long as you do all your arithmetic in GF(2^8).

Your first job is to figure out the map that carries bytes into field
elements, and vice versa. Map the byte matrix into a field element
matrix, do the inversion, then map the result back into bytes.

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

```
Date: 11/09/2000 at 05:45:07
From: Maire McLoone
Subject: Re: Multiplicative Inverse in GF(2^8)

I would like to obtain the multiplicative inverse of each individual
byte in GF(2^8). How do I do this?
```

```
Date: 11/09/2000 at 11:28:45
From: Doctor Rob
Subject: Re: Multiplicative Inverse in GF(2^8)

Thanks for writing back.

The field GF(2^8) is usually defined in the following way. Find a
polynomial f(x) of degree 8 which is irreducible over GF(2). There are
30 of these to choose from. Then the polynomials of degree less than 8
over GF(2) form a set of size 2^8.

modulo 2), and "multiplication" is the usual multiplication of
polynomials (reducing coefficients modulo 2), followed by a reduction
modulo f(x) (and further coefficient reduction modulo 2) until the
result has degree less than 8. Using these operations, this set forms
a field isomorphic to GF(2^8).

For example, suppose the polynomial were

f(x) = x^8 + x^6 + x^5 + x + 1

which is irreducible over GF(2). Then to add x^7 + x^3 + x + 1 and
x^4 + 1, you would get x^7 + x^4 + x^3 + x + 2, and reducing the
coefficients modulo 2, you get x^7 + x^4 + x^3 + x, which is the sum.
To multiply these same polynomials, you get:

x^11 + 2*x^7 + x^5 + x^4 + x^3 + x + 1
-> x^11 + x^5 + x^4 + x^3 + x + 1
-> x^7 + x^2 + x

which is the product.

Now suppose one of the entries in your matrix is the byte 11001001.
You have to figure out whether this means

x^7 + x^6 + x^3 + 1

(so the bits from left to right are the coefficients of the powers of
x in decreasing order) or

x^7 + x^4 + x + 1

(so the bits from left to right are the coefficients of the powers of
x in increasing order). Then you have to determine what polynomial
f(x) is being used to do the arithmetic. Once you know these data, you
can construct the multiplicative inverses you seek in the following
way.

First figure out what polynomial a(x) the byte you want to invert is
equivalent to.

Given a polynomial a(x) whose inverse you seek, perform the Extended
Euclidean Algorithm on a(x) and f(x). If a(x) is not zero, you will
obtain polynomials r(x) and s(x) such that

r(x)*a(x) + s(x)*f(x) = 1

Then reduce this equation modulo f(x):

r(x)*a(x) = 1 (mod f(x))

a(x) will be the multiplicative inverse of r(x).

Example: Inverse of x^4 + 1.

x^8 + x^6 + x^5 + x + 1 = (x^4+x^2+x+1)*(x^4+1) + (x^2)
x^4 + 1 = (x^2)*(x^2) + 1

and, working backwards,

1 = 1*(x^4+1) + (x^2)*(x^2)
= 1*(x^4+1) + (x^2)*([x^4+x^2+x+1]*[x^4+1]+[x^8+x^6+x^5+x+1])
= (x^6+x^4+x^3+x^2+1)*(x^4+1) + (x^2)*(x^8+x^6+x^5+x+1)

so, reducing modulo f(x),

1 = (x^6+x^4+x^3+x^2+1)*(x^4+1) (mod f(x))

Thus the multiplicative inverse sought is x^6 + x^4 + x^3 + x^2 + 1.

You can remove the need to work backwards by keeping track of some
auxiliary quantities as you perform the Euclidean Algorithm.

Remainder        Quotient     Auxiliary
x^8+x^6+x^5+x+1               0
x^4+1                         1
x^2              x^4+x^2+x+1  x^4+x^2+x+1
1                x^2          x^6+x^4+x^3+x^2+1

The Auxiliary column always starts with 0 and 1. The Remainder column
always starts with f(x) and a(x). To fill in any subsequent row,
divide the remainders in the previous two rows, and put the quotient
in the Quotient column and the remainder in the Remainder column. Then
multiply the quotient times the Auxiliary number in the previous row
and add the Auxiliary number in the row before that, putting the
result in the Auxiliary column. When the remainder is reduced to 1,
the content of the Auxiliary column in that row is the inverse of
a(x). This is a version of the Extended Euclidean Algorithm which you

Of course, once you have the inverse, you have to convert that
polynomial back to a byte.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms
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