Some properties of modular addition

Исследуется задача, которая возникла при попытке применить разностный криптоанализ к алгоритму «Магма». Получена общая формула распределения в строке разностной таблицы сложения по модулю $2^n$ и построен эффективный метод вычисления распределения в строке с заданным номером. С помощью этой формулы найдена асимптотическая оценка числа различных распределений. В работе приводится также алгоритм генерации всех возможных распределений за $2^{O(\sqrt{n})}$ операций (соответствующий алгоритм, использующий полный перебор, требует $2^{\Omega(n)}$ операций).