Math
Hachages et casiers
Une table de tri : les clés sont des étiquettes en papier, un chariot hache chacune et la laisse tomber dans le casier que son hachage nomme, une collision est deux clés différentes dans un même casier. Le hachage est une fonction nommée – somme des codes, polynôme en base 31, FNV-1a – ou l’oracle uniforme derrière la courbe des anniversaires. Modifiez une clé, suivez son hachage caractère par caractère, basculez un bit et comptez les bits du hachage qui bougent ; comparez deux fonctions sur les mêmes clés.
Ce qui se passe
Vingt-trois personnes dans une pièce partagent un anniversaire plus souvent qu’autrement, et la même arithmétique dimensionne une table de hachage. Ici les clés sont de vraies chaînes et le hachage une fonction NOMMÉE : la somme des codes des caractères, le polynôme en base 31, FNV-1a – ou l’oracle uniforme, qui n’a aucune clé et qui est le modèle derrière la courbe. Un chariot sur le rail hache chaque étiquette et la laisse tomber dans le casier de son indice ; une étiquette qui atterrit sur une autre est une collision, et les deux clés restent allumées. La feuille calcule le hachage de la clé sonde caractère par caractère, bascule un bit de la clé et compte les bits du hachage qui bougent. Trois questions restent séparées : les collisions, l’uniformité (χ² des remplissages contre n/m, espérance m − 1) et l’avalanche ; un histogramme uniforme sur des mots aléatoires n’est pas un verdict sur la fonction – donnez à la somme des lettres une liste d’anagrammes et chaque clé tombe dans un seul casier. Rien de tout cela n’est de la solidité cryptographique.
Équations du module
Équations n clés dans m casiers, uniformément P(au moins une collision) = 1 − produit (1 − i/m), EXACTEMENT : n = 23, m = 365 -> 0.50729723432398566 ; n = 50 -> 0.97037357957798842 nombre moyen de casiers vides = m·(1 − 1/m)^n EXACTEMENT - et non le m·e^(−n/m) habituel : pour n = m = 100 ils valent 36.603234127322921 et 36.787944, et la différence est visible clés jusqu'à la première collision, en moyenne : sqrt(pi·m/2) + 2/3 = 24.611199639354552 pour m = 365 (compté 24.6767 sur 20 000 exécutions) la charge maximale pour n = m se comporte comme ln n / ln ln n - un comportement ASYMPTOTIQUE, non une formule : le rapport mesuré CROÎT, 1.32 pour m = 64, 1.49 pour 256, 1.55 pour 1024 il est donc vérifié comme un encadrement et comme une tendance monotone, jamais fixé à un nombre mesuré face à la courbe exacte (20 000 exécutions chacune) : n = 10 -> 0.11605 contre 0.11695 ; n = 23 -> 0.50800 contre 0.50730 ; n = 70 -> 0.99920 contre 0.99916 fonctions nommées sur une clé k = c₁c₂…c_n (codes des caractères), toutes modulo 2³² : somme : h = Σ c_i ; base 31 : h ← 31·h + c_i ; FNV-1a : h₀ = 2166136261, h ← (h xor c_i)·16777619 casier = h mod m ; l'oracle uniforme tire le casier d'après la graine et le NUMÉRO de la clé - il n'a pas de clé uniformité : χ² = Σ (load_j − n/m)² / (n/m) sur les m casiers ; une répartition uniforme donne m − 1 ± √(2(m − 1)) avalanche : moyenne sur les clés de Hamming(h(k), h(k′)) lorsque UN bit de k est inversé ; une fonction idéale en déplace 16 sur 32 mesuré (graine 20260913, 40 mots aléatoires dans 64 casiers) : FNV-1a 7 collisions, χ² 46.4, avalanche 14.6 ; base 31 : 9, 52.8, 6.2 ; somme : 8, 52.8, 2.05 ; oracle : 9, 59.2, aucun bit 40 anagrammes d'un même mot sous la somme : 39 collisions, une chaîne de 40, χ² = 2520 - la somme ne distingue pas l'ordre des lettres
