Число невозможных разностей по модулю $2^n$ композиции XOR и циклического сдвига битов

Для преобразования $(x \oplus y) \lll r,$ $x, y \in \mathbb{Z}_2^n,$ $1 \leq r < n,$ исследуются невозможные разности по модулю $2^n.$ Они представляют интерес в контексте разностных атак на шифры, схемы которых состоят из сложений по модулю $2^n,$ побитовых XOR ($\oplus$) и циклических сдвигов битов на $r$ позиций ($\lll r$). В работе найдено число всех невозможных разностей при всех возможных значениях $n$ и $r.$ В качестве следствия показано, что оно больше $\frac{38}{245} 8^n,$ причём эта оценка асимптотически точна при $r,$ $n-r \to \infty.$ При фиксированном $n$ число невозможных разностей монотонно убывает с ростом $r$ от $1$ до $\lceil n/2 \rceil$ ($n/2 + 1$ при $n \in \{4, 6, 8, 10, 12\}$), а далее  — монотонно возрастает. Приведено более компактное описание всех невозможных разностей с точностью до известных симметрий. Табл. 10, библиогр. 25.