Paper 2018/1103

Some Properties of Modular Addition

Victoria Vysotskaya

Abstract

In this paper we study a problem which emerged during an attempt to apply a differential cryptanalysis method to the <<Magma>> algorithm. We obtained a general formula of distribution in the difference distribution table of addition modulo $2^n$ and provided an efficient method for computing the distribution in a row with given index. Moreover, an exact formula that may be used to solve the task of counting all the distributions was obtained, and an asymptotically accurate approximation of number of distinct distributions was proved. Finally, we designed an algorithm to generate all distributions in $2^{O(\sqrt{(n)})}$ operations (whereas the corresponding brute-force method takes $2^{\Omega(n)}$).