# Addition and multiplication table for GF(2²)

I'm reading Joan Daemen and Vincent Rijmen's book The Design of Rijndael and I'm giving myself a refresher course on group theory.

Key to the encryption standard is the Galois field on 256 elements GF(28). A multiplication table of 256 elements by 256 elements quickly becomes a wall of text, so let's reason by analogy and look at GF(22).

There are a number of ways to represent elements of the field; we'll start by representing them as polynomials with degree at most 1, and with integer coefficients modulo 2. There are four such polynomials: {0, 1, x, x + 1}.

Here are the addition and multiplication tables:

 + 0 1 x x + 1 0 0 1 x x + 1 1 1 0 x + 1 x x x x + 1 0 1 x + 1 x + 1 x 1 0

 ⋅ 0 1 x x + 1 0 0 0 0 0 1 0 1 x x + 1 x 0 x x2 mod m x2 + x mod m x + 1 0 x + 1 x2 + x mod m x2 + 1 mod m

Hold on. What's that funny-looking m?

It's a "reduction polynomial" which brings the product back down to degree 1 or less. It has to be a polynomial of degree 2. There are four such polynomials: let's try each and see what we get.

x2
 0 x x 1
x2 + 1
 1 x + 1 x + 1 0
x2 + x
 x 0 0 x + 1
x2 + x + 1
 x + 1 1 1 x

Note that the first three polynomials all factor into products of lower-degree polynomials: x2 = x(x), x2 + 1 = (x + 1)(x + 1), x2 + x = x(x + 1). Only x2 + x + 1 is prime; and this prime reduction polynomial generates a complete multiplication table with no 0s. This is a necessary condition to be a field. Our final tables are:

 + 0 1 x x + 1 0 0 1 x x + 1 1 1 0 x + 1 x x x x + 1 0 1 x + 1 x + 1 x 1 0

 ⋅ 0 1 x x + 1 0 0 0 0 0 1 0 1 x x + 1 x 0 x x + 1 1 x + 1 0 x + 1 1 x

We can also write our elements in binary form: 0 => 00, 1 => 01, x => 10, and x + 1 => 11. In this notation our tables become:

 + 00 01 10 11 00 00 01 10 11 01 01 00 11 10 10 10 11 00 01 11 11 10 01 00

 ⋅ 00 01 10 11 00 00 00 00 00 01 00 01 10 11 10 00 10 11 01 11 00 11 01 10

Rijndael works in GF(28) and uses a reduction polynomial of x8 + x4 + x3 + x + 1. They say this is prime. I sure hope so.

Tags

1. Note that the + table for the binary notation is just XOR.

2. lorenzo says:

you suck!

3. Sorry I upset you; can you elaborate?

4. Lipsha says:

how to do that multiplication operation?

5. sahin says:

There are many ways to check that m(x) = x^8 + x^4 + x^3 + x + 1 is irreducible (prime). The one that is probably easiest to understand is as follows: every polynomial is a product of irreducible polynomials, so it suffices to produce a list of irreducible polynomials of degrees 1 up to 4 and to check by polynomial division that none of them divides m(x) without remainder. These polynomials are x, x+1, x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1, x^4 + x + 1, x^4 + x^3 + 1 and x^4 + x^3 + x^2 + x + 1. To verify this list, just write all the polynomials up to degree 4 down and check which ones are divisible by a polynomial of smaller degree.

Anyone can tell me

How we Construct a Multiplication table of GF(2^3)

(This comment is best viewed in a fixed-width font)

GF(2^3)

Addition is easy, as it is just XOR:

000 001 010 011 100 101 110 111

001 000 011 010 101 100 111 110

010 011 000 001 110 111 100 101

011 010 001 000 111 110 101 100

100 101 110 111 000 001 011 011

101 100 111 110 001 000 011 010

110 111 100 101 010 011 000 001

111 110 101 100 011 010 001 000

Multiplication: we need to find a reduction polynomial. See this post for using sieving to find all the monic prime polynomials for GF(p^n):

blogs.msdn.com/…/sieving-irreducible-monic-polynomials-over-a-finite-field.aspx

As it turns out, there are two possible reduction polynomials, which are those monic prime polynomials of degree n:

x^3 + x + 1

x^3 + x^2 + 1

We'll choose the smaller of the too: x^3 + x + 1. This induces the following multiplication table:

001 010 011 100 101 110 111

010 100 110 011 001 111 101

011 110 101 111 100 001 010

100 011 111 110 010 101 001

101 001 100 010 111 011 110

110 111 001 101 011 010 100

111 101 010 001 110 100 011

As an example, here's the calculation of the 100 * 100 = 110 entry:

x + 0          R x^2 + x + 0

+————–

x^3 + 0x^2 + x + 1|x^4

x^4 + 0x^3 + x^2 + x + 0

0x^3 + x^2 + x + 0

Check:

x^4 =? x(x^3 + x + 1) + (x^2 + x + 0)

=? (x^4 + x^2 + x) + (x^2 + x)

= x^4

Yup.

If we had chosen x^3 + x^2 + 1, we would have gotten a different multiplication table, but the uniqueness of GF(p^n) implies that this is just a relabeling of the same eight elements.

8. Sandeep says:

1. kartik says:

multiply both the numbers in their polynomial form,
divide by the irreducible polynomial
and take the remainder.

9. Ashlin says:

TRULY INFORMATIVE SIR.
THANKS A LOT.

10. zetsubou says: