Geodesic
A complexity analysis of algorithm of parallel search of the ``gold'' collision
Matematičeskie voprosy kriptografii, Tome 6 (2015), pp. 77-97

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

The paper refines known estimates of time and memory complexities of Oorschot and Wiener algorithm for the “gold” collision searching. We use results related to the computation of characteristics of time-memory-data tradeoff method with distinguished points. Probabilistic approximations of the algorithm characteristics by random variables depending on the number of particles and the total number of particles in a subcritical Galton–Watson process are described.The limits of expectations of these random variables are found. 
@article{MVK_2015_6_a4,
     author = {D. V. Pilshchikov},
     title = {A complexity analysis of algorithm of parallel search of the ``gold'' collision},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {77--97},
     publisher = {mathdoc},
     volume = {6},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_a4/}
}
TY  - JOUR
AU  - D. V. Pilshchikov
TI  - A complexity analysis of algorithm of parallel search of the ``gold'' collision
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 77
EP  - 97
VL  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_a4/
LA  - ru
ID  - MVK_2015_6_a4
ER  - 
%0 Journal Article
%A D. V. Pilshchikov
%T A complexity analysis of algorithm of parallel search of the ``gold'' collision
%J Matematičeskie voprosy kriptografii
%D 2015
%P 77-97
%V 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_a4/
%G ru
%F MVK_2015_6_a4
D. V. Pilshchikov. A complexity analysis of algorithm of parallel search of the ``gold'' collision. Matematičeskie voprosy kriptografii, Tome 6 (2015), pp. 77-97. http://geodesic.mathdoc.fr/item/MVK_2015_6_a4/