So I am studying for finals and I came across this problem and I am completely stuck. I would really appreciate someone to clarify on the steps to take to solve these problems.

Let $f(x) = x^4 + x^3 + 1$ , which is an element of $\mathbb Z_2[x]$

a.) Show that $x^{16}\equiv x\pmod{f(x)}$

b.) What is the smallest integer $k>0$, so that $x^k\equiv 1\pmod{f(x)}$

  • $\begingroup$ Note that $x^4 \equiv x^3+1 \pmod{f(x)}$, and work from there: $x^5 = x^4\times x = \cdots$, etc. $\endgroup$ – fkraiem Dec 9 '14 at 20:19
  • $\begingroup$ fkraiem's hint is good, but this is really more of a math problem than a cryptography problem. $\endgroup$ – Guut Boy Dec 9 '14 at 20:20
  • $\begingroup$ Hint: for a.) the first steps are: $x^{16}=x^{12}(x^4+x^3+1)+x^{15}+x^{12}$, therefore $x^{16}\equiv x^{15}+x^{12}\pmod{f(x)}$; $\;$ $x^{15}+x^{12}=x^{11}(x^4+x^3+1)+x^{14}+x^{12}+x^{11}$, therefore $x^{16}\equiv x^{14}+x^{12}+x^{11}\pmod{f(x)}$. $\endgroup$ – fgrieu Dec 9 '14 at 20:25
  • $\begingroup$ Awesome! got a now any idea how to do pt b? $\endgroup$ – ABC Dec 9 '14 at 21:03

Note that $f$ is irreducible over $\mathbb F_2$, which you can easily show using the observation that if it was reducible, there was a non-trivial divisor of degree $1$ or $2$, and disproving both of these possibilities by trial division. Therefore, $\mathbb Z_2[x]/(f)$ forms a field isomorphic to $\mathbb F_{2^{\deg f}}=\mathbb F_{16}$.

  1. Since the non-zero elements of $\mathbb F_{16}$ form a (multiplicative) group of order $15$, by Fermat's little theorem, one has $a^{15}=1$ for all $a\in\mathbb F_{16}$. Therefore, $x^{16}+(f)=(x+(f))^{16}=x+(f)$, implying $x^{16}\equiv x\mod f$.

  2. Note that by Lagrange's theorem, $k$ must divide said group's order $15$. The only possible values smaller than $15$ are therefore $1$, $3$ and $5$, all of which one can easily eliminate by calculation:

    • $(x+(f))^1=x+(f)\neq1+(f)$;
    • $(x+(f))^3=x^3+(f)\neq1+(f)$;
    • $(x+(f))^5=x^3+x+1+(f)\neq1+(f)$.

    Hence, $k=15$ is the smallest exponent such that $x^k\equiv1\mod f$.


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.