Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a field F(2^4) and it is represented as a residue ring of the polynomials over F2 modulo the polynomial β4+β3+β2+β+1.

I want to express each element in this field as a power of a primitive element β+1.

My questions are : 1) What are the elements of the fields? 2) How to express them as power of the given primitive element?

Any hint will be very helpful.

share|improve this question

closed as off-topic by Dilip Sarwate, Claude Leibovici, T. Bongers, John, egreg Apr 13 '14 at 9:58

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

This question has been asked and answered on crypto.SE where the OP has already accepted an answer. He even made the same mistake: computing $g^{15}$ and finding that it equals $g^8$ in the comments there. –  Dilip Sarwate Apr 13 '14 at 3:06

1 Answer 1

To construct $\mathbb{F}_{16}$ first you need to find a degree $4$ polynomial which is irreducible over $\mathbb{F}_2.$ The only irreducible quadratic is $x^2+x+1$ so any degree $4$ polynomial which is not $(x^2+x+1)^2 = x^4+x^2+1$ and does not have a root in $\mathbb{F}_2$ is irreducible (think about this). The polynomial $x^4+x+1$ works well for us then:

$$ \mathbb{F}_{16} = \frac{ \mathbb{F}_2[x] }{ ( x^4+x+1) } .$$

So the elements of $\mathbb{F}_{16}$ are polynomials in $\mathbb{F}_2$ modulo the ideal $(x^4+x+1).$ Given any polynomial, you can apply the division algorithm to get a unique coset representation of the form $a+bx+cx^2+dx^4 + (x^4+x+1),$ and all of these are possible so this describes the elements of the field.

The group of units of this field has order $15,$ and the primitive elements are precisely those with order $15.$ The order of an element must divide the order of the group, so if we can find an element which does not have order $1,3$ or $5$ then it is a primitive element. A quick calculation shows that $x$ satisfies this.

Now to get every element as a power of the primitive element: Don't start with an element like $x+x^2+x^3$ and try to recognize it as a power of $x.$ Rather, compute and simplify (using $x^4=x+1$) all powers of $x.$ So the elements are

$$ \begin{align} 0,& 1, x ,x^2, x^3 \\x^4 &= x+1, \\ x^5 &= x^2+x, \\ x^6 &= x^3+x^2, \\ x^7 &= x^4+x^3 = x^3+x+1, \\ x^8 &= x^4+x^2+x = x^2+1, \\ x^9 &= x^3+x, \\ x^{10} &= x^4+x^2 = x^2+x+1, \\ x^{11} &= x^3+x^2+x, \\ x^{12} &= x^4+x^3+x^2 = x^3+x^2 +x+1, \\ x^{13} &= x^4+x^3+x^2+x = x^3+x^2+1, \\ x^{14} &= x^4+x^3+x = x^3+1. \end{align} $$

share|improve this answer
I think the OP already has a polynomial: $\beta^4+\beta^3+\beta^2+\beta+1$. –  TonyK Apr 11 '14 at 9:21
@TonyK I wasn't sure what OP meant. Hopefully my answer will still help them figure out how to do their question. –  Ragib Zaman Apr 11 '14 at 9:25
@RagibZaman Amazing Explaination sir. Yes your answer make it understand how to do it, though as TonyK said, it has a polynomial β4+β3+β2+β+1 . But your answer helps me to understand the concept which suffices my needs :) Thanks again. –  kingmakerking Apr 11 '14 at 11:47
@RagibZamanI figured out that for g^15 = g^8... Is it something weird? Am I doing something wrong or it is possible. I did not try after g15. here my g = β+1 –  kingmakerking Apr 11 '14 at 15:12
@sidnext2none You have definitely done something wrong. First exercise: Think of some reasons why $g^{15}=g^8$ should not be true. Second: Re-do your working. How did you compute $g^{15}?$ Compute $g^5$ and then cube that, you should be getting $1$. If you dont then something has already occurred wrong by the computation of $g^5.$ If it doesn't fix, edit your question to include your working and we will try to spot your mistake. –  Ragib Zaman Apr 11 '14 at 15:57

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