A complexity analysis of algorithm of parallel search of the “gold” collision

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.