0
$\begingroup$

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

$\endgroup$
4
  • $\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
    Commented Dec 9, 2014 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
    Commented Dec 9, 2014 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
    Commented Dec 9, 2014 at 20:25
  • $\begingroup$ Awesome! got a now any idea how to do pt b? $\endgroup$
    – ABC
    Commented Dec 9, 2014 at 21:03

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.