Inversion in $GF(2^8)$ AES I was wondering how you would calculate the S-box in AES. I found that you have to calculate the inverse of the polynomials in $GF(2^8)$. I found out that to calculate the inverse, you have to use the Extended Euclidean Algorithm. What I can't figure out is how do you apply this to a polynomial?
One neat trick for the AES Sbox is to use logarithm. In that specific field, the value 3 (0x03) is a multiplicative generator for the non-zero elements. Thus, if you have a "multiplication by 0x03" function, you can compute a mapping $n \mapsto \mathrm{\texttt{03}}^n$ for all $0 \le n \le 254$; this would be an "exponentiation table". From that table, you can make the inverse mapping as another table, which would be a "logarithm tables". By going to logarithms, you transform multiplications into additions modulo 255, and divisions into subtractions modulo 255. In particular, inversion becomes negation.

In Java code, this may look like this:

    /*
     * Make tmp[n] = pow(0x03, n) in the field.
     */
    int[] tmp = new int[255];
    for (int i = 0, x = 1; i &lt; 255; i ++) {
            tmp[i] = x;

            /*
             * Multiply x by 0x03 in the field.
             */
            int x2 = x &lt;&lt; 1;
            x2 ^= -(x2 &gt;&gt; 8) &amp; 0x11B;
            x ^= x2;
    }

    /*
     * Make Sbox[] as the inverse table. We use the fact that
     * 1/pow(0x03,n) = pow(0x03,255-n) in the field (since 0x03 is
     * a generator of the multiplicative subgroup of size 255).
     */
    Sbox = new int[256];
    Sbox[0] = 0; Sbox[1] = 1;
    for (int i = 1; i &lt; 255; i ++) {
            Sbox[tmp[i]] = tmp[255 - i];
    }

    /*
     * At that point, SBox[i] contains the inverse of i.
     * Now we apply the affine transform in GF(2).
     */
    for (int i = 0; i &lt; 256; i ++) {
            int x = Sbox[i];
            x |= x &lt;&lt; 8;
            x ^= (x &gt;&gt; 4) ^ (x &gt;&gt; 5) ^ (x &gt;&gt; 6) ^ (x &gt;&gt; 7);
            Sbox[i] = (x ^ 0x63) &amp; 0xFF;
    }


This kind of code can be convenient to recompute the S-box and related tables during an initialization process (assuming that you prefer the extra startup cost over the size cost of embedding the tables in the code).

(Of course, table-based AES implementations are not constant-time, you should not do that in practice, etc.)