Some properties of modular addition

We study a problem which emerged during an attempt to apply a differential cryptanalysis method to the “Magma” algorithm. We obtain a general formula of distribution in the difference distribution table of addition modulo $2^n$ and provide an efficient method for computing the distribution in a row with given index. By means of this formula an asymptotic estimate of the number of different distributions is established. Finally, we design an algorithm generating all distributions in $2^{O(\sqrt{n})}$ operations (whereas the corresponding brute-force method takes $2^{\Omega(n)}$ operations).