# Addition and multiplication table for GF(2²)

This blog post has moved to https://matthewvaneerde.wordpress.com/2014/01/30/addition-and-multiplication-table-for-gf2/

Tags

1. Maurits [MSFT] says:

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

2. lorenzo says:

you suck!

3. Maurits [MSFT] says:

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.

6. Muhammad Sami says:

Anyone can tell me

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

7. Maurits [MSFT] says:

(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: