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/

Comments (11)

Cancel reply

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

  2. Sorry I upset you; can you elaborate?

  3. Lipsha says:

    how to do that multiplication operation?

  4. 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.

  5. Muhammad Sami says:

    Anyone can tell me

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

  6. @Muhammad Sami

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

  7. Sandeep says:

    Cannot understand anything about GF(2^3) from your explanation

    1. kartik says:

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

  8. Ashlin says:

    TRULY INFORMATIVE SIR.
    THANKS A LOT.

  9. zetsubou says:

    Very helpful, thank you!

Skip to main content