Differential Characteristic Probability of Multiplied by Constant Operation on Modulo 2n

Multiplied by constant on modulo 2n operation, a building block, is widely used in the ciphers like Sosemanuk, RC6, MARS, and so on. This code link is recognized as a permutation with strong nonlinear property and fine realization efficiency, when the constant c is odd. But there is no published paper analyzed it with differential cryptanalysis. In this paper, the differential property of the operation is studied. And the characters of structure, counts of the input and output differentials and the constant are given for the first time, when the differential probability is to be 1. Then the recursive connection of its carries counts is given. Based on that, an algorithm of this operations differential probability is given, which time complexity is O(n) on average.