Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

$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
share|improve this answer

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.

share|improve this answer

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

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.