Paper 2009/047

On Approximating Addition by Exclusive OR

Palash Sarkar

Abstract

Let X(1),X(2),,X(n) be independent and uniformly distributed over the non-negative integers {0,1,,2i1}; S(n)=X(1)+X(2)++X(n) and L(n)=X(1)X(2)X(n). Denote the i-th bits of S(n) and L(n) by Si(n) and Li(n) respectively. We show that as i, , where is the -th Bernoulli number. As a consequence, for every ; and we show that as . For small values of , is significantly different from ; for example and . The behaviour of for even and odd values of was earlier shown by Staffelbach and Meier without actually obtaining the formula mentioned above. For every fixed , we give a simple method for computing for each . 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
palash @ isical ac in
History
2009-02-03: last of 2 revisions
2009-01-29: received
See all versions
Short URL
https://ia.cr/2009/047
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/047,
      author = {Palash Sarkar},
      title = {On Approximating Addition by Exclusive {OR}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/047},
      year = {2009},
      url = {https://eprint.iacr.org/2009/047}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.