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)$.

  • 2
    $\begingroup$ 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)$"? $\endgroup$
    – poncho
    Jul 6, 2014 at 15:43

1 Answer 1


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.

  • $\begingroup$ Explaining the $(0010)$ notation could come earlier in the response. Kudos for the rest. $\endgroup$
    – fgrieu
    Jul 7, 2014 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.