Анализ сложности алгоритма параллельного поиска “золотой” коллизии

В статье уточняются полученные ранее Оршотом и Винером оценки временно́й и емкостно́й сложностей предложенного ими алгоритма поиска “золотой” коллизии. Для этого используются результаты, относящиеся к расчету характеристик метода балансировки время-память-данные с особыми точками. Описывается вероятностная модель, позволяющая аппроксимировать исследуемые характеристики алгоритма случайными величинами, зависящими от числа частици суммарного числа частицв докритическом процессе Гальтона–Ватсона. Найдены предельные значения математических ожиданий этих случайных величин.