<p>Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (no need to propagate carry bits), but multiplication of integers is an operation people consider essential, and so has direct support in ALUs and programming languages.</p>

CC BY-SA 2.5
2011-01-16T21:32:32.207Z
I am really interested in the asymptotic complexity not so much practical aspects.  A linear time and space reduction would answer the question.
Simd
CC BY-SA 2.5
2011-01-08T09:00:36.567Z
2011-01-08T09:00:36.567Z
Peter Taylor
<p>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.</p>

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

<p>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?  </p>

CC BY-SA 2.5
2010-10-23T18:54:41.957Z
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.
Simd
CC BY-SA 2.5
2010-10-29T14:42:41.777Z
Thanks, Suresh!  I hope we can avoid the tumbleweed for this one :-)
Simd
CC BY-SA 2.5
2010-11-04T06:19:53.137Z
alas, looks like it will continue to tumble. pity...
Suresh Venkat
CC BY-SA 2.5
2010-11-04T08:01:21.383Z
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.
Simd
<ds.algorithms><reductions><time-complexity>
Binary multiplication and parity convolution
Simd
# Binary multiplication and parity convolution

(Asked by: username_0 on 2010-10-23)

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?

**Tags:** ds.algorithms, reductions, time-complexity

> **Comments:**
> **username_0**: 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.  
> **username_0**: Thanks, Suresh!  I hope we can avoid the tumbleweed for this one :-)  
> **username_1**: alas, looks like it will continue to tumble. pity...  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-01-08. Score: 2

Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (no need to propagate carry bits), but multiplication of integers is an operation people consider essential, and so has direct support in ALUs and programming languages.

> **Comments:**
> **username_0**: I am really interested in the asymptotic complexity not so much practical aspects.  A linear time and space reduction would answer the question.  

---

