Math
Geburtstage und Kollisionen
Menschen kommen auf einen Ring von Tagen, bis zwei einen teilen: in einem Jahr von 365 Tagen ist das der 23., nicht der 183., auf dem Mars der 32., in 65 536 Hash-Fächern der 302. - Läufe gegen die exakte Kurve, die Tage per Ziehen von einem Jahr bis 2³² gefahren, die Wurzelregel live gelesen, und eine Aufgabe zum Marsraum.
Was passiert
Ein Ring von Tagen. Menschen kommen einer nach dem anderen und erleuchten den Tag, auf dem sie landen; landet jemand auf einem erleuchteten Tag, flackert der Ring auf und der Lauf ist vorbei. In einem Jahr von 365 Tagen passiert das um den 23. Menschen - nicht den 183., denn die Frage ist nicht, ob jemand Ihren Geburtstag teilt, sondern ob irgendzwei einen teilen, und unter 23 Menschen gibt es 253 Paare. Die exakte Kurve ist 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m): 50,7 % bei 23, 99 % bei 57. Lauf folgt auf Lauf, und das Diagramm füllt den empirischen Anteil über der Kurve. Ziehen Sie über den Ring, und die Zahl der Tage gleitet logarithmisch: ein Marsjahr von 687 Tagen braucht 32 Menschen, eine Hashtabelle mit 65 536 Fächern kollidiert beim 302. Schlüssel, ein 32-Bit-Hash etwa beim 77 000. - der Raum, der mit Münzwahrscheinlichkeit kollidiert, folgt √(2m ln 2), der Wurzel aus den Tagen, nicht den Tagen. Deshalb braucht ein Hash weit mehr Fächer als Schlüssel, und deshalb ist der Geburtstagsangriff der billigste Weg, eine kurze Signatur zu brechen.
Gleichungen des Moduls
Gleichungen Kollision bis n: P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m); 365 Tage: 22 Personen 47.6 %, 23 Personen 50.7 %, 57 Personen 99 %; die erwartete erste Kollision tritt bei Person 24.617 ein der Münzwurf-Raum (kleinstes n mit P ≥ ½): 365 → 23, Mars 687 → 32 (52.0 %; 31 ergibt 49.7 %), 65 536 Behälter → 302, 2^32 → 77 164 die Quadratwurzelregel: n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - der Raum wächst mit der Quadratwurzel der Tage, nicht mit den Tagen Läufe: eine Ziehung pro Person, Tag = floor(r·m), über das gemeinsame xorshift; Startwert 1 bei 365 Tagen: die 40. Person landet an Tag 200, bereits von der 34. Person belegt; Startwerte 1…1000: 518 kollidieren bis 23 Personen, mittlere erste Kollision 24.05 Hashes: dieselbe Arithmetik für Schlüssel in Behältern - ein Hash a 32-Bit kollidiert erwartungsgemäß nach etwa 77 000 Schlüsseln
