0
$\begingroup$

got this assignment from my coding class and don't know if I've made it correct. Can someone tell if my methods for solving the tasks are correct?

Let $f(x) = 1 + x ^3 + x ^4$ . It is given that $f(x)$ is irreducible in $K[x]$. Let $F = GF(2^4 )$ be $K[x] modulo f(x)$ and let be $x modulo f(x)$ in $F$.

a) By making a table expressing $1, \beta, \beta^2... \beta^{14}$ in the form $a_0 + a_1\beta + a_2\beta^2 + a_3\beta^3$ (or $a_0a_1a_2a_3)$ with the a_i in $K$, verify that $\beta$ is a primitive element of $F$.

So after constructing the table I made the following equation:

$p(\beta)=1+\beta^3+\beta^4$ and after inputting the corresponding values from the table $p( \beta) = 1000 + 0001 + 1001 = 0000$ so $\beta$ is a primitive

b) Let $\alpha$ be $\beta^{12}$. Is $\alpha$ a primitive element of F?

so the equation is now $p(\beta^{12})=1+(\beta^{12})^3+(\beta^{12})^4 = 1 + \beta^{36} + \beta^{48}$. Here I'm not actually sure. The table is only till $\beta^{14}$ and in the book i've found that $\beta^{15} = 1$? so following this $\beta^{36} = \beta^6$ and $\beta^{48} = \beta^3$ and the equation gets the following form $p(\beta^{12})=1000+1111+0001=0110$ so $\beta^{12}$ is not a primitive?

c) Find the minimal polynomial $m(x)$ in $K[x]$ for $\alpha$ as in (b)

so $\alpha = \beta^{12}$, and $m_a(\beta^{12})=a_01+a_1\beta^{12}+a_2(\beta^{12})^2+a_3(\beta^{12})^3+a_4(\beta^{12})^4=a_01+a_1\beta^{12}+a_2\beta^{24}+a_3\beta^{36}+a_4\beta^{48} = a_0(1000)+a_1(1100)+a_2(1010)+a_3(1111)+a_4(0001)$. solving the equation gives $a_0=a_1=a_2=a_3=a_4=1$ and $m_\alpha(x) = 1 + x + x^2 + x^3 + x^4$ and the roots are $\{\beta^{12},\beta^{24},\beta^{36},\beta^{48}\}$ and $m_{12}(x)=m_{24}(x)=m_{36}(x)=m_{48}(x)$ denote the minimal polynomials of $\beta^i$

$\endgroup$
1
$\begingroup$

Your test that $1000+0001+1001 = 0000$, that is, $1+\beta^3+\beta^4 = 0$ shows only that $\beta$ is a root of $1+x^3+x^4$ and not that $\beta$ is primitive (meaning of order $15$). What shows that $\beta$ is primitive is that $1, \beta, \beta^2, \ldots, \beta^{14}$ all have different representations as polynomials of degree at most $3$ in $\beta$ and so $\beta$ has order $15$ or more; and when you compute $\beta^{15}$ as a polynomial of degree at most $3$ in $\beta$, you find that $\beta^{15} = 1$ and so $\beta$ is indeed of order $15$ and hence primitive.

On the other hand, $\alpha = \beta^{12}$ is not a primitive element. Here, it is simpler to use the result that

$${\sf ord}(\beta^k) = \frac{{\sf ord}(\beta)}{\gcd({\sf ord}(\beta), k)}$$ to deduce that $\beta^{12}$ is an element of order $5$. Or, you could try showing that $\alpha^5 = \beta^{60} = 1$, hopefully without grinding out the table to $60$ terms (hint: you already know that $\beta^{15}=1$). So, $\alpha$ is an element of order $5$ or a divisor of $5\quad$....

$\endgroup$
  • $\begingroup$ Thank You very much! I see I've understood the stuff from the book not correct! so summing up, looking for the roots doesn't tell anything about the primitive. (c) correct luckily :) $\endgroup$ – mjanisz1 Oct 7 '13 at 22:19
  • $\begingroup$ Sorry but reading this now i totally don't understand your solution? I assume primitive is of order 15 because the field is $2^4$ so $16-1 = 15$ How to check the order of other polynomials in that field? $\endgroup$ – mjanisz1 Oct 8 '13 at 18:34
  • $\begingroup$ What is meant by polynomials in that field? The irreducible polynomial divisors of $x^{15}-1$ are $$x+1, x^2+x+1, x^4+x^3+x^3+x^2+x+1,x^4+x^3+1, x^4+x+1$$ if which you know already that the roots of $x^4+x^3+1$ are of order $15$ and those of $x^4+x^3+x^2+x+1$ of order $5$. Since ${\sf{ord}}(\beta^{-1}) = {\sf{ord}}(\beta^{14}) = 15$, you can show that $x^4+x+1$ is also a primitive polynomial. All the remains is the orders of the roots of $x+1$ and $x^2+x+1$. Make a list of all elements whose orders you have found to figure out which elements are candidates for roots of these polynomials. $\endgroup$ – Dilip Sarwate Oct 8 '13 at 19:04
  • $\begingroup$ Sorry, I still don't understand Your method of showing how its primitive. I've found in my book that $βi ∈ GF(2^r)$ is primitive iff $gcd(i, 2^r – 1) = 1$ but don't know how to prove it. $\endgroup$ – mjanisz1 Oct 8 '13 at 19:18
  • $\begingroup$ What do you want to prove? The statement that if $\beta$ is a primitive element of $\text{GF}(2^r)$, then $\beta^i$ is a primitive element iff $\gcd(i,2^r-1)$? Note that your statement of this result is not true since you do not restrict $\beta$ to be a primitive element. As to "my" method, I merely said that if $1, \beta, \beta^2, \ldots, \beta^{14}$ are all different elements of the field, and $\beta^{15} = 1$, then $\beta$ is an element of order $15$ (this is the definition, there is nothing to prove here) and since $\beta\in\text{GF}(2^4)$, it is a primitive element $\endgroup$ – Dilip Sarwate Oct 8 '13 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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