Welcome to the resource topic for 2010/072
Title:
Approximating Addition by XOR: how to go all the way
Authors: Didier Alquié
Abstract:In this paper, we study approximation of addition by XOR, taking P. Sarkar’s publication~\cite{bib:sarkar} as the reference work and starting point. In this work, among various results, it was claimed that explicit formulas seemed difficult to obtain when the number n of summands is more than 5. In the first part of our work, we show a systematic way to find explicit formulas: the complexity to compute them is O(n^3), which allows large values of n. We present some numerical computation and point out a - conjectural - observation on the coefficients. In the second part, we study a generalization of P. Sarkar’s work to q-ary addition, instead of binary. We show that the mechanics of the addition is essentially the same as in the binary case. In particular, sequence of carries behaves very similarly: it is a Markov chain whose transition matrix can be computed. Running some experiments on small values of n leads us to a conjecture, the first part of which is intuitive and the second part of which reveals an amazing coincidence (and is probably not!). Finally, in a section titled very last news'', we refer to a paper published by Holte in 1997, that was brought to us after our first post and that we had missed before. It happens that this paper studies the topic and solves a major part of our open problems. Henceforth, the present post is an updated version of our previous Approximating Addition by XOR: how to go (a little) further than P. Sarkar’', taking into account this previous Holte’s reference.
ePrint: https://eprint.iacr.org/2010/072
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .