# Polynomial Modulus

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

• 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 '14 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 '14 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 '14 at 20:25
• Awesome! got a now any idea how to do pt b? – ABC Dec 9 '14 at 21:03

## 1 Answer

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$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8330799,"math_prob":1.0000031,"size":950,"snap":"2021-21-2021-25","text_gpt3_token_len":321,"char_repetition_ratio":0.11627907,"word_repetition_ratio":0.0,"special_character_ratio":0.37263158,"punctuation_ratio":0.10891089,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000092,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-24T08:45:45Z\",\"WARC-Record-ID\":\"<urn:uuid:86bf377e-2c50-40d3-bca3-3329d42d32ae>\",\"Content-Length\":\"167230\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:97930e82-1eb7-4f5d-a936-463009553506>\",\"WARC-Concurrent-To\":\"<urn:uuid:49e1783c-f366-4435-814c-ccf8d4b1f7f7>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://crypto.stackexchange.com/questions/20740/polynomial-modulus\",\"WARC-Payload-Digest\":\"sha1:JA22YFJSUFYQJOUWOBE2NNF3GQQGNQVZ\",\"WARC-Block-Digest\":\"sha1:OST3SVAGW32NGDZ3TCBDT7SY3BTV4JPW\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623488552937.93_warc_CC-MAIN-20210624075940-20210624105940-00136.warc.gz\"}"}