Math
Compleanni e collisioni
Le persone arrivano su un anello di giorni finché due ne condividono uno: in un anno di 365 è la 23ª persona, non la 183ª; su Marte la 32ª; in 65 536 secchi di hash la 302ª; estrazioni contro la curva esatta, i giorni scorsi trascinando da un anno a 2³², la regola della radice quadrata letta in diretta, e un compito sulla stanza marziana.
Cosa succede
Un anello di giorni. Le persone arrivano una alla volta e accendono il giorno su cui cadono; la prima volta che qualcuno cade su un giorno acceso, l'anello divampa e l'estrazione è finita. In un anno di 365 giorni succede verso la 23ª persona, non la 183ª, perché la domanda non è se qualcuno condivide il tuo compleanno ma se due qualsiasi ne condividono uno, e tra 23 persone ci sono 253 coppie. La curva esatta è 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m): 50,7 % a 23, 99 % a 57. Estrazione dopo estrazione, il grafico riempie la frazione empirica sopra la curva. Trascina sull'anello e il numero di giorni scorre in scala logaritmica: un anno marziano di 687 giorni chiede 32 persone, una tabella hash di 65 536 secchi collide alla 302ª chiave, un hash a 32 bit verso la 77 000ª; la stanza che collide con la probabilità di una moneta segue √(2m ln 2), la radice quadrata dei giorni, non i giorni. Per questo un hash ha bisogno di molti più secchi che chiavi, e per questo l'attacco del compleanno è il modo più economico per rompere una firma corta.
Equazioni del modulo
Equazioni collisione entro n: P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m); 365 giorni: 22 persone 47.6 %, 23 persone 50.7 %, 57 persone 99 %; la prima collisione attesa avviene alla persona numero 24.617 la stanza del testa o croce (il più piccolo n con P ≥ ½): 365 → 23, Marte 687 → 32 (52.0 %; 31 dà 49.7 %), 65 536 contenitori → 302, 2^32 → 77 164 la regola della radice quadrata: n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - la stanza cresce con la radice quadrata dei giorni, non con i giorni esecuzioni: un'estrazione per persona, giorno = floor(r·m), tramite lo xorshift condiviso; seme 1 in 365 giorni: la persona numero 40 cade nel giorno 200, già occupato dalla numero 34; semi 1…1000: 518 collidono entro 23, prima collisione media 24.05 hash: la stessa aritmetica per chiavi in contenitori - un hash a 32-bit si aspetta di collidere dopo circa 77 000 chiavi
