Past exam of the computer science course of the University of Oxford / 2015 / Computer networks / 1 / g / Solution

All the following polynomial coefficients and sums lie in the field with two elements, so $a+a=0$. For the constant polynomial,For the linear polynomial, subtracting the leading multiple means adding it:For the quadratic polynomial, first cancel $a{x}^2$ using $ax(x+1)$, leaving $(a+b)x+c$; then cancel $(a+b)x$ using $(a+b)(x+1)$. ThusThe requested polynomial quotients and polynomial remainders are thereforeFor a general polynomial $P(x)={\sum }_{i=0}^n{p}_i{x}^i$, write $P=(x+1)Q+R$ with constant $R$. Since $1+1=0$, polynomial evaluation at $x=1$ gives $P(1)=R$. This is the polynomial remainder theorem with $-1=1$ in the field with two elements. HenceThe polynomial remainder is precisely the parity bit obtained by taking the exclusive or of all the polynomial coefficients.