Easiest way to perform Euclid's division algorithm for polynomials

Question

Let's say I have the two polynomials $f(x) = x^3 + x + 1$ and $g(x) = x^2 + x$ over $\operatorname{GF}(2)$ and want to perform a polynomial division in $\operatorname{GF}(2)$.

What's the easiest and most bullet proof way to find the quotient $q(x) = x + 1$ and the remainder $r(x)=1$ by hand?

The proposal by the german edition of Wikipedia is rather awkward.

Answer 1

$f$ corresponds to the binary number $1011$ and $g$ to $110$ if you identify $x$ with $2$. Appending a $0$ (rsp. multiplication by $2$) corresponds to multiplying with $x$ and $\oplus$ (exclusive or) is addition.

1011:110 = 11, i.e., the quotient is $x+1$
110 
--- 
 111
 110
 ---
   1, i.e., the remainder is 1

Answer 2

Polynomial long division is the way to go. Especially over a finite field where you don't have to worry about fractional coefficients (working over for instance the rational numbers these can get extremely unwieldy surprisingly soon). Over $\mathbb Z/2\mathbb Z$ you don't even have to worry about dividing coefficients at all, the only question to be answered is "to substract or not to subtract", where as a bonus subtraction is actually the same as addition.

Note that the wikipedia article you refer to does not assume such a simple context, and avoids division by coefficients by doing a pseudo-division instead (for which instead of explosion of fractions you can get enormous coefficients).

Answer 3

I am not sure what Euclid's algorithm in the title of the question is referring to, but as Marc van Leeuwen says, polynomial long division is the way to go. Since doing it by hand is asked about, I will suggest the following based on long experience of doing such divisions by hand and making many mistakes along the way by not being careful.

Use ruled paper for your work, turning it through a right angle so that the lines are vertical rather than horizontal. Then, write one symbol per column to keep things aligned properly. The calculation is exactly as shown in ego's answer but has vertical ruled lines between the bits so that you can keep things properly aligned. Yes, the problem can be solved easily without this artifice in this instance, but the simple trick is very helpful when dealing with polynomials of larger degree.