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 ключей
