# Binary multiplication and parity convolution

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a better solution to the question from Knuth vol. 2, 3rd edition, page 420 than that given in the book.

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

Knuth gives a reasonably straightforward reduction which expands the number of bits in the input by a log multiplicative factor in the worst case. Can this log factor be reduced?

• To clarify a little, I am not actually interested in the "packed into computer words" part of the question but just the reduction. To put it more concisely, could it really be the case that multiplication of two binary numbers is strictly easier (in the sense of permitting an asymptotically faster solution) than the multiplication of polynomials modulo 2? This would seem counter to the standard intuition as I understand it. Oct 23, 2010 at 18:54
• Thanks, Suresh! I hope we can avoid the tumbleweed for this one :-) Oct 29, 2010 at 14:42
• alas, looks like it will continue to tumble. pity... Nov 4, 2010 at 6:19
• I wonder why this is. Maybe I didn't phrase it well but the question of whether multiplication could be easier than (parity) convolution must be a question that at least some people must have thought about, given how well established the known connections between the two problems are. Nov 4, 2010 at 8:01