Math
Urodziny i kolizje
Ludzie przychodzą na pierścień dni, aż dwoje trafi na ten sam: w roku o 365 dniach to 23. osoba, nie 183.; na Marsie 32.; w 65 536 kubełkach hasza 302. - przebiegi wobec dokładnej krzywej, dni przemiatane przeciąganiem od roku do 2³², reguła pierwiastka czytana na żywo i zadanie o marsjańskim pokoju.
Co się dzieje
Pierścień dni. Ludzie przychodzą po jednym i zapalają dzień, na który trafili; gdy ktoś trafi na zapalony dzień, pierścień rozbłyska i przebieg się kończy. W roku o 365 dniach dzieje się to około 23. osoby - nie 183., bo pytanie nie brzmi, czy ktoś ma urodziny w twój dzień, lecz czy jacyś dwoje mają je w ten sam, a par wśród 23 osób jest 253. Dokładna krzywa to 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m): 50,7 % przy 23, 99 % przy 57. Przebieg za przebiegiem wykres wypełnia udział empiryczny nad krzywą. Przeciągnij po pierścieniu, a liczba dni płynie w skali logarytmicznej: marsjański rok o 687 dniach potrzebuje 32 osób, tablica haszująca o 65 536 kubełkach zderza się przy 302. kluczu, 32-bitowy hasz około 77 000. - pokój, który zderza się z szansą monety, rośnie jak √(2m ln 2), pierwiastek z liczby dni, nie liczba dni. Dlatego hasz potrzebuje o wiele więcej kubełków niż kluczy i dlatego atak urodzinowy to najtańszy sposób złamania krótkiego podpisu.
Równania modułu
Równania kolizja do n: P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m); 365 dni: 22 osoby 47.6 %, 23 osoby 50.7 %, 57 osób 99 %; oczekiwana pierwsza kolizja następuje przy 24.617. osobie grupa jak rzut monetą (najmniejsze n z P ≥ ½): 365 → 23, Mars 687 → 32 (52.0 %; 31 daje 49.7 %), 65 536 koszyków → 302, 2^32 → 77 164 reguła pierwiastka kwadratowego: n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - grupa rośnie jak pierwiastek kwadratowy z liczby dni, a nie jak liczba dni przebiegi: jedno losowanie na osobę, dzień = floor(r·m), przez wspólny xorshift; ziarno 1 przy 365 dniach: 40. osoba trafia w dzień 200, zajęty przez 34. osobę; ziarna 1…1000: 518 ma kolizję do 23, średnia pierwsza kolizja 24.05 funkcje skrótu: ta sama arytmetyka dla kluczy w koszykach - dla 32-bitowego skrótu kolizji należy się spodziewać po około 77 000 kluczy
