Geodesic
Some properties of modular addition
Matematičeskie voprosy kriptografii, Tome 10 (2019) no. 2, pp. 75-88 
V. V. Vysotskaya. Some properties of modular addition. Matematičeskie voprosy kriptografii, Tome 10 (2019) no. 2, pp. 75-88. http://geodesic.mathdoc.fr/item/MVK_2019_10_2_a5/
@article{MVK_2019_10_2_a5,
     author = {V. V. Vysotskaya},
     title = {Some properties of modular addition},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {75--88},
     year = {2019},
     volume = {10},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2019_10_2_a5/}
}
TY  - JOUR
AU  - V. V. Vysotskaya
TI  - Some properties of modular addition
JO  - Matematičeskie voprosy kriptografii
PY  - 2019
SP  - 75
EP  - 88
VL  - 10
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2019_10_2_a5/
LA  - en
ID  - MVK_2019_10_2_a5
ER  - 
%0 Journal Article
%A V. V. Vysotskaya
%T Some properties of modular addition
%J Matematičeskie voprosy kriptografii
%D 2019
%P 75-88
%V 10
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2019_10_2_a5/
%G en
%F MVK_2019_10_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

We study a problem which emerged during an attempt to apply a differential cryptanalysis method to the “Magma” algorithm. We obtain a general formula of distribution in the difference distribution table of addition modulo $2^n$ and provide an efficient method for computing the distribution in a row with given index. By means of this formula an asymptotic estimate of the number of different distributions is established. Finally, we design an algorithm generating all distributions in $2^{O(\sqrt{n})}$ operations (whereas the corresponding brute-force method takes $2^{\Omega(n)}$ operations).

[1] GOST 28147-89. National Standard of the USSR. Cryptographic Protection for Data Processing System, Standardinform, M., 1996 (in Russian)

[2] GOST R 34.12-2015 . National Standard of the Russian Federation. Cryptographic Data Security. Block Ciphers, Standardinform, M., 2016 (in Russian)

[3] H. Lipmaa, S. Moriai, “Efficient algorithms for computing differential properties of addition”, Lect. Notes Comput. Sci., 2355, 2002, 336–350 | DOI | Zbl

[4] V. Vysotskaya, Some properties of modular addition (Extended abstract), , Cryptology ePrint Archive, 2018 http://eprint.iacr.org/2018/1103

[5] J. Kelleher, B. O'Sullivan, Generating all partitions: a comparison of two encodings, 2009, arXiv: [0909.2331]

[6] G. H. Hardy, S. Ramanujan, “Asymptotic formulae in combinatory analysis”, Proc. London Math. Soc. (2), XVII:1 (2018), 75–115 | DOI | MR