Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
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 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.

share|improve this answer
    
Explaining the $(0010)$ notation could come earlier in the response. Kudos for the rest. –  fgrieu Jul 7 at 6:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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