I want to do a division of two binaries and take the rest (mod). But I want to do this using polynomials, let's take the example:
binary dividend: 010001100101000000000000 binary divisor: 100000111
polynomial form dividend: x²²+x¹⁸+x¹⁷+x¹⁴+x¹²
polynomial form divisor: x⁸+x²+x¹+x⁰
after the division: x²²+x¹⁸+x¹⁷+x¹⁴+x¹² / x⁸+x²+x¹+x⁰
result is: x¹⁴+x¹⁰+x⁹+x⁸+x⁷+x²+x¹
Remainder is : x⁷+x⁴+x¹
Someone can explain to me, step-by-step, how to do this division? Without convert to binary, needs to be in polynomial form.
Thank you.
Update for move to math:
Well, now that it's here, the Mathematica answer doesn't seem quite as useful anymore.
The answer is that you use the same long division you learned in elementary school. The only difference is that now you do it all modulo 2, so $1+1=0$. Similarly $x^2+x^2=0$. And consequently $-x^2=x^2$.
Then for:
$$x^3+x+1\over x+1$$
we start the long division by multiplying $x+1$ by $x^2$ so that we can get rid of the $x^3$ term. The first term in our quotient is then $x^2$. We get $x^3+x^2$. We now have:
$$x^2+{x^2+x+1\over x+1}$$
Doing that again, we get:
$$x^2+x+{1\over x+1}$$
The final term has a smaller degree over a larger degree, so we can proceed no further. The quotient is $x^2+x$ and the remainder is $1$.