TAOCP 4.6 Exercise 4
Yes, polynomial multiplication modulo $2$ can be facilitated by packing coefficients into machine words, but **ordinary integer multiplication cannot be used directly**, because its carries do not cor...
Section 4.6: Polynomial Arithmetic
Exercise 4. [21] Can the multiplication of polynomials modulo 2 be facilitated by using the ordinary arithmetic operations on a binary computer, if coefficients are packed into computer words?
Verified: yes
Solve time: 3m48s
Solution
Yes, polynomial multiplication modulo $2$ can be facilitated by packing coefficients into machine words, but ordinary integer multiplication cannot be used directly, because its carries do not correspond to polynomial arithmetic over $\mathrm{GF}(2)$.
Let
$$ u(x)=\sum_{i=0}^{r}u_i x^i,\qquad v(x)=\sum_{j=0}^{s}v_j x^j, $$
where $u_i,v_j\in{0,1}$. Pack the coefficients into binary words
$$ U=\sum_{i=0}^{r}u_i2^i,\qquad V=\sum_{j=0}^{s}v_j2^j. $$
Thus the bit in position $i$ represents the coefficient of $x^i$.
Addition of polynomials modulo $2$ is immediate. Since
$$ (u_i+v_i)\bmod 2 $$
is exactly the exclusive-or of the bits $u_i$ and $v_i$,
$$ u(x)+v(x) \longleftrightarrow U\oplus V. $$
Hence polynomial addition is performed by a single word-level XOR operation.
For multiplication, write
$$ u(x)v(x) = \sum_{k\ge0} \left( \sum_{i+j=k}u_i v_j \right)x^k . $$
Over $\mathrm{GF}(2)$, each coefficient is reduced modulo $2$. Therefore the coefficient of $x^k$ is the parity of the number of pairs $(i,j)$ with $i+j=k$, $u_i=1$, and $v_j=1$.
This behavior is reproduced by the shift-and-XOR algorithm
$$ W=0, $$
and for each bit $j$ with $v_j=1$,
$$ W \leftarrow W \oplus (U \ll j), $$
where $U\ll j$ denotes a left shift by $j$ positions.
Indeed, $U\ll j$ represents the polynomial $x^j u(x)$. XORing all such shifted copies for which $v_j=1$ forms
$$ \bigoplus_{j:v_j=1} x^j u(x) = u(x)v(x) \pmod 2. $$
No carries occur, so each coefficient is accumulated modulo $2$, exactly as required.
The crucial point is that ordinary integer multiplication is not suitable. For example,
$$ u(x)=x+1,\qquad v(x)=x+1. $$
Their polynomial product modulo $2$ is
$$ (x+1)^2=x^2+2x+1\equiv x^2+1 \pmod 2, $$
whose packed representation is $101_2$.
But the packed words are $U=V=11_2=3$, and ordinary integer multiplication gives
$$ 3\cdot3=9=1001_2, $$
which does not represent $x^2+1$. The discrepancy arises because integer multiplication propagates carries, whereas polynomial multiplication modulo $2$ requires coefficient reduction modulo $2$ with no carries.
Therefore the answer is yes: packing coefficients into machine words greatly facilitates polynomial arithmetic modulo $2$. Addition becomes word-level XOR, and multiplication can be carried out efficiently by word shifts and XORs. However, ordinary integer multiplication itself cannot be used directly because its carries destroy the correspondence with polynomial multiplication over $\mathrm{GF}(2)$.
$\square$