Carry-free multiplication operation

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

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 Transform

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

StackExchange Computer Science Q#16578, answer score: 5