Massimiliano Sala edited section_Bytes_The_polynomials_in__.tex  about 6 years ago

Commit id: 4113e577b71f8f1eaee13465470bdf156b6af5da

deletions | additions      

       

x^5+x \,=\, x^2(\underline{x^3})+x \,=^{\mathrm{substitution}}\, x^2(\underline{x+1})+x\,=\,  \underline{x^3}+x^2+x=^{\mathrm{substitution}} \underline{x+1}+x^2+x \,=\, x^2+1 \,.  \]  One The crucial observation here is that we  can obtain the same result by  dividing the polynomial $x^4+x^2$ $x^5+x$  by the polynomial $x^3+x+1$. The $g=x^3+x+1$: the  remainder is $x$.  Hence $x$ (see Exercise \label{QuoRemEx}).\\  Indeed, we can consider a set $T$, which collects the remainders of  the divisions of all  polynomialsdefined  in $F_2[x]$ by $g$. It is easy to see that $T$ contains $S$, because when  we divide a polynomial $f$ of degree less than $3$ by $g$,  the set  \[  \Fb[x], \mbox{ where }x^3+x+1=0  \]  are the polynomials  \[  0, remainder is $f$ itself  (see Example \ref{QuotRemStrange}), so  $$  \{0,  1, x, x+1, x^2, x^2+x, x^2+1, x^2+x+1.   \]  These polynomials are $8=2^3$. This number can be obtained directly x^2+x+1 \} subset T  $$  On the other hand,  if we consider that the generic any  polynomial $f \notin S$, this has $\deg(f)\geq 3$ and   when we divide it by $g$, we will get a remainder  of degree $2$ is  \[  a_2 x^2+ a_1 x+ a_0,  \]  where $a_2,a_1,a_0\in \Fb$. strictly less than $\deg(g)=3$,  and so $T$ can only contain polynomials of degree at most $2$, therefore  $$  T=S=\{0, 1, x, x+1, x^2, x^2+x, x^2+1, x^2+x+1 \}   $$  \begin{Definition}\label{RemPol} We define can perform this construction in general. Let $g$ be in $F_2[x]$, we consider  the set $A$  of polynomials $A$ as  \[  \Fb[x], \mbox{ where }p=0  \]  \end{Definition} that collects all remainders of the division by $g$  $$  A \,=\, \{ \mathrm{remainders by } g \} \,.  $$  The finite set $A$ inherits the operations of sum and product defined in the polynomial ring $\Fb[x]$. Moreover the following fact holds  \begin{Theorem}