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.

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

share|improve this question
    
Note that $x^4 \equiv x^3+1 \pmod{f(x)}$, and work from there: $x^5 = x^4\times x = \cdots$, etc. –  fkraiem Dec 9 at 20:19
    
fkraiem's hint is good, but this is really more of a math problem than a cryptography problem. –  Guut Boy Dec 9 at 20:20
    
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)}$. –  fgrieu Dec 9 at 20:25
    
Awesome! got a now any idea how to do pt b? –  A. Great Dec 9 at 21:03

1 Answer 1

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

share|improve this answer

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.