In long-multiplication, you shift and add, once for each $1$ bit in the lower number.Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication, the addition does not carry. Essentially you bitwise-xor the shifted numbers.Like so:$$  \left[\begin{matrix}    &&p_n & ... & p_i & ... & p_2 & p_1 \\    &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\    \hline\\    &&q_1 \cdot p_n & ... & q_1 \cdot p_i      & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\    &q_2 \cdot p_n & ... & q_2 \cdot p_i      & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\    &&&&&&&...\\    q_i \cdot p_n & ... & q_i \cdot p_i      & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow}      &&{\Huge{\oplus}} \\    \hline \\    \\r_{2n}& ... & r_i      & ... &r_4& r_3 & r_2 &r_1 & =  \end{matrix}  \right]$$Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.Followup: Shift-and-or multiplication operation
Carry-free multiplication operation
algorithms;integers;number theory;multiplication
Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.If $p,q$ are $r$ bits long, this polynomial multiplication operation can be computed in $O(r \lg r)$ time using FFT techniques, but in practice this may not be a win unless your polynomial is extremely large. There is also a Karatsuba-style algorithm, whose complexity is something like $O(r^{1.6})$, as well as other options.  The situation is somewhat analogous to integer multiplication, in that many of the same fast algorithms can be applied, but not identical.See, e.g.,Wikipedia on Fast multiplication algorithms for large inputs.  These methods are described in terms of multiplying two integers, but they can be transposed to apply to polynomial multiplication.Polynomial Multiplication, Karatsuba and Fast Fourier TransformWhen is FFT multiplication of arbitrary-precision polynomials practical?.  Richard Fateman, March 14, 2006.Can you save time in multiplying polynomials by encoding them as integers?.  Richard Fateman, January 15, 2005.