Уточнение асимптотической аппроксимации размера группы в парадоксе дней рождений

Abstract

Доведено дві теореми про асимптотичну поведінку розміру групи у парадоксі днів народжень. В теоремі 1 наведено асимптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення частинок по чарунках. В теоремі 2 наведено асипмптотично непокращувальні оцінки для розміру групи у випадку рівноймовірного та незалежного розміщення двох однакових комплектів частинок по чарунках. Отримані результати можна застосувати у криптографії для оцінювання трудомісткості побудови колізій хеш-функцій.

Proved two theorems about asymptotic behavior group size in birthday paradox. Theorem 1 gives asymptotically best possible estimates for group size in case uniform and independent particle occupancy in cells. Theorem 2 gives asymptotically best possible estimates for group size in case uniform and independent occupancy of two equal sets of particles in cells. These results one may apply in cryptography for estimation working time for construction collisions of hash-functions.