exhib power of alpha of GF(256)

Question

I have a question about the finite field extension.

We suppose that we have a field $F_2[X]$ and $f = x^8+x^4+x^3+x+1 $, so we we create the field $F_2[X]/f$ which is isomorphic to $GF(2^8)$.

I want to exhib the element of the field like the powers of alpha.

We know that $\alpha^8 = \alpha^4 + \alpha^3 + \alpha + 1$

So we can compute $\alpha^9$ with this equation: $\alpha^9 = \alpha^8 * \alpha = (\alpha^4 + \alpha^3 + \alpha + 1) * \alpha = \alpha^5 + \alpha^4 + \alpha^2 + \alpha$

I implemented an algorithm to compute all the power of $\alpha^0, \alpha, \alpha^2,... \alpha^{254}$

#define degre 8
#define order (1<<degre)
#define num 2

int main() {

    // Polynome generator of the fields (alpha and beta)
    uint8_t poly[num] = {0x1b, 0x1d};
    uint8_t element[num][order] = {};

    int i=0, j=0;

    // Generation of the elements of alpha and beta
    for(j=0; j<num; j++) {
        // special case
        element[j][0] = 0x01;

        for(i=1; i<=0xff; i++) {
            element[j][i] = (element[j][i-1]<<1);
            if(element[j][i-1]>>(degre-1)==1)
                    element[j][i] ^= poly[j];
        }
    }

for(i=0; i<256; i++)
{
    printf("(%03d,%02X)\t(%03d, %02X)\n", i, element[0][i], i, element[1][i]);
}

return 0;
}

I think my programm is correct but my problem is that the $\alpha^{51} = 1 $ with the polynomial $f = x^8+x^4+x^3+x+1 $. $f$ is irreductible so there are only $\alpha^0$ and $\alpha^{255}$ which equal to 1. Other weird thing, if I change the polynomials by $g = x^8+x^4+x^3+x^2+1 $, it works.

Have you got any explanations ?

Thank you

Answer 1

There is no reason to assume that $\alpha$ is a generator for the multiplicative cyclic group $GF(2^8)^\times$, just because it's a root of an irreducible polynomial of degree $8$.

The cyclic group $GF(2^8)^\times$ has $255$ elements, which means it has $128$ different possible generators. However, there are $2^8-2^4=240$ elements in $GF(2^8)$ that are not elements of any proper subfield, meaning that they alone generate $GF(2^8)$ as a field over $GF(2)$. ($GF(2^8)$ has a single subfield isomorphic to $GF(2^4)$, and any element not in that subfield will generate $GF(2^8)$ over $GF(2)$.)

In other words, there are $112$ elements of $GF(2^8)$ that are roots of irreducible degree 8 polynomials in $GF(2)[x]$ whose powers do not reach all of $GF(2^8)\setminus\{0\}$.

Your $\alpha$ might just happen to be one of those.