Paper 2009/047

On Approximating Addition by Exclusive OR

Palash Sarkar

Abstract

Let $X^{(1)},X^{(2)},\ldots,X^{(n)}$ be independent and uniformly distributed over the non-negative integers $\{0,1,\ldots,2^i-1\}$; $S^{(n)}=X^{(1)}+X^{(2)}+\cdots+X^{(n)}$ and $L^{(n)}=X^{(1)}\oplus X^{(2)}\oplus \cdots\oplus X^{(n)}$. Denote the $i$-th bits of $S^{(n)}$ and $L^{(n)}$ by $S^{(n)}_i$ and $L^{(n)}_i$ respectively. We show that as $i\rightarrow \infty$, $\pr[S^{(n)}_i=L^{(n)}_i]\rightarrow \gamma^{(n)}= \frac{1}{2}+\frac{2^{n+1}(2^{n+1}-1)}{2(n+1)}\times\frac{b_{n+1}}{n!}$, where $b_n$ is the $n$-th Bernoulli number. As a consequence, $\gamma^{(2r)}=1/2$ for every $r$; and we show that $\gamma^{(2r+1)}\rightarrow 1/2$ as $r\rightarrow \infty$. For small values of $r$, $\gamma^{(2r+1)}$ is significantly different from $1/2$; for example $\gamma^{(3)}=1/3$ and $\gamma^{(5)}=17/30$. The behaviour of $\gamma^{(n)}$ for even and odd values of $n$ was earlier shown by Staffelbach and Meier without actually obtaining the formula mentioned above. For every fixed $n\geq 2$, we give a simple method for computing $\pr[S^{(n)}_i=L^{(n)}_i]$ for each $i\geq 0$. The expression involving Bernoulli numbers is arrived at via the Eulerian number triangle which in turn arises in relation to the stationary distribution of a Markov chain formed by the carry values.

Note: We would like to thank Willi Meier for pointing out an earlier work (from Crypto 1990) of his (co-authored with Othmar Staffelbach). This revision explains the relation between the eprint report and the earlier work.