Math
Cumpleaños y colisiones
La gente llega a un anillo de días hasta que dos comparten uno: en un año de 365 es la 23.ª persona, no la 183.ª; en Marte la 32.ª; en 65 536 cubetas de hash la 302.ª: tiradas contra la curva exacta, los días barridos arrastrando desde un año hasta 2³², la regla de la raíz cuadrada leída en vivo, y una tarea sobre la sala marciana.
Qué ocurre
Un anillo de días. La gente llega de una en una y enciende el día en que cae; la primera vez que alguien cae en un día encendido, el anillo destella y la tirada termina. En un año de 365 días eso ocurre hacia la 23.ª persona, no la 183.ª, porque la pregunta no es si alguien comparte tu cumpleaños sino si dos cualesquiera comparten uno, y entre 23 personas hay 253 parejas. La curva exacta es 1 − (1 − 1/m)(1 − 2/m)…(1 − (n − 1)/m): 50,7 % con 23, 99 % con 57. Tirada tras tirada, la gráfica rellena la fracción empírica sobre la curva. Arrastra por el anillo y el número de días barre en escala logarítmica: un año marciano de 687 días necesita 32 personas, una tabla hash de 65 536 cubetas colisiona en la clave 302, un hash de 32 bits hacia la 77 000: la sala que colisiona con probabilidad de moneda sigue √(2m ln 2), la raíz cuadrada de los días, no los días. Por eso un hash necesita muchas más cubetas que claves, y por eso el ataque del cumpleaños es la forma más barata de romper una firma corta.
Ecuaciones del módulo
Ecuaciones colisión con n personas: P = 1 − (1 − 0/m)(1 − 1/m)…(1 − (n − 1)/m); 365 días: 22 personas 47.6 %, 23 personas 50.7 %, 57 personas 99 %; la primera colisión esperada es la persona 24.617 la sala de cara o cruz (menor n con P ≥ ½): 365 → 23, Marte 687 → 32 (52.0 %; 31 da 49.7 %), 65 536 cubetas → 302, 2^32 → 77 164 la regla de la raíz cuadrada: n ≈ √(2m ln 2) = 22.5, 30.9, 301.4, 77 162.7 - la sala crece con la raíz cuadrada de los días, no con los días ejecuciones: un sorteo por persona, día = floor(r·m), mediante el xorshift compartido; semilla 1 en 365 días: la cuadragésima persona cae en el día 200, ocupado por la trigésima cuarta; semillas 1…1000: 518 colisionan con 23 personas, primera colisión media 24.05 funciones hash: la misma aritmética para claves en cubetas - se espera que una función hash de 32-bits colisione tras unas 77 000 claves
