questions about AES irreducible polynomials

Question

For galois field GF(2^8), the polynomial's format is a7x^7+a6x^6+...+a0.

For AES, the irreducible polynomial is x^8+x^4+x^3+x+1.

Apparently, the max power in GF(2^8) is x^7, but why the max power of irreducible polynomial is x^8?

How will the max power in irreducible polynomial affect inverse result in GF?

Can I set the max power of irreducible polynomial be x^9?

Answer 1

To understand why the modulus of GF(2⁸) must be order 8 (that is, have 8 as its largest exponent), you must know how to perform polynomial division with coefficients in GF(2), which means you must know how to perform polynomial division in general. I will assume you know how to do those things. If you don't know how, there are many tutorials on the web from which you can learn.

Remember that if r = a mod m, it means that there is a q such that a = q m + r. To make a working GF(2⁸) arithmetic, we need to guarantee that r is a element of GF(2⁸) for any a and q (even though a and q do not need to be elements of GF(2⁸)). Furthermore, we need to ensure that r can be any element of GF(2⁸), if we pick the right a from GF(2⁸).

So we must pick a modulus (the m) that makes these guarantees. We do this by picking an m of exactly order 8.

If the numerator of the division (the a in a = q m + r) is order 8 or higher, we can find something to put in the quotient (the q) that, when multiplied by x⁸, cancels out that higher order. But there's nothing we can put in the quotient that can be multiplied by x⁸ to give a term with order less than 8, so the remainder (the r) can be any order up to and including 7.

Let's try a few examples of polynomial division with a modulus (or divisor) of x⁸+x⁴+x³+x+1 to see what I mean. First let's compute x⁸+1 mod x⁸+x⁴+x³+x+1:

                1            <- quotient
             ┌──────────────
x⁸+x⁴+x³+x+1 │ x⁸        +1
             -(x⁸+x⁴+x³+x+1)
             ───────────────
                  x⁴+x³+x    <- remainder

So x⁸+1 mod x⁸+x⁴+x³+x+1 = x⁴+x³+x.

Next let's compute x¹²+x⁹+x⁷+x⁵+x² mod x⁸+x⁴+x³+x+1.

               x⁴ +x +1                      <- quotient
             ┌──────────────────────────────
x⁸+x⁴+x³+x+1 │ x¹²+x⁹   +x⁷+x⁵      +x²
             -(x¹²   +x⁸+x⁷+x⁵+x⁴      )
             ───────────────────────────
                   x⁹+x⁸      +x⁴   +x²
                 -(x⁹      +x⁵+x⁴   +x²+x)
                 ─────────────────────────
                      x⁸   +x⁵         +x
                    -(x⁸      +x⁴+x³   +x+1)
                    ────────────────────────
                            x⁵+x⁴+x³     +1  <- remainder

So x¹²+x⁹+x⁷+x⁵+x² mod x⁸+x⁴+x³+x+1 = x⁵+x⁴+x³+1, which has order < 8.

Finally, let's try a substantially higher order: how about x¹⁰⁰+x⁹⁶⁺x⁹⁵+x⁹³+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x mod x⁸+x⁴+x³+x+1?

               x⁹²             +x⁸⁴                    <- quotient
             ┌────────────────────────────────────────
x⁸+x⁴+x³+x+1 │ x¹⁰⁰+x⁹⁶⁺x⁹⁵+x⁹³    +x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x
             -(x¹⁰⁰+x⁹⁶+x⁹⁵+x⁹³+x⁹²                  )
             ─────────────────────────────────────────
                                x⁹²+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x
                              -(x⁹²+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴  )
                              ────────────────────────
                                                    x  <- remainder

So x¹⁰⁰+x⁹⁶⁺x⁹⁵+x⁹³+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x mod x⁸+x⁴+x³+x+1 = x. Note that I carefully chose the numerator so that it wouldn't be a long computation. If you want some pain, try doing x¹⁰⁰ mod x⁸+x⁴+x³+x+1 by hand.