# Approximating multiplication with few instances of $\oplus$, $\ll$, $\land$, $\lor$

In their paper about the AEAD scheme NORX, the authors mention that $$a+b$$ can be "well approximated" (this is a bit a hand-wavy statement) by $$a+b \; "="\; a\oplus b \oplus ((a\land b) \ll 1).$$

(Note that the purpose of $$((a \land b) \ll 1)$$ is to simulate the "carry bit operation.")

Is there such a neat approximation for multiplication $$a\cdot b$$?

• While I can recommend the whole paper by Aumasson et al linked in the question, let me add that the approximation of $+$ is mentioned at the top of page 2. Commented May 30, 2021 at 17:53
• While I have no literature references, it looks like that approximation comes from representing $a+b$ via an adder (via something like $a + b = (a\oplus b) + ((a\land b)\gg 1)$, and then approximating $+\mapsto \oplus$. To derive something similar for $a\cdot b$ I would try to apply some similar process to a binary multiplier, and then try to approximate the resulting expression. Commented May 30, 2021 at 22:41
• I can't think of anything that wouldn't result in a lot of operations. Even using $\mathbb{F}_2[x]$ multiplication as a primitive, there doesn't seem to be some simple relation between the two operations to make a useful compromise. The obvious thing is to do shift-and-add multiplication using the NORX operation as the "add", but that's not exactly "neat". Commented May 31, 2021 at 4:10
• Thanks to both commenters; the way @Mark suggests is the natural thing to do. I wondered whether there is some nifty shortcut I keep missing Commented May 31, 2021 at 8:39