Math
Hashes y cubos
Una mesa de clasificación: las claves son etiquetas de papel, un carro calcula el hash de cada una y la deja caer en el cubo que su hash nombra, y una colisión son dos claves distintas en un mismo cubo. El hash es una función con nombre – suma de códigos, polinomio en base 31, FNV-1a – o el oráculo uniforme tras la curva de los cumpleaños. Edite una clave, vea su hash calculado carácter a carácter, invierta un bit y cuente los bits del hash que cambian; compare dos funciones sobre las mismas claves.
Qué ocurre
Veintitrés personas en una sala comparten cumpleaños más veces que no, y la misma aritmética dimensiona una tabla hash. Aquí las claves son cadenas reales y el hash una función CON NOMBRE: la suma de los códigos de los caracteres, el polinomio en base 31, FNV-1a – o el oráculo uniforme, que no tiene clave alguna y es el modelo tras la curva. Un carro sobre el raíl calcula el hash de cada etiqueta y la deja caer en el cubo de su índice; una etiqueta que cae sobre otra es una colisión, y ambas claves quedan iluminadas. La hoja calcula el hash de la clave de prueba carácter a carácter, invierte un bit de la clave y cuenta los bits del hash que cambian. Tres preguntas se mantienen separadas: colisiones, uniformidad (χ² de las cargas contra n/m, esperanza m − 1) y avalancha; un histograma uniforme sobre palabras aleatorias no es un veredicto sobre la función – dele a la suma de letras una lista de anagramas y todas las claves caen en un solo cubo. Nada de esto es fortaleza criptográfica.
Ecuaciones del módulo
Ecuaciones n claves en m cubos, de forma uniforme P(al menos una colisión) = 1 − prod (1 − i/m), EXACTAMENTE: n = 23, m = 365 -> 0.50729723432398566; n = 50 -> 0.97037357957798842 cubos vacíos esperados = m·(1 − 1/m)^n EXACTAMENTE - no el habitual m·e^(−n/m): con n = m = 100 son 36.603234127322921 y 36.787944, y la diferencia se nota claves hasta la primera colisión, en promedio: sqrt(pi·m/2) + 2/3 = 24.611199639354552 para m = 365 (contado 24.6767 en 20 000 ejecuciones) la carga máxima con n = m se comporta como ln n / ln ln n - una ASINTÓTICA, no una fórmula: la razón medida CRECE, 1.32 con m = 64, 1.49 con 256, 1.55 con 1024 por eso se comprueba como un intervalo y como una tendencia monótona, nunca fijada a un número medido frente a la curva exacta (20 000 ejecuciones cada una): n = 10 -> 0.11605 frente a 0.11695; n = 23 -> 0.50800 frente a 0.50730; n = 70 -> 0.99920 frente a 0.99916 funciones con nombre sobre una clave k = c₁c₂…c_n (códigos de caracteres), todas módulo 2³²: suma: h = Σ c_i; base 31: h ← 31·h + c_i; FNV-1a: h₀ = 2166136261, h ← (h xor c_i)·16777619 cubo = h mod m; el oráculo uniforme extrae el cubo de la semilla y del NÚMERO de la clave - no tiene clave uniformidad: χ² = Σ (load_j − n/m)² / (n/m) sobre los m cubos; un reparto uniforme da m − 1 ± √(2(m − 1)) avalancha: media sobre las claves de Hamming(h(k), h(k′)) con UN bit de k invertido; una función ideal cambia 16 de 32 medido (semilla 20260913, 40 palabras aleatorias en 64 cubos): FNV-1a 7 colisiones, χ² 46.4, avalancha 14.6; base 31: 9, 52.8, 6.2; suma: 8, 52.8, 2.05; oráculo: 9, 59.2, sin bits 40 anagramas de una palabra bajo la suma: 39 colisiones, una cadena de 40, χ² = 2520 - la suma no distingue el orden de las letras
