Math
Дні народження і колізії
Люди приходять на кільце днів, доки двоє не опиняться на одному: у році з 365 днів це 23-й, а не 183-й, на Марсі — 32-й, у 65 536 кошиках хешу — 302-й; прогони проти точної кривої, дні пливуть під перетягуванням від року до 2³², правило квадратного кореня читається наживо, і задача про марсіанську кімнату.
Що відбувається
Кільце днів. Люди приходять по одному і запалюють день, на який потрапили; коли хтось потрапляє на вже запалений день, кільце спалахує і прогін закінчено. У році з 365 днів це трапляється близько 23-ї людини — не 183-ї, бо питання не в тому, чи збіжиться чийсь день народження з твоїм, а в тому, чи збіжаться у якихось двох, а пар серед 23 людей 253. Точна крива — 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m): 50,7 % при 23, 99 % при 57. Прогін за прогоном, і графік заповнює емпіричну частку поверх кривої. Тягни по кільцю — кількість днів пливе за логарифмом: марсіанському року з 687 днів треба 32 людини, хеш-таблиця на 65 536 кошиків стикається на 302-му ключі, 32-бітний хеш — близько 77 000-го; кімната, де зіткнення — монетка, росте як √(2m ln 2), корінь із числа днів, а не число днів. Тому кошиків у хешу має бути куди більше, ніж ключів, і тому атака «днів народження» — найдешевший спосіб зламати короткий підпис.
Рівняння модуля
Рівняння колізія до n: P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m); 365 днів: 22 людини 47.6 %, 23 людини 50.7 %, 57 людей 99 %; очікувана перша колізія настає на 24.617-й людині кімната підкидання монети (найменше n при P ≥ ½): 365 → 23, Марс 687 → 32 (52.0 %; 31 дає 49.7 %), 65 536 кошиків → 302, 2^32 → 77 164 правило квадратного кореня: n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - кімната зростає як квадратний корінь із кількості днів, а не як кількість днів прогони: один розіграш на людину, день = floor(r·m), через спільний xorshift; зерно 1 для 365 днів: 40-та людина потрапляє на день 200, уже зайнятий 34-ю; зерна 1…1000: у 518 колізія настає до 23, середня перша колізія 24.05 хеші: та сама арифметика для ключів у кошики - 32-бітний хеш, імовірно, дасть колізію приблизно після 77 000 ключів
