Efficient Algorithms for Computing Differential Properties of Addition

In this paper we systematically study the differential properties of addition modulo 2n. We derive Θ(logn)-time algorithms for most of the properties, including differential probability of addition. We also present log-time algorithms for finding good differentials. Despite the apparent simplicity of modular addition, the best known algorithms require naive exhaustive computation. Our results represent a significant improvement over them. In the most extreme case, we present a complexity reduction from Ω(24n) to Θ(logn).