0
$\begingroup$

Motivation. There is a fast approximation to conventional multiplication. It conceptually works like long multiplication except for the fact that the carry is discarded instead of applied to the more significant position. Hence its name: carry-less product. One use is to improve the speed of applications doing block cipher encryption in Galois/Counter Mode. The operation is also known as an XOR multiplication, as carry-discarding addition is equivalent to an exclusive or.

This question is about the quality of this approximation in terms of Hamming distance.

Carry-less product. Assume we have two non-negative integers $a=\sum_{i}a_{i}2^{i}$ and $b=\sum_{i}b_{i}2^{i}$, with $a_i , b_i \in \{ 0 , 1\}$ denoting the bits of these numbers. Then the carry-less product of $a,b$ is defined to be $c=\sum_{i}c_{i}2^{i}$, with each bit $c_i$ computed as the XOR of products of bits from the input numbers as follows:

$$c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{i-j}.$$

Questions. In terms of $n$, what is the maximum Hamming distance of the conventional product to the carry-less product that any $n$-bit numbers can have? And what is the average Hamming distance between the conventional and the carr-less product of $n$-bit numbers?

$\endgroup$
3
  • 1
    $\begingroup$ The carryless product seems to be precisely standard polynomial multiplication over $\mathbb{F}_2[x] \cong \mathbb{Z}[x] / (2)$. The standard product can additionally be seen as a product in $\mathbb{Z}[x] / (x -2)$ in a natural way. $\endgroup$
    – Mark Schultz-Wu
    Jan 29, 2022 at 7:08
  • 1
    $\begingroup$ The average is difficult to obtain, but the maximum is $2n-2$, and it's not difficult to create inputs matching it. $\endgroup$ Jan 30, 2022 at 16:35
  • 1
    $\begingroup$ While this doesn't precisely answer your question, BoringSSL's page on GHASH discusses how one can use standard integer multiplication to compute exactly the carryless product via a certain padding technique. $\endgroup$
    – Mark Schultz-Wu
    Feb 1, 2022 at 5:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.