# Generate Finite Field power of g

consider the field $\mathbb{F}_{2^4}$, defined by using polynomial representation with the irreducible polynomial $f(x) = x^4 + x + 1$.

Given element $g = (0010)$ as a generator for the field, How are the powers of g generated? What are the steps to generate the binary values of $g^0$ to $g^{15}$ as follows?

$g^0 = (0001)$, $g^1 = (0010)$, $g^2 = (0100)$, $g^3 = (1000)$, $g^4 = (0011)$, $g^5 = (0110)$, $g^6 = (1100)$, $g^7 = (1011)$, $g^8 = (0101)$, $g^9 = (1010)$, $g^{10} = (0111)$, $g^{11} = (1110)$, $g^{12} = (1111)$, $g^{13} = (1101)$, $g^{14} = (1001)$, $g^{15} = (0001)$.

• Is the question "what is meant by the notation $g^x$"? Or, is the question "how do you do multiplication in the field $GF(16)$"? – poncho Jul 6 '14 at 15:43

To answer this, let's look at what the elements of $\mathbb{F}_{2^4}$ are: polynomials with coefficients in $\mathbb{F}_2$ that are reduced modulo $f(x)=x^4+x+1$. This reduction means that any power of $x$ greater than or equal to $x^4$ can be rewritten as a sum of smaller powers: in particular, $x^4=x+1$, and higher powers we can factor this $x^4$ out first. Using this, our elements are of the form $a_3x^3+a_2x^2+a_1x+a_0$, where each $a_j$ is either $0$ or $1$. Now, if we take an element of our field, say $g=0x^3+0x^2+1x+0=x$, we can compute powers of $g$ by repeated multiplication:
• $g^0=1$
• $g^1=x$
• $g^2=x^2$ and so on.
When we take higher powers, this starts getting interesting. For $g^4=x^4$, we can reduce our element mod $f(x)$, and we get $g^4=x+1$. We can continue from here and get $g^5=g\cdot g^4=x\cdot(x+1)=x^2+x$. At $g^7$, we have $x^4+x^3$, which we once again reduce and get $x^3+x+1$; $g^8=x^4+x^2+x$ which reduces to $x^2+1$.
Your question asks how we can compute powers of a generator $g=(0010)$, so let's examine what the notation $(0010)$ means in this case. As mentioned above, our elements are of the form $a_3x^3+a_2x^2+a_1x+a_0$. We can identify this polynomial with its list of coefficients, $(a_3a_2a_1a_0)$, so that $1=(0001)$, $x=(0010)$, $x+1=(0011)$, and so forth. In your particular example, you have $g=(0010)$, which is just $x$. Then $g^2=x^2$ like before, which converts to the list $(0100)$. So to calculate these, what we do is convert to polynomial form, do the polynomial arithmetic described above, and convert back to a list of coefficients.
• Explaining the $(0010)$ notation could come earlier in the response. Kudos for the rest. – fgrieu Jul 7 '14 at 6:27